У меня есть строковый список из 10 000 записей. У меня есть процедура перемешивания, но доступ к любому из элементов занимает много времени. На прохождение всех 10к предметов уходит огромное количество времени.
Я хочу сохранить его на диске, а затем перетасовать файл другим методом.
Какие-либо предложения?
Как реализована ваша процедура перемешивания? Особенно рутинный обмен? Если вы написали свое собственное, в следующих строках:
vTempSrting := vStringList[I];
vStringList.Delete(I);
vStringList.Insert(J,vTempString);
это будет очень медленно. Используйте метод обмена в списке строк.
Этот код занял 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.
Переупорядочивание списка строк в памяти происходит медленно, поэтому я бы перетасовал список индексов в качестве начальной оптимизации.
Я предполагаю, что вы выбрали строковый список для удобства загрузки и сохранения на диск. Один из более быстрых подходов - перетасовать индекс. Составьте массив из 10 000 целых чисел, перемешайте их, затем используйте временную строковую переменную для хранения элемента подкачки и переставьте свой строковый список сверху вниз, используя перемешанные значения индекса.
Значительные переписывания дадут большие улучшения, но это может помочь, если ваши строки не слишком велики.
Простой способ - сгенерировать список случайных чисел, отсортировать его, а затем выполнить попарную замену данных позже. Сортировка может выполняться по алгоритму o (n * log (n)), тогда как замена всегда выполняется по алгоритму o (n), что намного быстрее.
На всякий случай, если вы не подумали об этом, оставьте данные как есть и просто сохраните дополнительный перетасованный индекс.
Раньше я задавал вопрос о создании перетасованного диапазона - вместо того, чтобы создавать список чисел и затем перетасовывать их, мне нужна была функция, которая могла бы итеративно возвращать список перетасованных чисел без затрат памяти O (n):
Генерация перемешанного диапазона с использованием PRNG вместо перемешивания
Если вы создаете какой-то индекс для своего файла на диске, вы можете создать перетасованную версию, не платя за память, что может быть важно для очень больших файлов. Для индекса я предлагаю что-нибудь простое, например, плоский поток позиций (как 32- или 64-битные целые числа) начала каждой строки. Таким образом, чтобы извлечь N-ю строку из текстового файла, вы можете просто выполнить поиск в потоке индекса до N * 4 (или N * 8 для 64-битных индексов), чтобы определить смещение начала строки, а затем выполнить поиск эту позицию в потоке текстового файла и зачитайте строку.
Используя этот подход, вы можете перемешивать очень большие файлы, не тратя на это затраты в памяти. Конечно, перетасовка будет означать случайное извлечение строк из исходного файла, что не будет столь же эффективным, как сортировка в памяти, если только файл не очень маленький (помещается в кеш почти при первом доступе) или очень большой (в этом случае происходит переполнение памяти. будет хуже, чем случайный поиск), или, возможно, если вы не используете механический жесткий диск (например, SSD).
Для вашей ситуации 10К - это действительно небольшое число. Что-то в районе 10 миллионов строк, возможно, попадающее в несколько гигабайт текста (в зависимости от длины строки, конечно), будет намного сложнее, и именно здесь этот подход (или что-то подобное) будет необходим в 32-битной среде.
