Перемешать текстовый файл 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

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

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

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

Answer 3

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

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

Answer 4

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

Создание перетасованного диапазона с использованием PRNG, а не перетасовкой

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

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

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