أسرع طريقة للعثور على كائنات من مجموعة مطابقة لشرط عضو السلسلة

Question

لنفترض أن لدي مجموعة (سواء كانت مصفوفة أو قائمة عامة أو أي شيء آخر الأسرع حل لهذه المشكلة) من فئة معينة، دعنا نسميها ClassFoo:

class ClassFoo
{
    public string word;
    public float score;
    //... etc ...
} 

لنفترض أنه سيكون هناك حوالي 50.000 عنصر في المجموعة، كلها في الذاكرة.الآن أريد الحصول بأسرع ما يمكن على جميع المثيلات في المجموعة التي تلتزم بشرط على عضو الشريط الخاص بها، على سبيل المثال مثل هذا:

List<ClassFoo> result = new List<ClassFoo>();
foreach (ClassFoo cf in collection)
{
    if (cf.word.StartsWith(query) || cf.word.EndsWith(query))
        result.Add(cf);
}

كيف يمكنني الحصول على النتائج في أسرع وقت ممكن؟هل يجب أن أفكر في بعض تقنيات الفهرسة المتقدمة وهياكل البيانات؟

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

Answer 1

مع القيد المتمثل في أن الشرط الشرطي يمكن أن يكون "أي شيء"، فأنت مقيد بمسح القائمة بأكملها وتطبيق الشرط.

إذا كانت هناك قيود على جملة الشرط، فيمكنك النظر في تنظيم البيانات للتعامل بشكل أكثر كفاءة مع الاستعلامات.

على سبيل المثال، نموذج التعليمات البرمجية مع القاموس "byFirstLetter" لا يساعد على الإطلاق في الاستعلام "endsWith".

لذلك، يتعلق الأمر حقًا بالاستعلامات التي تريد إجراؤها مقابل تلك البيانات.

في قواعد البيانات، تقع هذه المشكلة على عاتق "مُحسِّن الاستعلام".في قاعدة البيانات النموذجية، إذا كان لديك قاعدة بيانات لا تحتوي على فهارس، فمن الواضح أن كل استعلام سيكون عبارة عن فحص جدول.أثناء قيامك بإضافة فهارس إلى الجدول، يمكن للمُحسِّن استخدام تلك البيانات لإنشاء خطط استعلام أكثر تعقيدًا للوصول إلى البيانات بشكل أفضل.هذه هي في الأساس المشكلة التي تصفها.

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

يحرر, ، بناء على التعليق

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

إذا كانت البيانات ديناميكية، فقم بتخزينها في شجرة متوازنة، وابحث عنها.يعد هذا بحثًا ثنائيًا بشكل فعال، ويتيح لك الاستمرار في إضافة البيانات بشكل عشوائي.

أي شيء آخر هو بعض التخصص في هذه المفاهيم.

Answer 2

var Answers = myList.Where(item => item.bar.StartsWith(query) || item.bar.EndsWith(query));

هذا هو الأسهل في رأيي، وينبغي تنفيذه بسرعة.

Answer 3

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

يمكنك التوازي إذا كان لديك نوى أو آلات متعددة.

Answer 4

أنا لا أستخدم Java حاليًا، ولكنني أفكر في الأمور التالية.

كيف تقوم بإنشاء قائمتك؟ربما يمكنك إنشاء الطلب بالفعل بطريقة تقلل من وقت المقارنة.

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

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

إن تحسين استعلام المقارنة الخاص بك عن طريق معرفة المقارنة التي من المرجح أن تكون صحيحة والقيام بذلك أولاً يمكن أن يساعد أيضًا.أي:إذا كان بشكل عام 10% من الوقت الذي يبدأ فيه عضو المجموعة بالاستعلام الخاص بك، و30% من الوقت الذي ينتهي فيه العضو بالاستعلام، فقد ترغب في إجراء المقارنة النهائية أولاً.

Answer 5

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

بشكل عام، إذا كنت تعرف بنية الاستعلام مسبقًا، فيمكنك فرز مجموعتك (أو إنشاء عدة فهارس مرتبة لمجموعتك إذا كانت هناك عبارات متعددة) بشكل مناسب؛إذا لم تقم بذلك، فلن تتمكن من القيام بعمل أفضل من البحث الخطي.

Answer 6

إذا كان الأمر يتعلق بملء القائمة مرة واحدة ثم إجراء العديد من عمليات البحث (الآلاف أو أكثر)، فيمكنك إنشاء نوع من قاموس البحث الذي يبدأ بالخرائط/ينتهي بقيم لقيمها الفعلية.قد يكون ذلك بحثًا سريعًا، ولكنه سيستخدم ذاكرة أكبر بكثير.إذا لم تكن تقوم بالعديد من عمليات البحث أو تعلم أنك ستعيد ملء القائمة على الأقل بشكل شبه متكرر، فسأختار استعلام LINQ الذي اقترحته CQ.

Answer 7

يمكنك إنشاء نوع من الفهرس وقد يصبح أسرع.

يمكننا بناء فهرس مثل هذا:

Dictionary<char, List<ClassFoo>> indexByFirstLetter;
foreach (var cf in collection) {
  indexByFirstLetter[cf.bar[0]] = indexByFirstLetter[cf.bar[0]] ?? new List<ClassFoo>();
  indexByFirstLetter[cf.bar[0]].Add(cf);
  indexByFirstLetter[cf.bar[cf.bar.length - 1]] = indexByFirstLetter[cf.bar[cf.bar.Length - 1]] ?? new List<ClassFoo>();
  indexByFirstLetter[cf.bar[cf.bar.Length - 1]].Add(cf);
}

ثم استخدمه مثل هذا:

foreach (ClasssFoo cf in indexByFirstLetter[query[0]]) {
  if (cf.bar.StartsWith(query) || cf.bar.EndsWith(query))
    result.Add(cf);
}

ربما لا نحتاج الآن إلى تكرار عدد كبير من ClassFoo كما في مثالك، ولكن مرة أخرى يتعين علينا الحفاظ على تحديث الفهرس.ليس هناك ما يضمن أنه أسرع، لكنه بالتأكيد أكثر تعقيدا.

Answer 8

يعتمد على.هل سيتم دائمًا تحميل جميع العناصر الخاصة بك في الذاكرة؟هل لديك حد محدود للكائنات التي يمكن تحميلها؟هل يجب على استفساراتك أن تأخذ في الاعتبار الكائنات التي لم يتم تحميلها بعد؟

إذا أصبحت المجموعة كبيرة، سأستخدم بالتأكيد فهرسًا.

في الواقع، إذا كان من الممكن أن تنمو المجموعة إلى حجم عشوائي ولم تكن متأكدًا من قدرتك على احتوائها كلها في الذاكرة، فسأبحث في ORM، أو قاعدة بيانات في الذاكرة، أو قاعدة بيانات أخرى مضمنة.يتبادر إلى الذهن XPO من DevExpress لـ ORM أو SQLite.Net لقاعدة البيانات في الذاكرة.

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

Answer 9

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