Newsgroup: it.comp.programmare
Titolo: Performance!!

Salve a tutti,
avrei bisogno di un consiglio sulla seguente questione.
Ho una mia applicazione che archivia dati in un file in forma di record
di tipo:
"campo1:int32, campo2:int32, campo3:int32, campo4:int32"
Nella tabella ho migliaia e migliaia di record e devo ordinarli,
rispetto ad uno o più campi.
Programmo in Visual C, utilizzo un algoritmo di quick sort ma la parte
che mi fa affondare (come tempo di esecuzione) è il controllo sui vari
campi..in pratica io non ho da ordinare un vettore di elementi in cui
posso fare if(v[i]<v[j]) per esempio; ho una funzione che verifica che
il record[n] ed il record[m] verifichino le condizioni impostate.
Anche per ordinare solo 1000 record ci mette minuti sul mio P2!!!!
Che fare?!!? Sto sbagliando qualcosa alla base!?
Grazie a tutti per l'aiuto.
-- 
Posted via Mailgate.ORG Server - 
http://www.Mailgate.ORG

 Che fare?!!? Sto sbagliando qualcosa alla base!?
Se credi di esserti spiegato, ti stai sbagliando, perche' non ho capito
molto del tuo problema.
In primo luogo: i record possono essere definiti nel seguente modo:
  struct { unsigned long campo1, campo2, campo3, campo4; }
o sono record testuali, magari a lunghezza variabile?
In secondo luogo: e' fattibile leggere tutto il file in memoria, o
richiederebbe troppa memoria?
In terzo luogo: i campi di ordinamento hanno un range (valore minimo
e valore massimo) piu' limitato del loro tipo o possono assumere
pressoche' qualunque valore permesso dal loro tipo?
Sapendo queste informazioni, possibilmente corredate da un breve esempio
dei dati, puoi sperare in un aiuto.
-- 
	Carlo Milanesi
 
http://digilander.libero.it/carlmila

Hai ragione, mi sono spiegato malissimo! Però anche tu un pò acido eh..?
Comunque cerco di spiegarmi meglio:
Sto scrivendo un software che archivia, e poi riutilizza, dei dati
tramite un file.
Il file viene scritto nel seguente formato:
Record1, Record2,...RecordN
Dove il singolo elemento Record viene definito nel seguente modo:
typedef struct
{
  int nID;
  int nItemID;
  time_t tAcquTime;
  float fValue;
} RECORD;
I dati vengono letti in memoria (dal disco) in un solo blocco. Da una
analisi preventiva abbiamo stimato che non c'è problema.
Il problema sorge nel momento in cui vogliamo ordinare i record secondo
uno o più campi.
Mi spiego: l'utilizzo di un algoritmo di quick sort per ordinare un
qualsiasi vettore di interi in maniera crescente è sicuramente molto
veloce.
Noi però dobbiamo ordinare i record secondo uno o più campi ed in modo
crescente o decrescente a seconda delle scelte dell'utente.
Tutto questo complica moltissimo la verifica della condizione per
l'ordinamento, che poi rallenta tutto.
In altre parole nell'ordinamento di un semplice vettore di interi io
farò il confronto in una singola istruzione (ad es. v[i] < v[j]).
Nell'ordinamento dei record per campi io devo scrivere una procedura per
verificare che un record sia maggiore o minore(rispetto a tutti i campi)
di un altro!!
Questa procedura di confronto (comunque molto banale!!) appesantisce
enormemente l'ordinamento.
Come risolveresti il problema!?
Ti ringrazio e spero di essermi spiegato meglio di ieri che avevo un
gran mal di testa!! :P


 Come risolveresti il problema!?
