レコードタイプと、そのレコードタイプで構成される動的配列があります。私はそれをマージソートルーチンに渡し、ブール値であるが効果がないように見えるフィールドプロパティの1つを設定しようとします。
他の方法でレコードの配列を並べ替えることを検討しました（customrecord配列についてはこのクイックソートを参照してください：http：//en.wikibooks.org/wiki/Algorithm_Implementation/Sorting/Quicksort#Delphi）またはここ：配列を並べ替える最良の方法（主にコマーリング関数を作成するために、これらの提案のいずれもここから機能しないようにします）。この質問：配列をアルファベット順に並べ替えますか？役に立ち、機能しましたが、この並べ替えは非常に遅いです。
コード：
type
TCustomRecord = Record
fLine : AnsiString; //full line
fsubLine : AnsiString; // part of full line
isDuplicate : boolean; //is that subline duplicate in another line
isRefrence : boolean; // is this line from a refrence file or the one being deduped
fIndex : Cardinal; // original order line was loaded
end;
TCustomRecordArray = array of TCustomRecord;
function Merge2(var Vals: array of TCustomRecord ):Integer;
var
AVals: array of TCustomRecord;
//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].fsubLine < Vals[j].fsubLine) then
begin
Vals[k] := AVals[i];
if Vals[k].isRefrence = False then
Vals[k].isDuplicate := False;
inc(i);
inc(k);
end
else if (AVals[i].fsubLine > Vals[j].fsubLine) then
begin
Vals[k]:=Vals[j];
if Vals[k].isRefrence = False then
Vals[k].isDuplicate := False;
inc(k);
inc(j);
end else
begin //duplicate
Vals[k] := AVals[i];
if Vals[k].isRefrence = False then
Vals[k].isDuplicate := True;
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) + 1 div 2);
SetLength(AVals, Length(Vals) div 2 + 1);
Result := 1 + PerformMergeSort(0, High(Vals));
end;
質問：できればmergesortを使用して、このレコードの配列を効率的に並べ替え、その並べ替えに従ってプロパティの一部を設定するにはどうすればよいですか？ありがとうございました。
更新：ポインター型を追加し、ポインターの配列に対して変更されたマージソートを実行しました。これは、レコードの配列をソートする非常に高速な方法であることが判明しました。必要なフラグを追加する比較ルーチンも追加しました。私ができない唯一の部分は、それらがファイルAまたは参照ファイルに属しているかどうかに基づいて重複のフラグを追加することです。
コード：
type
PCustomRecord = ^TCustomRecord;
TCustomRecord = Record
fLine : AnsiString; //full line
fsubLine : AnsiString; // part of full line
isDuplicate : boolean; //is that subline duplicate in another line
isRefrence : boolean; // line from a refrence file or the one being deduped
isUnique : boolean; //flag to set if not refrence and not dupe
fIndex : Cardinal; // original order line was loaded
end;
TCustomRecordArray = array of TCustomRecord;
PCustomRecordList = ^TCustomRecordArray;
//set up actual array
//set up pointer array to point at actual array
//sort by mergesort first
// then call compare function - this can be a procedure obviously
function Compare(var PRecords: array of PCustomRecord; iLength: int64): Integer;
var
i : Integer;
begin
for i := 0 to High(PRecords) do
begin
Result := AnsiCompareStr(PRecords[i]^.fsubline, PRecords[i+1]^.fsubline);
if Result=0 then
begin
if (PRecords[i].isrefrence = False) then
PRecords[i].isduplicate := True
else if (PRecords[i+1].isrefrence = False) then
PRecords[i+1].isduplicate := True;
end;
end;
end;
procedure MergeSort(var Vals:array of PCustomRecord;ACount:Integer);
var AVals:array of PCustomRecord;
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].fsubline) <= (Vals[j].fsubline) then
begin
Vals[k]:=AVals[i];
inc(i);inc(k);
end
else if (AVals[i].fsubline) > (Vals[j].fsubline) then
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);
end;
end;
begin
SetLength(AVals, ACount div 2 + 1);
PerformMergeSort(0,ACount - 1);
end;
これはすべて、1秒未満かかる小さなファイルでは非常に高速です。ただし、参照フラグではなく重複フラグを持つ配列内のアイテムの重複排除は非常に困難です。マージソートは安定したソートであるため、ブールフラグを使用して再試行しましたが、期待したものが得られませんでした。TStringlist以前のフラグが正しく設定されていて、完全に機能するかどうかを確認するためにを使用しました。時間は1秒から6秒に増加しました。なしisUniqueでフラグをマークする簡単な方法が必要であることを私は知っています。 TStringlist
これが私が試したことです：
function DeDupe(var PRecords: array of PCustomRecord; iLength: int64): Integer;
var
i : Integer;
begin
for i := 0 to High(PRecords) do
begin
if (PRecords[i]^.isrefrence = False) and (PRecords[i+1]^.isrefrence = false)then
begin
Result := AnsiCompareStr(PRecords[i]^.isduplicate, PRecords[i+1]^.isduplicate);
if Result = 0 then PRecords[i]^.isUnique := True;
end
else
begin
Continue;
end;
end;
end;
これはすべての値を取得するわけではなく、まだ多くの重複が見られるため、違いは見られませんでした。論理が間違っていると思います。
助けてくれたすべての偉大な魂に感謝します。配列に焦点を当てるために、を導出するTObject方法と使用する方法をすでに知っているかもしれないという利点を私に許可してください。TStringList
質問：上記のような関数または手順を実行して、繰り返されるアイテムに次のマークを付けるのを手伝ってください： isRefrence=falseおよびisDuplicate=True and unique
編集3：ブールフラグを使用することで重複を排除することができました。これは、アレイのサイズを変更せずにアレイを安定させるのに役立ちました。TList子孫やを使用するよりもはるかに高速だと思いますTStringList。配列などの基本的なコンテナの使用には、コーディングのしやすさに制限がありますが、非常に効率的であるため、私はそれを渡しません。ポインタで並べ替えが簡単になりました。通常の配列を使用しているのとまったく同じようにポインター配列を使用したときに、配列にポインターを設定した後、どのようにすればよいかわかりません。そして、私がそれをデレファレンスしたかどうかにかかわらず、それは違いがありませんでした。ポインタ配列を次のように設定します。
iLength := Length(Custom_array); //get length of actual array
SetLength(pcustomRecords, iLength); // make pointer array equal + 1
for M := Low(Custom_array) to High(Custom_array) do //set up pointers
begin
pcustomRecords[M] := @Custom_array[M];
end;
並べ替える実際のデータと並べ替えをできるだけ分けてみましたが、改善できると思います。
///////////////////////////////////////////////////////////////////
function Comparesubstring(Item1, Item2: PCustomRecord): Integer;
begin
Result := AnsiCompareStr(item1^.fsubline, item2^.fsubline);
end;
///////////////////////////////////////////////////////////////////
function CompareLine(Item1, Item2: PCustomRecord): Integer;
begin
Result := AnsiCompareStr(item1^.fLine, item2^.fLine);
end;
///////////////////////////////////////////////////////////////////
function Compare(var PRecords: array of PCustomRecord; iLength: int64): Integer;
var
M, i : Integer;
begin
M := Length(PRecords);
for i := 1 to M-1 do
begin
Result := Comparesubstring(PRecords[i-1], PRecords[i]);
if Result=0 then
begin
if (PRecords[i-1].isRefrence = False) then
PRecords[i-1].isduplicate := True
else if (PRecords[i].isRefrence = False) then
PRecords[i].isduplicate := True;
end;
end;
end;
///////////////////////////////////////////////////////////////////