隨機文本文件德爾福來源或其他

我有一個10000條目的字符串列表。我有一個洗牌程序，但訪問任何項目都花費了很多時間。通過所有10K項目需要大量的時間。隨機文本文件德爾福來源或其他

我想保存它做的磁盤，然後使用另一種方法對文件進行洗牌。

有什麼建議嗎？

2009-10-21 Hein du Plessis

您的洗牌程序如何實施？特別是交換程序？如果你已經寫下你自己的，請按照以下方式：

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.

來源

2009-10-21 11:16:17

哇感謝代碼svein！我確實使用了交換，但我剛剛解決了我的問題 - 字符串從備忘錄傳遞到了我的shuffeling過程 - 顯然，每次更新後，備忘錄必須更新10000個視覺項目！我現在使用中介AstrinList，對其進行排序，然後將其分配回備忘錄： aStringLIst：= TStringList.Create; aStringList.Assign（mNumbers.Lines）; Shuffle（aStringList）; mNumbers.Lines.Assign（aStringList）; aStringList.Free; 這是瞬間！非常感謝 – 2009-10-21 11:45:04

哇的評論真的搞砸了我的代碼，抱歉希望你能把它弄出來。 – 2009-10-21 11:46:13

沒問題，我可以讀它:-) – 2009-10-21 11:47:08

在內存中重新排列字符串列表很慢，所以我會將索引列表作爲初始優化進行洗牌。

我猜你選擇了stringlist方便從磁盤加載和保存到磁盤。一個更快的方法是洗牌索引。創建一個由10,000個整數組成的數組，然後使用臨時字符串變量來保存交換元素，並使用混洗後的索引值從上到下重新排列字符串列表。

主要重寫將提供更大的改進，但這可能有助於如果你的字符串不是太大。

來源

2009-10-21 11:04:17 Argalatyr

我確實使用TStringList，但問題是訪問任何東西需要很長時間，所以只需從上到下掃描需要幾分鐘。這只是一個數字列表，所以我可以將它加載到數組中並隨機播放它。我喜歡TStringList功能，但是，有沒有索引TStringList或者什麼？ – 2009-10-21 11:07:36

一個簡單的方法是生成隨機數的列表，排序，然後做數據的兩兩互換後。排序可以作爲o（n * log（n））算法完成，而交換總是一個o（n）算法，因此速度要快得多。

爲防萬一您沒有想到它，請考慮將數據保持原樣，並保存一個額外的洗牌索引。

來源

2009-10-21 11:26:47

我在創建混洗範圍之前問過一個問題 - 而不是生成一個數字列表然後洗牌，我想要一個函數能夠迭代地返回混洗數字列表，而不需要O（n）內存費用：

Generating shuffled range using a PRNG rather than shuffling

如果創建某種指數，爲您在磁盤上的文件，那麼你就可以不用管內存成本，這對於非常大的文件創建重要的一個改組型式。對於索引，我建議一些簡單的東西，比如每行開始的位置（32或64位整數）。這樣，爲了從文本文件中提取出第N行，可以簡單地在索引流中查找N * 4（或64 *索引的N * 8）以發現行開始的偏移量，然後嘗試在文本文件流中的位置並讀出一行。

使用此方法，您可以洗牌超大文件，而無需支付內存中的成本。當然，混洗意味着從源文件中隨機提取行，除非文件非常小（適合緩存幾乎在第一次訪問時）或非常大（在這種情況下，內存抖動會比隨機搜索更糟糕），或者如果你沒有使用機械硬盤驅動器（例如SSD）。

對於你的情況，10K真的不是一個大數字。在1000萬行的區域中，可能會佔用幾千兆字節的文本（當然取決於行長度），將會變得更具挑戰性，這就是32位的這種方法（或類似方法）所必需的。

來源

2009-10-21 19:28:16

感謝Barry，儘管我發現我的錯誤是使用shuffle函數進行控件的視覺更新。雖然有趣的方法！ – 2009-10-23 11:05:21

隨機文本文件德爾福來源或其他

回答

相關問題