0

在http://www.explainth.at/en/delphi/dsort.shtml上找到了这个编码的合并排序（站点关闭，但尝试使用 wayback 机器或这个站点：http ://read.pudn.com/downloads192/sourcecode/delphi_control/901147 /Sorts.pas__.htm）但本质上定义的数组不是字符串数组。 type TSortArray = array[0..8191] of Double; 我想传递一个字符串数组，它可能会消除重复项（这将是联合？），并尽可能保留原始顺序，以便以后将其恢复到原始索引位置减去重复项（原始索引），以便可以将数组传回用于进一步处理。我正在使用非常大的字符串文件，其中包含数百万个字符串（14 到 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

回答第二个问题：合并排序修改与重复删除。应该适用于字符串。

//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 数组修改为字符串数组（或 MyRecord 数组）

    合并嵌套过程中的比较例程需要与字符串兼容。检查确定是否为 AVal[x] < / > AVal[y] 的任何地方。Delphi 有这方面的程序（AnsiCompareText / AnsiCompareStr 取决于您是否需要区分大小写）

    那应该可以，但是如果您在之前的尝试中没有这样做，那么 Delphi 应该抱怨类型不匹配而不是提供 AV，所以可能还有其他事情发生

  2. 我认为重复检查应该在排序后进行 - 它只需要对数据进行一次扫描

  3. 如果要存储原始索引数据，则可能需要使用记录数组（数据：字符串；原始索引：整数）。然后需要修改 Merge 过程中的代码以将 Vals[x].Data 传递给比较例程。在调用 Merge 过程之前填充 OriginalIndex 值将是一个快速扫描

  4. 说实话，不是 100% 确定 - 使用链表移动大块连续的数据比使用数组更容易，而且数组不需要弄乱指针。如果您的数据集足够大，您甚至可能需要求助于流式传输到磁盘，这可能比这些点中的任何一个更能推动您的选择。

于 2012-10-01T16:26:56.430 回答