配列をソートする最良の方法
https://stackoverflow.com/questions/41733
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
レコードの配列があり、レコード内のフィールドの 1 つに基づいて並べ替えたいとします。これを達成するための最善の方法は何でしょうか?
TExample = record
SortOrder : integer;
SomethingElse : string;
end;
var SomeVar : array of TExample;
解決
配列の要素へのポインタを追加できます。 TList, 、その後電話します TList.Sort 比較関数を使用して、最後に新しい配列を作成し、TList から値を目的の順序でコピーします。
ただし、次のバージョン D2009 を使用している場合は、配列を並べ替えることができる新しいコレクション ライブラリがあります。オプションが必要です IComparer<TExample> カスタム並べ替え順序の実装。ここでは、特定のケースで動作しています。
TArray.Sort<TExample>(SomeVar , TDelegatedComparer<TExample>.Construct(
function(const Left, Right: TExample): Integer
begin
Result := TComparer<Integer>.Default.Compare(Left.SortOrder, Right.SortOrder);
end));
他のヒント
(これは 1 年後のことですが、それでも役立つ内容です。)
整数値をパディングするという Skamradt の提案は、文字列比較を使用して並べ替えることを前提としています。これでは遅いでしょう。挿入ごとに format() を呼び出すと、さらに遅くなります。代わりに、整数比較を実行したいとします。
まずレコード タイプから始めます。
TExample = record
SortOrder : integer;
SomethingElse : string;
end;
レコードがどのように保存されたか、または並べ替えられた後にどのようにアクセスしたいかについては述べていませんでした。したがって、それらを動的配列に配置すると仮定します。
var MyDA Array of TExample;
...
SetLength(MyDA,NewSize); //allocate memory for the dynamic array
for i:=0 to NewSize-1 do begin //fill the array with records
MyDA[i].SortOrder := SomeInteger;
MyDA[i].SomethingElse := SomeString;
end;
次に、この配列を整数値 SortOrder で並べ替えます。取得したいものが TStringList である場合 (つまり ts.Find メソッドを使用できる)、各文字列をリストに追加し、SortOrder をポインターとして追加する必要があります。次に、ポインターでソートします。
var tsExamples: TStringList; //declare it somewhere (global or local)
...
tsExamples := tStringList.create; //allocate it somewhere (and free it later!)
...
tsExamples.Clear; //now let's use it
tsExamples.sorted := False; //don't want to sort after every add
tsExamples.Capacity := High(MyDA)+1 //don't want to increase size with every add
//an empty dynamic array has High() = -1
for i:=0 to High(MyDA) do begin
tsExamples.AddObject(MyDA[i].SomethingElse,TObject(MyDA[i].SortOrder));
end;
Integer SortOrder を TStringList.Object プロパティに格納されている TObject ポインターにキャストするトリックに注意してください。(これは、Integer と Pointer が同じサイズであるという事実に依存します。) TObject ポインターを比較する関数をどこかで定義する必要があります。
function CompareObjects(ts:tStringList; Item1,Item2: integer): Integer;
var i,j: integer;
begin
Result := integer(ts.Objects[i]) - integer(ts.Objects[j];
end;
これで、.Sort (文字列値に基づいて並べ替えられます) の代わりに .CustomSort を呼び出すことで、.Object の tsList を並べ替えることができます。
tsExample.CustomSort(@CompareObjects); //Sort the list
TStringList がソートされたので、0 から .Count-1 まで反復処理して、ソートされた順序で文字列を読み取ることができます。
ただし、TStringList が必要ではなく、ソートされた順序の配列だけが必要だとします。または、レコードにはこの例の 1 つの文字列だけではなく多くのデータが含まれており、並べ替え順序はより複雑になります。すべての文字列を追加する手順を省略して、配列インデックスを TList の項目として追加するだけです。TStringList の代わりに TList を使用することを除いて、上記のすべてを同じ方法で実行します。
var Mlist: TList; //a list of Pointers
...
for i:=0 to High(MyDA) do
Mlist.add(Pointer(i)); //cast the array index as a Pointer
Mlist.Sort(@CompareRecords); //using the compare function below
function CompareRecords(Item1, Item2: Integer): Integer;
var i,j: integer;
begin
i := integer(item1); //recover the index into MyDA
j := integer(item2); // and use it to access any field
Result := SomeFunctionOf(MyDA[i].SomeField) - SomeFunctionOf(MyDA[j].SomeField);
end;
Mlist がソートされたので、それをルックアップ テーブルとして使用して、ソートされた順序で配列にアクセスします。
for i:=0 to Mlist.Count-1 do begin
Something := MyDA[integer(Mlist[i])].SomeField;
end;
TList を反復処理すると、ソートされた順序で配列インデックスが返されます。TList はそれらをポインタであると考えるため、それらを整数にキャストし直す必要があるだけです。
私はこの方法を好みますが、配列要素のインデックスの代わりにアドレスを追加することで、TList 内の配列要素への実際のポインターを配置することもできます。次に、それらを使用するには、それらを TExample レコードへのポインターとしてキャストします。これは、バリー・ケリー氏とクールマジック氏が回答の中で述べたことです。
文字列でソートする必要がある場合は、sorted を使用してください TStringList そして、レコードを追加します TString.AddObject(string, Pointer(int_val)).
ただし、整数フィールドと文字列で並べ替える必要がある場合は、使用します TObjectList すべてのレコードを追加した後、呼び出します TObjectList.Sort 必要なソート関数をパラメータとして使用します。
これはすべて、並べ替えるレコードの数によって異なります。数百未満のソートのみを行う場合は、他のソート方法で問題なく機能しますが、それ以上のソートを行う場合は、信頼できる古い Turbo Power をよく見てください。 システムツール プロジェクト。ソースには非常に優れた並べ替えアルゴリズムが含まれています。数百万のレコードを効率的に分類するという非常に優れた仕事をします。
レコードのリストを並べ替える tStringList メソッドを使用する場合は、リストに整数を挿入する前に、整数が右に埋められていることを確認してください。使用できます format('%.10d',[rec.sortorder]) たとえば、10 桁に右揃えにします。
クイックソート アルゴリズムは、高速な並べ替えが必要な場合によく使用されます。Delphi は、たとえば List.Sort にこれを使用しています (または使用していました)。Delphi List はあらゆるものを並べ替えるために使用できますが、構造上のポインタの配列のように見えることになっている重量級のコンテナです。このスレッドの Guy Gordon のようなトリック (ポインターの代わりにインデックスなどを置く、または 32 ビット未満の場合は値を直接置く) を使用したとしても、それは重量級です。リストなどを作成する必要があります...
したがって、構造体の配列を簡単かつ高速にソートする代替手段は、 qsort C ランタイム関数 msvcrt.dllから。
これは良いかもしれない宣言です (警告:コードは Windows でのみ移植可能です)。
type TComparatorFunction = function(lpItem1: Pointer; lpItem2: Pointer): Integer; cdecl;
procedure qsort(base: Pointer; num: Cardinal; size: Cardinal; lpComparatorFunction: TComparatorFunction) cdecl; external 'msvcrt.dll';
完全な例 ここ.
レコードが大きい場合、レコードの配列を直接ソートすると速度が低下する可能性があることに注意してください。その場合、レコードへのポインターの配列をソートすると、より高速になる可能性があります (リストのアプローチに似た方法です)。
配列の場合はどちらかを使用します quicksort あるいはおそらく heapsort, を使用するように比較を変更するだけです。 TExample.SortOrder, 、スワップ部分は引き続き配列に作用し、ポインターをスワップします。配列が非常に大きく、挿入と削除が頻繁に行われる場合は、リンク リスト構造が必要になる場合があります。
C ベースのルーチン。ここにはいくつかありますhttp://www.yendor.com/programming/sort/
別のサイトですが、パスカルのソースがありますhttp://www.dcc.uchile.cl/~rbaeza/handbook/sort_a.html
によって提案されるソート アルゴリズムの 1 つを使用します。 ウィキペディア. 。Swap 関数は、配列要素と同じ型の一時変数を使用して配列要素を交換する必要があります。同じ SortOrder 整数値を持つエントリを最初の順序で維持したい場合は、安定した並べ替えを使用してください。
TStringList 効率的なソート方法を持っています。
並べ替えが必要な場合は、 TStringList オブジェクト Sorted プロパティを True に設定します。
注記：速度を上げるには、ソートされていない状態でオブジェクトを追加します。 TStringList 最後にプロパティを True に変更します。
注記：整数フィールドによる並べ替えの場合は、文字列に変換します。
注記：重複した値がある場合、このメソッドは無効になります。
よろしく。
Delphi XE2 以降を使用している場合は、次のことを試すことができます。
var
someVar: array of TExample;
list: TList<TExample>;
sortedVar: array of TExample;
begin
list := TList<TExample>.Create(someVar);
try
list.Sort;
sortedVar := list.ToArray;
finally
list.Free;
end;
end;
並べ替えフィールドが文字列の場合に正しく動作する非常に単純な例を作成しました。
Type
THuman = Class
Public
Name: String;
Age: Byte;
Constructor Create(Name: String; Age: Integer);
End;
Constructor THuman.Create(Name: String; Age: Integer);
Begin
Self.Name:= Name;
Self.Age:= Age;
End;
Procedure Test();
Var
Human: THuman;
Humans: Array Of THuman;
List: TStringList;
Begin
SetLength(Humans, 3);
Humans[0]:= THuman.Create('David', 41);
Humans[1]:= THuman.Create('Brian', 50);
Humans[2]:= THuman.Create('Alex', 20);
List:= TStringList.Create;
List.AddObject(Humans[0].Name, TObject(Humans[0]));
List.AddObject(Humans[1].Name, TObject(Humans[1]));
List.AddObject(Humans[2].Name, TObject(Humans[2]));
List.Sort;
Human:= THuman(List.Objects[0]);
Showmessage('The first person on the list is the human ' + Human.name + '!');
List.Free;
End;
