أفضل طريقة لفرز مجموعة

Question

لنفترض أن لدي مجموعة من السجلات التي أريد فرزها بناءً على أحد الحقول الموجودة في السجل.ما هي أفضل طريقة لتحقيق ذلك؟

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

var SomeVar : array of TExample;

Answer 1

يمكنك إضافة مؤشرات إلى عناصر المصفوفة إلى ملف TList, ، ثم اتصل TList.Sort باستخدام وظيفة المقارنة، وأخيرًا أنشئ مصفوفة جديدة وانسخ القيم من قائمة TL بالترتيب المطلوب.

ومع ذلك، إذا كنت تستخدم الإصدار التالي، 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));

Answer 2

(أعلم أن هذا قد مر عام، ولكن لا تزال هناك أشياء مفيدة.)

يفترض اقتراح 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 إلى مؤشر TObject، والذي يتم تخزينه في الخاصية TStringList.Object.(يعتمد هذا على حقيقة أن العدد الصحيح والمؤشر لهما نفس الحجم.) في مكان ما يجب علينا تحديد دالة لمقارنة مؤشرات TObject:

function CompareObjects(ts:tStringList; Item1,Item2: integer): Integer;
var i,j: integer;
begin
  Result := integer(ts.Objects[i]) - integer(ts.Objects[j];
end;

الآن، يمكننا فرز قائمة tsList على .Object عن طريق استدعاء .CustomSort بدلاً من .Sort (الذي سيتم فرزه بناءً على قيمة السلسلة).

tsExample.CustomSort(@CompareObjects);     //Sort the list

تم الآن فرز TStringList، لذا يمكنك التكرار عليها من 0 إلى .Count-1 وقراءة السلاسل بالترتيب المفرز.

لكن لنفترض أنك لا تريد TStringList، بل مجرد مصفوفة مرتبة.أو تحتوي السجلات على بيانات أكثر من مجرد سلسلة واحدة في هذا المثال، ويكون ترتيب الفرز أكثر تعقيدًا.يمكنك تخطي خطوة إضافة كل سلسلة، وإضافة فهرس المصفوفة كعناصر في قائمة TL.افعل كل شيء أعلاه بنفس الطريقة، باستثناء استخدام قائمة TL بدلاً من قائمة TStringList:

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، نستعيد فهارس المصفوفة بترتيب فرزها.نحتاج فقط إلى إعادتها إلى الأعداد الصحيحة، نظرًا لأن قائمة TL تعتقد أنها مؤشرات.

أحب القيام بذلك بهذه الطريقة، ولكن يمكنك أيضًا وضع مؤشرات حقيقية لعناصر المصفوفة في قائمة TL عن طريق إضافة عنوان عنصر المصفوفة بدلاً من فهرسه.ثم لاستخدامها، يمكنك إرسالها كمؤشرات إلى سجلات TExample.هذا ما قاله Barry Kelly وCoolMagic في إجاباتهما.

Answer 3

إذا كانت حاجتك مرتبة حسب السلسلة، فاستخدم فرزها TStringList وإضافة سجل بواسطة TString.AddObject(string, Pointer(int_val)).

ولكن إذا لزم الأمر، قم بالفرز حسب الحقل الصحيح والسلسلة - استخدم TObjectList وبعد إضافة جميع سجلات المكالمة TObjectList.Sort مع الوظائف المصنفة الضرورية كمعلمة.

Answer 4

كل هذا يعتمد على عدد السجلات التي تقوم بفرزها.إذا كنت تقوم بفرز أقل من بضع مئات فقط، فإن طرق الفرز الأخرى تعمل بشكل جيد، وإذا كنت ستقوم بفرز عدد أكبر، فقم بإلقاء نظرة فاحصة على Turbo Power القديم الموثوق به أدوات النظام مشروع.هناك خوارزمية فرز جيدة جدًا مضمنة في المصدر.واحد يقوم بعمل جيد جدًا في فرز ملايين السجلات بطريقة فعالة.

إذا كنت ستستخدم أسلوب tStringList لفرز قائمة السجلات، فتأكد من وضع العدد الصحيح على اليمين قبل إدراجه في القائمة.يمكنك استخدام ال التنسيق('%.10d',[rec.sortorder]) لمحاذاة اليمين إلى 10 أرقام على سبيل المثال.

Answer 5

غالبًا ما يتم استخدام خوارزمية الفرز السريع عندما يكون الفرز السريع مطلوبًا.دلفي (أو كانت) تستخدمه في List.Sort على سبيل المثال.يمكن استخدام قائمة دلفي لفرز أي شيء، ولكنها حاوية ثقيلة الوزن، من المفترض أن تبدو مثل مجموعة من المؤشرات على الهياكل.إنها ثقيلة الوزن حتى لو استخدمنا حيلًا مثل 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';

مثال كامل هنا.

لاحظ أن الفرز المباشر لمصفوفة السجلات قد يكون بطيئًا إذا كانت السجلات كبيرة.في هذه الحالة، يمكن أن يكون فرز مصفوفة من المؤشرات إلى السجلات أسرع (بطريقة ما مثل طريقة القائمة).

Answer 6

مع مجموعة، سأستخدم إما quicksort أو ربما heapsort, ، وقم فقط بتغيير المقارنة للاستخدام TExample.SortOrder, ، سيظل جزء المبادلة يعمل فقط على مؤشرات المصفوفة والمبادلة.إذا كان المصفوفة كبيرة جدًا، فقد تحتاج إلى بنية قائمة مرتبطة إذا كان هناك الكثير من عمليات الإدراج والحذف.

الإجراءات القائمة على لغة C، هناك العديد منها هناhttp://www.yendor.com/programming/sort/

موقع آخر، ولكن لديه مصدر باسكالhttp://www.dcc.uchile.cl/~rbaeza/handbook/sort_a.html

Answer 7

استخدم إحدى الخوارزميات التي يقترحها النوع ويكيبيديا.يجب أن تقوم وظيفة Swap بتبديل عناصر المصفوفة باستخدام متغير مؤقت من نفس نوع عناصر المصفوفة.استخدم الفرز المستقر إذا كنت تريد أن تظل الإدخالات التي لها نفس قيمة العدد الصحيح SortOrder بالترتيب الذي كانت عليه في المقام الأول.

Answer 8

TStringList لديك طريقة فرز فعالة.
إذا كنت تريد الفرز، استخدم أ TStringList كائن مع Sorted الملكية إلى صحيح.

ملحوظة:لمزيد من السرعة، أضف كائنات في حالة غير مصنفة TStringList وفي النهاية قم بتغيير الخاصية إلى True.
ملحوظة:للفرز حسب حقل عدد صحيح، قم بالتحويل إلى سلسلة.
ملحوظة:إذا كانت هناك قيم مكررة، فهذه الطريقة ليست صالحة.

يعتبر.

Answer 9

إذا كان لديك دلفي 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;

Answer 10

لقد قمت بإنشاء مثال بسيط جدًا يعمل بشكل صحيح إذا كان حقل الفرز عبارة عن سلسلة.

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;