0

このコード化されたマージソートはhttp://www.explainth.at/en/delphi/dsort.shtmlで見つかりました（サイトはダウンしていますが、ウェイバックマシンまたはこのサイトを試してください：http：//read.pudn.com/downloads192/sourcecode/delphi_control/901147 /Sorts.pas__.htm）が、基本的に定義された配列は文字列の配列用ではありませんでした。 type TSortArray = array[0..8191] of Double; 重複を排除する可能性のある文字列の配列（これはUnionですか？）を渡し、可能であれば元の順序を保持して、後で元のインデックス位置から重複を差し引いたもの（元のインデックス）に戻して、配列を戻すことができるようにしたいさらなる処理のために。私は数百万の文字列（1400万から3000万）を含む非常に大きな文字列ファイルを使用しています。TStringListオプションではありません。これらの大きなファイルに最適なオプションは、文字列の配列またはレコードの配列（または単一のリンクリスト??）を使用し、大量のデータ用に作成された安定したアルゴリズムで並べ替えることです。

  1. 文字列の配列を取るようにこれを変更するにはどうすればよいですか？
  2. 重複を削除または少なくともマークするようにさらに変更するにはどうすればよいですか？
  3. 元のインデックス番号を保存して、文字列を元の位置に戻すことはできますか？
  4. 単一のリンクリストと比較して、文字列の配列またはレコードの配列は、多数の文字列に対して優れていますか？

質問は重要度の高い順にリストされているので、質問番号1に答える場合は、それだけで問題ありません。よろしくお願いします。

procedure MergeSort(var Vals:TSortArray;ACount:Integer);
var AVals:TSortArray;

  procedure Merge(ALo,AMid,AHi:Integer);
  var i,j,k,m:Integer;
  begin
    i:=0;
    for j:=ALo to AMid do
    begin
      AVals[i]:=Vals[j];
      inc(i);
      //copy lower half or Vals into temporary array AVals
    end;

    i:=0;j:=AMid + 1;k:=ALo;//j could be undefined after the for loop!
    while ((k < j) and (j <= AHi)) do
    if (AVals[i] < Vals[j]) then
    begin
      Vals[k]:=AVals[i];
      inc(i);inc(k);
    end else
    begin
      Vals[k]:=Vals[j];
      inc(k);inc(j);
    end;
    {locate next greatest value in Vals or AVals and copy it to the
     right position.}

    for m:=k to j - 1 do
    begin
      Vals[m]:=AVals[i];
      inc(i);
    end;
    //copy back any remaining, unsorted, elements
  end;

  procedure PerformMergeSort(ALo,AHi:Integer);
  var AMid:Integer;
  begin
    if (ALo < AHi) then
    begin
      AMid:=(ALo + AHi) shr 1;
      PerformMergeSort(ALo,AMid);
      PerformMergeSort(AMid + 1,AHi);
      Merge(ALo,AMid,AHi);   <==== passing the array as string causes AV breakdown here
    end;
  end;

begin
  SetLength(AVals, ACount);
  PerformMergeSort(0,ACount - 1);
end;
4

2 に答える 2

3

2番目の質問への回答：重複削除によるマージソートの変更。文字列に対して機能するはずです。

