Shuffle Text File Delphi Source o cualquier otra cosa

Question

Tengo una lista de cadenas con 10,000 entradas. Tengo una rutina aleatoria, pero el acceso a cualquiera de los elementos lleva mucho tiempo. Pasar por todos los 10k artículos lleva mucho tiempo.

Quiero guardarlo en el disco y luego hacer una reproducción aleatoria del archivo usando otro método.

¿Alguna sugerencia?

Answer 1

¿Cómo se implementa tu rutina aleatoria? ¿Especialmente la rutina de intercambio? Si has escrito el tuyo, siguiendo estas líneas:

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

será muy lento. Utilice el método de intercambio en la lista de cadenas.

Este código tomó 78 ms en mi computadora bastante promedio (3 años):

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

La reorganización de una lista de cadenas en la memoria es lenta, así que barajaría una lista de índice como una optimización inicial.

Supongo que eligió la lista de cadenas por la conveniencia de cargar y guardar en el disco. Un enfoque más rápido sería barajar un índice. Haga una matriz de 10,000 enteros, mezcle esos, luego use una variable de cadena temporal para mantener el elemento de intercambio y reorganice su lista de cadenas de arriba a abajo usando los valores de índice barajados.

Las reescrituras principales proporcionarán mejoras mayores, pero esto puede ayudar si tus cadenas no son demasiado grandes.

Answer 3

Una forma fácil es generar una lista de números aleatorios, ordenarla y luego hacer intercambios de datos por pares más tarde. La clasificación se puede hacer como un algoritmo o (n * log (n)), mientras que el intercambio siempre es un algoritmo o (n), por lo tanto mucho más rápido.

En caso de que no lo hayas pensado, considera dejar los datos como están y guarda un índice extra barajado.

Answer 4

Antes hice una pregunta sobre la creación de un rango aleatorio: en lugar de generar una lista de números y luego mezclarlos, quería una función que fuera capaz de devolver de forma iterativa una lista de números aleatorios, sin el costo de memoria O (n) :

Generando el rango aleatorio utilizando un PRNG en lugar de barajar

Si crea algún tipo de índice para su archivo en el disco, puede crear una versión aleatoria sin pagar el costo de la memoria, lo que puede ser importante para archivos muy grandes. Para un índice, sugiero algo simple, como un flujo plano de las posiciones (como enteros de 32 o 64 bits) de cada inicio de línea. De esa manera, para extraer la línea Nth del archivo de texto, simplemente puede buscar en el flujo de índice a N * 4 (o N * 8 para índices de 64 bits) para descubrir el desplazamiento del inicio de línea, y luego buscar esa posición en el flujo de archivos de texto y leer una línea.

Usando este enfoque, puedes mezclar archivos extremadamente grandes, sin pagar el costo de la memoria. Por supuesto, la combinación aleatoria significará extraer líneas al azar del archivo de origen, lo que no será tan eficiente como la clasificación en memoria a menos que el archivo sea muy pequeño (se ajuste a la memoria caché casi en el primer acceso) o muy grande (en cuyo caso, la memoria no funciona) será peor que las búsquedas aleatorias), o tal vez si no está utilizando un disco duro mecánico (por ejemplo, SSD).

Para su situación, 10K realmente no es un número grande. Algo en la región de 10 millones de líneas, quizás con varios gigabytes de texto (dependiendo de la longitud de la línea, por supuesto), será mucho más difícil, y ahí es donde este enfoque (o algo similar) sería necesario en 32 bits.