Esiste un'implementazione TList più veloce?

Question

La mia applicazione fa un uso pesante di TList, quindi mi chiedevo se ci sono implementazioni alternative che sono più veloci o ottimizzate per casi d'uso particolari.

Conosco RtlVCLOptimize.pas 2.77, che ha ottimizzato le implementazioni di diversi metodi TList.

Ma mi piacerebbe sapere se c'è qualcos'altro là fuori. Inoltre, non ho bisogno che sia un discendente TList, ho solo bisogno della funzionalità TList indipendentemente da come è implementata.

È assolutamente possibile, data la funzionalità piuttosto basilare fornita da TList, che non c'è molto margine di miglioramento, ma vorremmo comunque verificarlo, quindi questa domanda.

modifica: Nel mio caso di utilizzo particolare, nessun elenco è ordinato. Ci sono molte liste, con vari elementi in. Ho sostituito TList con la mia classe per registrare il numero di Aggiungi/Rimuovi chiamate e il conteggio degli elementi. Riferisce (toatal per tutte le liste):

ListAdd = 15766012; ListRemove = 10630000; ListCount = 5136012 

potrei anche scoprire che cosa il maggior numero di elementi in un unico elenco è.

Non ho alcun problema particolare, mi chiedo solo se c'è un modo per renderlo più veloce tutto intorno, visto che con questi numeri anche piccoli miglioramenti si sommano.

Answer 1

Uno dei maggiori collo di bottiglia che conosco su TList è l'eliminazione/estrazione nella lista grande. La rimozione dell'elemento [0] è molto più lenta della rimozione di Item [Count-1] a causa del movimento della memoria che lo segue.

Per exemple, in un elenco che contiene 65.536 elementi:

while list.Count > 0 do List.Delete(0) //Takes 2 mins to complete 

for I := List.Count-1 downto 0 do List.Delete(I) //Takes less than 1 sec 

Quindi, se si dispone di un TList con milioni di elementi, l'eliminazione di una voce di basso indice può essere costoso prestazioni-saggio.Inoltre, considera che avere una lista non ordinata rende molto lento trovare un elemento in essa. IndexOf è molto lento nella lista grande. Si potrebbe voler considerare di mantenere la lista ordinata.

Inoltre, considerando che il numero di elementi può essere piuttosto ampio, è consigliabile prendere in considerazione l'utilizzo di un elenco di TList per memorizzare i propri elementi, il che consentirà di ridurre l'overhead di eliminazione/estrazione che ho già menzionato.

Answer 2

La struttura di dati più veloce di solito non è una struttura di dati, ma piuttosto una simulazione che estrae i dati solo quando è necessario, proprio come fa Virtual Treeview. Forse puoi scrivere una sorta di TVirtualList che chiama le funzioni appropriate per raccogliere i dati richiesti quando gli elementi sono richiesti.

Answer 3

Sembra che tu stia facendo un sacco di aggiunte. Non so quante liste si sono diffuse, ma se i tuoi elenchi individuali stanno diventando molto grandi, potresti voler implementare un elenco che cresce più velocemente.

Dai uno sguardo allo TList.Grow, che viene chiamato quando tenti di aggiungere un elemento a un elenco in cui sono in uso tutti gli elementi dell'array e vedrai che aumenta del 25%. Questo serve a mantenere l'uso della memoria a un livello ragionevole. Ma se hai bisogno di elenchi davvero grandi, crea la tua classe discendente e sostituisci Grow in modo che nella seconda riga, invece di Delta := FCapacity div 4, venga indicato Delta := FCapacity. Questo fa sì che la tua lista cresca due volte più grande ogni volta, il che significa meno realloc e meno copie.

Ma la cosa che probabilmente ti sta uccidendo sono tutte quelle Rimuovi chiamate. Remove deve trovare l'elemento prima che possa rimuoverlo, il che implica una chiamata a IndexOf, che è una scansione lineare dell'intero array. Se hai una grande lista e stai facendo molte asportazioni, questo ucciderà la tua performance.

A cosa servono queste liste, in particolare quelle grandi? A seconda di cosa stai facendo con loro, potrebbero esserci strutture di dati migliori per il lavoro.

Answer 4

Stai utilizzando la procedura di notifica? Altrimenti, crea la tua implementazione TList. A causa della procedura di notifica, TList.Clear (che viene chiamato alla distruzione) è un'operazione O (n). Il metodo TList.Clear chiama SetCount che a sua volta chiama Delete per tutti gli elementi in esso contenuti in modo che la procedura di notifica venga chiamata per ogni elemento rimosso. Quando non è necessario eseguire l'override del metodo di notifica, è possibile regolare la procedura SetCount per non chiamare Elimina. Questo può farti risparmiare il tempo di 15.766.012 - 10.630.000 = 5.136.012 Cancellare le chiamate.

NB: il guadagno di prestazioni che si ottiene non sarà mai grande quanto il guadagno di prestazioni ottenuto ordinando l'elenco e ottimizzando la procedura di rimozione, come suggerito da Mason Wheeler. A meno che l'elenco non contenga un numero molto piccolo di elementi e la funzione di confronto richiede molto tempo.