//returns new valid length
function MergeSortRemoveDuplicates(var Vals: array of Integer):Integer;
var
  AVals: array of Integer;

   //returns index of the last valid element
  function Merge(I0, I1, J0, J1: Integer):Integer;
  var
    i, j, k, LC:Integer;
  begin
    LC := I1 - I0;
    for i := 0 to LC do
      AVals[i]:=Vals[i + I0];
      //copy lower half or Vals into temporary array AVals

    k := I0;
    i := 0;
    j := J0;
    while ((i <= LC) and (j <= J1)) do
    if (AVals[i] < Vals[j]) then begin
      Vals[k] := AVals[i];
      inc(i);
      inc(k);
    end else  if (AVals[i] > Vals[j]) then begin
      Vals[k]:=Vals[j];
      inc(k);
      inc(j);
    end else begin //duplicate
      Vals[k] := AVals[i];
      inc(i);
      inc(j);
      inc(k);
    end;

    //copy the rest
    while i <= LC do begin
      Vals[k] := AVals[i];
      inc(i);
      inc(k);
    end;

    if k <> j then
      while j <= J1 do begin
        Vals[k]:=Vals[j];
        inc(k);
        inc(j);
      end;

    Result := k - 1;
  end;

 //returns index of the last valid element

  function PerformMergeSort(ALo, AHi:Integer): Integer; //returns
  var
    AMid, I1, J1:Integer;
  begin

  //It would be wise to use Insertion Sort when (AHi - ALo) is small (about 32-100)
    if (ALo < AHi) then
    begin
      AMid:=(ALo + AHi) shr 1;
      I1 := PerformMergeSort(ALo, AMid);
      J1 := PerformMergeSort(AMid + 1, AHi);
      Result := Merge(ALo, I1, AMid + 1, J1);
    end else
      Result := ALo;
  end;

begin
  SetLength(AVals, Length(Vals) div 2 + 1);
  Result := 1 + PerformMergeSort(0, High(Vals));
end;


//short test
var
  A: array of Integer;
  i, NewLen: Integer;
begin
  Randomize;
  SetLength(A, 12);
  for i := 0 to High(A) do
    A[i] := Random(10);
   NewLen := MergeSortRemoveDuplicates(A);
   SetLength(A, NewLen);
   for i := 0 to High(A) do
     Memo1.Lines.Add(IntToStr(A[i]))
  end;

文字列の簡単な変更：

function MergeSortRemoveDuplicates(var Vals: array of String):Integer;
var
  AVals: array of String;

およびテストケース：

var
  List: TStringList;
  Arr: array of string;
  i, n: Integer;
begin
  with TStringList.Create do try
    LoadFromFile('F:\m2.txt'); //contains some equal strings
    SetLength(Arr, Count);
    for i := 0 to Count - 1 do
      Arr[i] := Strings[i];
  finally
    Free
  end;
  n := MergeSortRemoveDuplicates(Arr);
  for i := 0 to n - 1 do
    Memo1.Lines.Add(Arr[i]);
end;
于 2012-10-01T16:46:16.447 に答える
2

  1. 宣言TSortArrayをdoubleの配列からstringの配列（またはMyRecordの配列）に変更する必要があります

    ネストされたプロシージャのマージの比較ルーチンは、文字列と互換性を持たせる必要があります。AVal [x] </>AVal[y]かどうかを判断する場所を確認します。Delphiには、このための手順があります（大文字と小文字を区別するかどうかに応じて、AnsiCompareText / AnsiCompareStr）

    それはうまくいくはずですが、以前の試みでこれをしていなかった場合、DelphiはAVを与えるのではなく、タイプの不一致について不平を言うはずだったので、何か他のことが起こっている可能性があります

  2. 重複チェックはソート後に実行する必要があると思います-データを1回スキャンするだけで済みます

  3. 元のインデックスデータを保存する場合は、おそらくレコードの配列（データ：文字列; OriginalIndex：整数）を使用する必要があります。次に、Mergeプロシージャのコードを変更して、Vals[x].Dataを比較ルーチンに渡す必要があります。OriginalIndex値の入力は、マージプロシージャを呼び出す前のクイックスキャンになります

  4. 100％確実ではありませんが、正直に言うと、配列よりもリンクリストを使用してデータの大きな連続チャンクを移動する方が簡単であり、配列はポインターをいじる必要がありません。データセットが十分に大きい場合は、ディスクへのストリーミングに頼る必要があるかもしれません。これは、これらのポイントのいずれよりも選択を促進する可能性があります。

于 2012-10-01T16:26:56.430 に答える