셔플 텍스트 파일 델파이 소스 또는 다른 것
-
05-07-2019 - |
문제
10,000 개의 항목이있는 StringList가 있습니다. 셔플 루틴이 있지만 항목에 액세스하는 데 많은 시간이 걸립니다. 모든 10k 품목을 모두 겪으려면 많은 시간이 걸립니다.
디스크를 저장 한 다음 다른 방법을 사용하여 파일에 셔플을 수행하고 싶습니다.
제안이 있습니까?
해결책
셔플 라우팅은 어떻게 구현됩니까? 특히 Exchange-Routine? 당신이 직접 작성한 경우, 다음 줄을 따라 다음과 같습니다.
vTempSrting := vStringList[I];
vStringList.Delete(I);
vStringList.Insert(J,vTempString);
매우 느릴 것입니다. StringList에서 Exchange 방법을 사용하십시오.
이 코드는 평균 (3 세) 컴퓨터에서 78ms를 사용했습니다.
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.
다른 팁
메모리에서 StringList를 재 배열하면 느리기 때문에 초기 최적화로 인덱스 목록을 셔플합니다.
로드하고 디스크에 저장하는 편의성을 위해 StringList를 선택했다고 생각합니다. 더 빠른 접근 방식은 색인을 셔플하는 것입니다. 10,000 정수의 배열을 만들고, 셔플 한 다음, 임시 문자열 변수를 사용하여 스왑 요소를 유지하고 셔플 인덱스 값을 사용하여 StringList를 위에서 아래로 재 배열하십시오.
주요 다시 쓰기는 더 큰 개선을 제공하지만 문자열이 너무 크지 않으면 도움이 될 수 있습니다.
쉬운 방법은 임의 숫자 목록을 생성하고 정렬 한 다음 나중에 데이터를 교체하는 것입니다. 정렬은 O (n*log (n)) 알고리즘으로 수행 될 수 있지만, 스왑은 항상 O (n) 알고리즘이므로 훨씬 빠릅니다.
생각하지 않은 경우 데이터를 그대로 두는 것을 고려하고 추가 셔플 인덱스를 저장하십시오.
숫자 목록을 생성 한 다음 섞는 대신 셔플 레인지를 만드는 것에 대해 전에 질문을했습니다. O (n) 메모리 비용없이 셔플 숫자 목록을 반복적으로 반환 할 수있는 기능을 원했습니다.
셔플 링 대신 PRNG를 사용하여 셔플 레인지를 생성합니다
디스크에서 파일에 대한 종류의 색인을 만들면 메모리 비용을 지불하지 않고 셔플 버전을 만들 수 있습니다. 이는 매우 큰 파일에 중요 할 수 있습니다. 색인의 경우 모든 라인 시작의 위치 (32 또는 64 비트 정수)의 평평한 스트림과 같은 간단한 것을 제안합니다. 이렇게하면 텍스트 파일에서 N 번째 줄을 추출하려면 인덱스 스트림에서 단순히 N*4 (또는 64 비트 인덱스의 N*8)를 찾아 라인 시작의 오프셋을 발견 한 다음 추구 할 수 있습니다. 텍스트 파일 스트림에서 해당 위치를 읽고 줄을 읽습니다.
이 접근법을 사용하면 메모리 비용을 지불하지 않고도 매우 큰 파일을 셔플 할 수 있습니다. 물론, 셔플 링은 소스 파일에서 무작위로 선을 추출하는 것을 의미합니다. 파일이 매우 작지 않는 한 (첫 번째 액세스에 거의 캐시에 적합) 또는 매우 큰 (이 경우 메모리 스 래싱에 적합하지 않으면 메모리 내 분류만큼 효율적이지 않습니다. 무작위가 추구하는 것보다 더 나빠질 것입니다) 또는 아마도 기계식 하드 드라이브 (예 : SSD)를 사용하지 않는 경우.
당신의 상황에서는 10k는 실제로 다수가 아닙니다. 1 천만 줄의 지역에있는 어떤 것, 아마도 여러 기가 바이트의 텍스트 (물론 라인 길이에 따라 다름)에 들어가는 것이 훨씬 더 어려울 것이며,이 접근법 (또는 유사한 것)이 32 비트에서 필요한 곳입니다.