텍스트 파일 섞기 Delphi 소스 또는 기타

Question

10,000 개의 항목이있는 문자열 목록이 있습니다. 셔플 루틴을 가지고 있지만 항목에 액세스하는 데 많은 시간이 걸립니다. 10k 항목을 모두 거치려면 엄청난 시간이 필요합니다.

디스크를 저장하고 다른 방법을 사용하여 파일을 셔플하고 싶습니다.

제안 사항?

Answer 1

셔플 루틴은 어떻게 구현됩니까? 특히 교환 일과? 다음 내용을 직접 작성한 경우 :

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

매우 느립니다. 문자열 목록에 exchange-method를 사용하십시오.

가이 코드는 내 꽤 평균 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 (또는 64 비트 색인의 경우 N * 8)의 색인 스트림에서 줄 시작 오프셋을 검색하고 텍스트 파일 스트림의 해당 위치와 라인을 읽습니다.

이 방법을 사용하면 메모리 비용을 지불하지 않고도 매우 큰 파일을 섞을 수 있습니다. 물론, 셔플 링은 소스 파일에서 무작위로 라인을 추출하는 것을 의미합니다. 파일이 매우 작거나 (처음 액세스 할 때 거의 캐시에 들어 가지 않음) 또는 매우 큰 경우 (메모리 스레 싱의 경우)에는 메모리 내 정렬만큼 효율적이지 않습니다. 무작위 탐색보다 나빠질 수 있습니다.) 또는 기계식 하드 드라이브 (예 : SSD)를 사용하지 않는 경우입니다.

상황에 따라 10K는 실제로 큰 수가 아닙니다.1 천만 라인의 영역에서 뭔가 (아마도 라인의 길이에 따라) 수 기가 바이트의 텍스트를 얻는 것이 훨씬 더 어려울 것이며, 32 비트에서이 접근법 (또는 이와 유사한 것)이 필요할 것입니다.