Mi sembra strano che una procedura di confronto _scritta in C_ possa
rallentare tanto le cose.  Comunque, il problema e` un classico nei
linguaggi di piu` alto livello, e la soluzione e` nota come "DSU"
(Decorate-Sort-Undecorate) in Python, e "Schwartzian transform" in
Perl (in onore di Randal Schwartz).
In termini C, possiamo descrivere l'appoggio come segue.
Vogliamo sortare un array X di N elementi, magari molto grossi,
sulla base di condizioni di confronto fra coppie di elementi (i,j)
che possono essere magari complicate da calcolare ma si prestano
ad essere ridotte a confronti elementari della forma:
    chiave(X[i]) < chiave(X[j])
la funzione "chiave" ritorna una qualche stringa di bit di
dimensione fissa che puo` essere confrontata rapidamente.  In
addizione spesso e` richiesta la condizione di stabilita` del
sort, cioe`, se i e j portano a chiavi eguali, l'ordine fra di
essi non deve essere alterato (e il quicksort normalmente non
rispetta questo tipo di vincoli).
Soluzione: 
1. "decorate"
allocare un array parallelo Y di N celle ciascuna con spazio
per una chiave seguita da un indice; poi inizializzare Y:
for(i=0; i<N; ++i) {
    Y[i].spaziochiave = chiave(X[i]);
    Y[i].indice = i;
}
questo passo e` O(N), quindi per N sufficientemente grande
e` trascurabile rispetto al sort vero e proprio, O(N log N)
2, "sort"
sortare Y.  il confronto diretto fra due elementi di Y e`
massimamente veloce; se la parte 'spaziochiave' risulta
equale nei due elementi il confronto naturalmente prosegue
con la parte 'indice' e questo dettaglio garantisce la
stabilita` del sort.
3. "undecorate"
usare la sequenza di indici negli elementi di Y per fare
il cambio di ordinamento in X -- ottenere una copia sortata
e` banale, ma anche usare questa informazione per un sort
in-place e` facile (e` il classico problema "applica una
permutazione); comunque, anche questa parte e` O(N)
In pratica, DSU puo` essere visto come l'applicazione di
un preprocessing (D) e postprocessing (U), che sono O(N),
per accelerare al massimo la parte centrale, che e`
O(N log N).  Invece di 2 N log N "estrazioni di chiave"
se ne eseguono solo N, e per N sufficientemente alto ed
"estrazione di chiave" sufficientemente onerosa cio`
ripaga ampiamente lo sforzo supplementare (allocazione di
Y, applicazione di permutazione in X).  Benefici ausiliari:
facile ottenimento di sort stabile; se gli elementi di X
sono molto grossi (per cui scambiarli e` oneroso), ma si
sortano su chiavi piu` piccole, DSU garantisce di minimizzare
il numero di scambi nella parte "applicazione di permutazione".
Alex

 eh..?
Scusa, ma il tatto non e' il mio forte!

Sei stato chiaro, ma stento a credere che, se invece di un confronto
tra numeri interi ne fai tre, ottieni un risultato scadente.
Comunque, puoi tenere conto dei seguenti suggerimenti:
1) Usare std::sort invece di qsort. Siccome il Visual C compila anche
codice C++, puoi usare gli algoritmi della libreria standard del C++,
che sono piu' efficienti di qsort, perche' espandono in linea la routine
di confronto invece di effettuare una chiamata di funzione. L'algoritmo
"sort" e' il piu' veloce, ma non mantiene l'ordine di elementi
equivalenti, l'algoritmo "stable_sort" invece lo mantiene.
2) Usare un array di appoggio, come suggerito da Alex Martelli.
3) Usare l'algoritmo binsort. Se devi ordinare secondo il campo nID, e
il range del campo nID contiene un numero di valori non molto superiore
al numero di record da ordinare, l'algoritmo binsort e' il migliore.
Se, per esempio, nei tuoi dati il valore minimo di nID e' 0 e il valore
massimo e' 5 milioni, e devi ordinare 3 milioni di record. Puoi creare
un array 5 milioni di bucket (5 * 4 = 20 MB) e una free list di 3
milioni di nodi (3 * 8 = 24 MB)
Questo vale anche per il campo nItemID.
Disponibile per chiarimenti.
-- 
	Carlo Milanesi
 
http://digilander.libero.it/carlmila
 
http://digilander.libero.it/carlmila

 ha scritto nel messaggio
news:d411da2f069c7a47582...@mygate.mailgate.org...
