문제

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 비트에서 필요한 곳입니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top