Shuffle Source File Delphi o qualsiasi altra cosa

Question

Ho una lista di stringhe con 10.000 voci. Ho una routine di riproduzione casuale, ma l'accesso a qualsiasi elemento richiede molto tempo. Esaminare tutti gli articoli da 10k richiede molto tempo.

Voglio salvarlo su disco e quindi fare un riordino del file usando un altro metodo.

Qualche suggerimento?

Answer 1

Come viene implementata la tua routine shuffle? Soprattutto la routine di scambio? Se hai scritto il tuo, in questo senso:

vTempSrting := vStringList[I]; 
vStringList.Delete(I); 
vStringList.Insert(J,vTempString);

sarà molto lento. Utilizzare il metodo di scambio nell'elenco di stringhe.

Questo codice ha impiegato 78 ms sul mio computer piuttosto medio (di 3 anni):

program Project1;

{$APPTYPE CONSOLE}

uses
  SysUtils,Classes,uIntegerList,Windows,Math;

procedure Shuffle(aSL : TStringList);
var I,J : integer;
begin
  for I := 0 to aSL.Count-1 do
  begin
    J := randomrange(I,aSL.Count);
    aSL.Exchange(I,J);
  end;
end;

procedure CreateTestFile;
var
  vSL : TStringList;
  I : integer;
begin
  vSL := TStringList.Create;
  try
    for I := 1 to 100000 do vSL.Add('Sample text #'+inttostr(I));
    vSL.SaveToFile('c:\test.txt');
  finally
    vSL.Free;
  end;
end;

function TestShuffle : longword;
var
  vSL : TStringList;
  vTick0 : longword;
begin
  vSL := TStringList.Create;
  try
    vTick0 := gettickcount;
    vSL.LoadFromFile('c:\test.txt');
    Shuffle(vSL);
    vSL.SaveToFile('c:\test.txt');
    Result := gettickcount - vTick0;
  finally
    vSL.Free;
  end;
end;

begin
  CreateTestFile;
  writeln(TestShuffle,' ms');
  readln;
end.

Answer 2

Riorganizzare un elenco di stringhe in memoria è lento, quindi mescolerei un elenco di indici come ottimizzazione iniziale.

Suppongo che tu abbia scelto stringlist per la comodità di caricare e salvare su disco. Un approccio più rapido sarebbe quello di mescolare un indice. Crea una matrice di 10.000 numeri interi, mescola quelli, quindi usa una variabile di stringa temporanea per contenere l'elemento di scambio e riorganizza l'elenco di stringhe dall'alto verso il basso utilizzando i valori dell'indice mischiato.

Le riscritture importanti forniranno maggiori miglioramenti, ma ciò può aiutare se le stringhe non sono troppo grandi.

Answer 3

Un modo semplice è generare un elenco di numeri casuali, ordinarlo e quindi effettuare scambi di dati a coppie in un secondo momento. L'ordinamento può essere fatto come un algoritmo o (n * log (n)), mentre lo scambio è sempre un algoritmo o (n), quindi molto più veloce.

Nel caso in cui non ci avessi pensato, considera di lasciare i dati così come sono e di salvare un indice mischiato extra.

Answer 4

Prima ho fatto una domanda sulla creazione di un intervallo mescolato - piuttosto che generare un elenco di numeri e quindi mescolarli, volevo una funzione che fosse in grado di restituire iterativamente un elenco di numeri mescolati, senza il costo di memoria O (n) :

Generazione dell'intervallo mischiato usando un PRNG anziché mischiarlo

Se crei un qualche tipo di indice per il tuo file su disco, puoi creare una versione mescolata senza pagare il costo della memoria, che può essere importante per file molto grandi. Per un indice, suggerisco qualcosa di semplice, come un flusso piatto delle posizioni (come numeri interi a 32 o 64 bit) di ogni inizio di riga. In questo modo, per estrarre l'ennesima riga dal file di testo, puoi semplicemente cercare nel flusso dell'indice su N * 4 (o N * 8 per gli indici a 64 bit) per scoprire l'offset dell'inizio della riga e quindi cercare di quella posizione nel flusso di file di testo e leggere una riga.

Usando questo approccio, puoi mescolare file estremamente grandi, senza pagare il costo in memoria. Ovviamente, mischiare significherà estrarre le righe in modo casuale dal file sorgente, che non sarà efficiente come l'ordinamento in memoria a meno che il file non sia molto piccolo (si inserisca nella cache quasi al primo accesso) o molto grande (nel qual caso il thrashing della memoria sarà peggio delle ricerche casuali) o forse se non si utilizza un disco rigido meccanico (ad esempio SSD).

Per la tua situazione, 10K non è davvero un numero elevato. Qualcosa nella regione di 10 milioni di righe, forse entrare in diversi gigabyte di testo (a seconda della lunghezza della linea ovviamente), sarà molto più impegnativo, ed è qui che questo approccio (o qualcosa di simile) sarebbe necessario a 32 bit.