Shuffle Text File Delphi Source или что-нибудь еще

Question

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

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

Любые предложения?

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) Стоимость:

Generating shuffled range using a PRNG rather than shuffling

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

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

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