Перемешать текстовый файл Delphi Source или что-нибудь еще

Question

У меня есть список строк с 10000 записей. У меня есть режим случайного воспроизведения, но доступ к любому из элементов занимает много времени. Прохождение всех 10к предметов занимает огромное количество времени.

Я хочу сохранить его на диске, а затем выполнить перемешивание файла другим способом.

Какие-либо предложения?

Answer 1

Как реализуется твой случайный порядок? Особенно обмен рутиной? Если вы написали свой собственный, по этим направлениям:

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

это будет очень медленно. Используйте метод exchange в списке строк.

Этот код занял 78 мс на моем довольно среднем (3 года) компьютере:

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

Перестановка списка строк в памяти происходит медленно, поэтому я бы перетасовал список индексов в качестве начальной оптимизации.

Я предполагаю, что вы выбрали stringlist для удобства загрузки и сохранения на диск. Одним из более быстрых подходов было бы перетасовать индекс. Создайте массив из 10000 целых чисел, перемешайте их, затем используйте временную строковую переменную для хранения элемента подкачки и перегруппируйте ваш список строк сверху вниз, используя перемешанные значения индекса.

Основные переписывания обеспечат большие улучшения, но это может помочь, если ваши строки не слишком велики.

Answer 3

Самый простой способ - создать список случайных чисел, отсортировать его, а затем выполнить попарно обмен данными позже. Сортировка может быть выполнена в виде алгоритма o(n*log(n)), тогда как замена всегда является алгоритмом o(n), таким образом, намного быстрее.

На случай, если вы не подумали об этом, рассмотрите возможность оставить данные как есть и просто сохранить дополнительный перетасованный индекс.

Answer 4

Ранее я задавал вопрос о создании перетасованного диапазона - вместо того, чтобы генерировать список чисел и затем перетасовывать их, я хотел функцию, которая могла бы итеративно возвращать список перетасованных чисел без затрат памяти O(n):

Генерация перетасованного диапазона с использованием PRNG вместо перетасовки

Если вы создаете какой-то индекс для вашего файла на диске, то вы можете создать перемешанную версию, не оплачивая стоимость памяти, что может быть важно для очень больших файлов. Для индекса я предлагаю что-то простое, например плоский поток позиций (как 32- или 64-разрядные целые числа) каждой строки в начале. Таким образом, чтобы извлечь N-ю строку из текстового файла, вы можете просто найти в потоке индекса значение N*4 (или N*8 для 64-битных индексов), чтобы обнаружить смещение начала строки, а затем попытаться эту позицию в потоке текстового файла и зачитать строку.

Используя этот подход, вы можете перетасовывать чрезвычайно большие файлы, не оплачивая стоимость в памяти. Конечно, перестановка будет означать случайное извлечение строк из исходного файла, что не будет столь же эффективно, как сортировка в памяти, если файл не очень маленький (помещается в кэш почти при первом обращении) или очень большой (в этом случае перегрузка памяти будет хуже, чем случайный поиск), или, возможно, если вы не используете механический жесткий диск (например, SSD).

Для вашей ситуации 10К действительно не большое число. Что-то в области 10 миллионов строк, возможно, в несколько гигабайт текста (в зависимости от длины строки, конечно), будет гораздо более сложным, и именно здесь этот подход (или что-то подобное) был бы необходим в 32-разрядной версии.