بنية البيانات للتصفية السريعة (Delphi)؟

Question

أقوم بتحسين جزء من تطبيق Delphi حيث يتم تصفية قوائم الكائنات بشكل متكرر باستخدام معايير مختلفة. يتم الاحتفاظ بالكائنات في TObjectList الهياكل ومن الشائع اختيار نسبة مئوية صغيرة جدًا (على سبيل المثال 1 ٪) من المجموعة بأكملها مع كل مرشح. يمكن أن يكون العدد الإجمالي للكائنات في نطاق 100K وخلال الحسابات لا تتغير المجموعة الرئيسية. على الرغم من أن المرشحات يتم تطبيقها على عدد قليل من الخصائص ، إلا أنه لا يمكن فرز القوائم بطريقة من شأنها تحسين جميع المعايير المحتملة.

أبحث عن اقتراحات حول كيفية تنظيم الكائنات (هياكل البيانات) أو خوارزمية يمكن استخدامها للتعامل مع هذه المشكلة. شكرًا لك!

مثال مرشح:

  ((Object.A between 5 and 15) AND
  (Object.B < 20) AND
  (Object.C(AParam) > 0)) OR
  (Object.IsRoot(...))

Answer 1

الفكرة رقم 1

قم بتشغيل الكود الخاص بك في profiler. اكتشف ما إذا كانت هناك أي نقاط بطيئة.

الفكرة رقم 2

ربما يمكنك الاستفادة من تأثيرات ذاكرة التخزين المؤقت عن طريق تخزين كائناتك بالتتابع في الذاكرة. (أفترض أنك تمشي قائمتك بالتتابع من البداية إلى النهاية.)

قد تكون إحدى الطرق للقيام بذلك هي استخدام مجموعة من السجلات بدلاً من قائمة الكائنات. إذا كان ذلك ممكنًا في قضيتك. تذكر أن السجلات في Delphi 2006 يمكن أن تحتوي على طرق (ولكن ليس افتراضية).

قد تكون فكرة أخرى هي كتابة مخصص الفصل الخاص بك. لم أحاول ذلك أبدًا ، ولكن هذا مقال وجدته. ربما حاول المشي الكائنات باستخدام مؤشر بدلاً من استخدام ToBectList.

Answer 2

يمكنك استخدام أ قائمة فرز باستخدام الحقل ، الذي يقيد البحث/التصفية على الأكثر ، ثم قم بإجراء أ بحث ثنائي للحصول على الفهرس/فهارس هذه المعايير.

في إشارة إلى مثالك أعلاه: إنشاء A-قائمة ، ابحث عن فهارس 5 و 15 وهكذا ستحصل على قائمة أصغر (الكثير) (جميع الفهارس بين الاثنين) ، حيث يتعين عليك التحقق من الحقول الأخرى (B, C و IsRoot).

Delphi (2009+) تنفيذ قائمة مرتبة: Dehl.Collections.SortedList

Answer 3

أعلم أنك لا تستخدم Tiopf ، ولكن هناك الكثير لنتعلمه من الكود المصدري لهذا المشروع. نظرًا لأنك ربما ستحلق على الكائنات التي تمت تصفيتها ، فلماذا لا تنشئ مرشحًا مرشحًا؟

هذه الوحدة بداية جيدة ، لكنني أعتقد أنه من الأسهل تنزيل المصدر الكامل وتصفح الملفات: http://tiopf.svn.sourceforge.net/viewvc/tiopf/tiopf2/trunk/core/tifilteredobjectlist.pas؟revision=1469&view=markup

ربما يستخدم هذا الحل الكثير من RTTI: فقط قم بإنشاء قائمة مع مرشحات (أسماء الخصائص والقيم) والحلقة على الكائنات. سيوفر لك أقصى قدر من المرونة ولكن على حساب بعض السرعة. إذا كنت بحاجة إلى سرعة أعتقد أن الحل الذي توفره Ulrichb سيكون أفضل.

Answer 4

إذا كانت كمية الكائنات صغيرة ، فربما لا يهم مدى كفاءة البحث ، على الرغم من أن التخزين المؤقت للنتيجة قد يساعد في كثير من الأحيان.

إذا كانت كمية الكائنات كبيرة ، فسأفكر في استخدام قاعدة بيانات في الذاكرة واستخدام SQL لإجراء الاستعلام. يمكن لقاعدة البيانات بعد ذلك استخدام الفهارس للعثور على الأشياء في أسرع وقت ممكن ، وتنقل العبء إلى أداة مثبتة. أنا شخصياً أستخدم DBISAM أو ElevatedB ، لكن الآخرين سوف يفعلون قواعد بيانات في الذاكرة أيضًا. باستخدام أداة قاعدة بيانات حقيقية ، يمكنك نقل البيانات إلى القرص بسهولة إذا أصبحت كبيرة حقًا.

Answer 5

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

Answer 6

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

أنا متأكد من أنك لا ترغب في تنفيذ مُحسّن استعلام كامل ، لذا إليك بعض النصائح حول كيفية جعل استفساراتك سريعة بما فيه الكفاية:

(1) حدد بعض الحقول التي يتم استخدامها بشكل متكرر في استفساراتك وإعداد فهارس عليها. تحتاج هذه الحقول إلى توفير انتقائية جيدة: لا تقم بفهرسة على قيمة "منطقية" ، فأنت فقط ستفقد هياكل البحث الثنائية المعقدة عندما تكون سريعًا (أو أسرع) تنظر إلى القائمة بأكملها!

(2) لكل استعلام معين حدد واحد فهرس واحد لتصفية البيانات مسبقًا وتطبيق جميع المرشحات الأخرى واحدًا تلو الآخر (بدون تحسين).

في مثالك: قم بإنشاء فهارس على الحقول "A" و "B". يبدو أن "C" وظيفة بحيث يكون من المستحيل الفهرس. يبدو أن "iSroot" يعيد منطقية ، وهذا لا يستحق الفهرسة.

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