33

レコード内のフィールドの 1 つに基づいて並べ替えたいレコードの配列があるとします。これを達成するための最良の方法は何ですか？

TExample = record
  SortOrder : integer;
  SomethingElse : string;
end;

var SomeVar : array of TExample;
4

10 に答える 10

37

配列の要素へのポインターを に追加し、比較関数で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));
于 2008-09-03T15:36:17.073 に答える
12

（私はこれが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;

TStringList.Objectプロパティに格納されているTObjectポインタに整数SortOrderをキャストするトリックに注意してください。（これは、整数とポインターが同じサイズであるという事実に依存します。）どこかで、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のItemsとして追加するだけです。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レコードへのポインターとしてそれらをキャストします。これは、バリーケリーとCoolMagicが彼らの答えで行うと言ったことです。

于 2009-09-04T22:53:31.143 に答える
3

文字列でソートする必要がある場合は、 sorted を使用しTStringListてレコードを追加しTString.AddObject(string, Pointer(int_val))ます。

ただし、整数フィールドと文字列で並べ替える必要がある場合はTObjectList、すべてのレコードを追加した後TObjectList.Sort、必要な並べ替え関数をパラメーターとして使用して呼び出します。

于 2008-10-02T10:21:55.100 に答える
2

これはすべて、並べ替えるレコードの数によって異なります。数百未満しかソートしない場合は、他のソート方法で問題なく機能します。それ以上ソートする場合は、古い信頼できる Turbo Power SysToolsプロジェクトをよく見てください。ソースには非常に優れたソート アルゴリズムが含まれています。効率的な方法で何百万ものレコードをソートする非常に優れた仕事をするもの.

レコードのリストをソートする tStringList メソッドを使用する場合は、リストに挿入する前に、整数が右側にパディングされていることを確認してください。たとえば、format('%.10d',[rec.sortorder])を使用して 10 桁に右揃えできます。

于 2008-10-02T15:05:27.663 に答える
1

クイックソート アルゴリズムは、高速なソートが必要な場合によく使用されます。たとえば、DelphiはList.Sortにそれを使用しています（または使用していました）。Delphi List はあらゆるソートに使用できますが、構造上のポインタの配列のように見える重いコンテナです。このスレッドで Guy Gordon のようなトリックを使用しても (ポインターの代わりにインデックスまたは何かを配置するか、32 ビットより小さい場合は直接値を配置する)、リストを作成する必要があります...

したがって、構造体の配列を簡単かつ迅速にソートする代わりに、 msvcrt.dll のqsort C ランタイム関数を使用することもできます。

これは良い宣言です (警告: コードは Windows でのみ移植可能です)。

type TComparatorFunction = function(lpItem1: Pointer; lpItem2: Pointer): Integer; cdecl;
procedure qsort(base: Pointer; num: Cardinal; size: Cardinal; lpComparatorFunction: TComparatorFunction) cdecl; external 'msvcrt.dll';

ここに完全な例があります。

レコードが大きい場合、レコードの配列を直接ソートすると遅くなる可能性があることに注意してください。その場合、レコードへのポインターの配列をソートする方が高速になる可能性があります（どういうわけかリストアプローチに似ています）。

于 2012-01-25T10:34:56.883 に答える
1

配列では、どちらかquicksortまたはおそらくheapsortを使用し、比較を use に変更するだけTExample.SortOrderで、スワップ部分は配列とスワップポインターに作用するだけです。配列が非常に大きく、挿入と削除が多い場合は、リンクされたリスト構造が必要になる場合があります。

C ベースのルーチン、ここにいくつかあり ます http://www.yendor.com/programming/sort/

別のサイトですが、パスカルのソースがあり ます http://www.dcc.uchile.cl/~rbaeza/handbook/sort_a.html

于 2008-09-08T13:26:03.910 に答える
0

ウィキペディアが提案する種類のアルゴリズムの1つを使用してください。Swap関数は、配列要素と同じタイプの一時変数を使用して配列要素を交換する必要があります。同じSortOrder整数値を持つエントリを最初の順序のままにしたい場合は、安定ソートを使用します。

于 2008-09-03T14:35:21.683 に答える
0

TStringList効率的なソート方法があります。
Sort が必要な場合は、プロパティを True に設定 したTStringListオブジェクトを使用します。Sorted

注: 速度を上げるには、not Sorted にオブジェクトを追加TStringListし、最後にプロパティを True に変更します。
注: 整数フィールドでソートするには、文字列に変換します。
注: 重複する値がある場合、このメソッドは有効ではありません。

よろしく。

于 2008-10-02T11:52:49.093 に答える