إذا كان لدي مجموعة من المفاتيح M ، ومجموعة من الأهداف n ، كيف يمكنني التحقق من وجود m [i] في n قبل البحث عنها؟

Question

كما يقول العنوان ، أحاول العثور على عناصر M الموجودة في مجموعة كبيرة ثابتة N. زمن.

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

فما هي الحيل التي يمكنني استخدامها لخفض فرصة البحث في M دون داع؟

هذا سؤال مستقل للغة في الغالب ، ولكن فقط لأكون مكتملًا قدر الإمكان ، أستخدم C ++.

Answer 1

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

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

Answer 2

يمكنك بناء علامة تجزئة مع قيم n كمفاتيح.

ثم تحاول الوصول إلى علامة التجزئة [M [i]] ، إذا أعادت قيمة ، فهذا هو O (1) (تجاهل التصادم.)

Answer 3

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

يحتوي كتاب CLR على الخوارزميات على فصل على هذا ، ويحتوي صفحة Wiki أعلاه على روابط قد تجدها مفيدة. قد يكون الأمر معقدًا للغاية وقد تتعرض لضغوط شديدة للعثور على تطبيق مفيد.. ينظر الى gperf للتنفيذ.

يمكنك دائمًا استخدام جدول التجزئة المتاح بشكل شائع مع O (1) المتوقع.

أفترض أنك تقوم بتخزين بعض المعلومات الإضافية التي تريد استردادها مع العلم أنها موجودة؟ كيف تقوم بتخزين هؤلاء؟

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