Ho una matrice allocata dinamicamente di numeri interi in cui voglio inserire numeri interi in posizioni arbitrarie. Molti numeri interi come in più di 2,5 milioni.Come gestisco in modo efficiente più inserti in un array?
Il mio codice attualmente appare così:
type
TIntegerArr = array of Integer;
var
FCount: Integer;
FSortedList: TIntegerArr;
procedure Insert(_Value: Integer; _InsertPos: integer);
var
OldList: TIntegerArr;
begin
OldList := FSortedList;
if Length(FSortedList) < FCount + 1 then begin
OldList := FSortedList;
FSortedList := nil;
SetLength(FSortedList, FCount + 100);
CopyMemory(@FSortedList[0], @OldList[0], SizeOf(Integer) * _InsertPos);
end;
MoveMemory(@FSortedList[_InsertPos + 1], @OldList[_InsertPos], SizeOf(Integer) * (FCount - _InsertPos));
FSortedList[_InsertPos] := _Value;
Inc(FCount);
end;
(Il codice reale è un metodo di una classe che ha FSortedList e FCOUNT come campi.)
Utilizzando un elenco temporaneo e l'utilizzo di Sposta piuttosto che un ciclo for per lo spostamento dei dati ha migliorato le prestazioni già abbastanza perché impedisce che l'array venga copiato due volte quando deve crescere (una volta in SetLength sull'array esistente e un'altra volta con Move).
Ma il caso peggiore Insert (SomeValue, 0) sposta sempre tutti i valori esistenti.
Finora stavo pensando lungo la linea di introdurre un offset all'inizio dell'array quindi piuttosto che dover spostare tutti i valori esistenti ogni volta che un nuovo valore è inserito nella parte anteriore, potrei farlo solo quando l'offset raggiunge 0. Es:
// simple case: inserting at Position 0:
if FOffset = 0 then begin
// [...] reallocate a new array as above
Move(@FSortedList[100], @OldList, SizeOf(Integer) * _InsertPos);
FOffset := 100;
end;
Dec(FOffset);
FSortedList[FOffset] := _NewValue;
(Questo codice è testato e probabilmente buggy) Ciò naturalmente può essere esteso per verificare se il punto di inserimento è più vicino all'inizio o alla fine e seconda che si muovono sia il primo o gli ultimi valori di una posizione in modo tale che in media solo 1/4 delle voci deve essere spostato anziché 1/2 come è attualmente.
Un'altra opzione sarebbe l'implementazione di un array sparse. Ricordo di aver visto una tale implementazione in alcune biblioteche commerciali negli anni '90, ma non ricordo quale fosse (TurboPower?).
Questa procedura è fondamentale per alcuni codici di ordinamento e indicizzazione che funzionano su matrici di dimensioni diverse, da poche decine di voci fino ai milioni di voci sopra menzionate.
Attualmente il programma è in esecuzione per circa 2 ore (prima delle mie ottimizzazioni erano prossime alle 5 ore) e so già che il numero di voci nell'array è almeno raddoppiato. Man mano che le prestazioni degli inserti peggiorano, tanto più grande è già l'array, sospetto che con il doppio del numero di voci, il tempo di esecuzione sarà almeno quadruplo.
Vorrei alcuni suggerimenti su come ottimizzare le prestazioni. Il consumo di memoria non è attualmente un grosso problema, ma il tempo di esecuzione lo è sicuramente.
(Questo è Delphi 2007, ma che non dovrebbe fare molta differenza a meno che le nuove versioni di Delphi hanno già una libreria ottimizzata per fare quanto sopra Classes.TList non è ottimizzato..)
Edit1: Appena trovato la scarsa implementazione dell'array che ho menzionato sopra: è StColl di TurboPower SysTools.
Edit2: Ok, un po 'di background: Il mio programma legge una tabella DBase con attualmente 2,4 milioni di voci e genera diverse nuove tabelle da queste voci. Le nuove tabelle sono normalizzate e sono indicizzate dopo che sono state create (per ragioni di prestazioni non generi gli indici prima di inserire i dati, credetemi, l'ho provato prima.). La matrice è la parte centrale del codice che fornisce l'ordinamento interno per le tabelle generate. I nuovi record vengono aggiunti alla tabella, ma il loro RecNo viene inserito nell'array in ordine ordinato.
Vedere ['Implementazione migliorata di array di fette] (http://www.cromis.net/blog/2013/03/improved-sliced-array-implementation/) di [' @ Runner'] (http: // stackoverflow.com/users/118765/runner) se questo fornisce un input su come migliorare l'ordinamento. –
@LURD: Grazie. Ho letto questo post sul blog quando lo ha scritto (il primo commento su quella pagina è mio) ma avevo già dimenticato. – dummzeuch
Dicci di più su casi d'uso per questo "array inseribile". Possibili soluzioni dipendono da loro. – MBo