سؤال فضولي :ما هي الخوارزمية التي تنفذها STL set_intersect؟

Question

لقد أمضيت قدرًا كبيرًا من الوقت في البرمجة باستخدام خوارزمية التقاطع السريع المحددة من Baeza-Yates لأحد تطبيقاتي.على الرغم من أنني تفوقت بشكل طفيف على STL set_intersect، إلا أن حقيقة أنني طلبت فرز المجموعة الناتجة تمت إزالتها في أي وقت استفدته من تنفيذ الخوارزمية الخاصة بي بعد فرز المخرجات.بالنظر إلى أن STL set_intersect يؤدي هذا بشكل جيد، هل يمكن لأي شخص أن يوجهني إلى الخوارزمية التي تنفذها بالفعل؟أم أنها تنفذ نفس خوارزمية Baeza-Yates ولكن بطريقة أكثر كفاءة فقط؟

بايزا ييتس: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.91.7899&rep=rep1&type=pdf

Answer 1

على الأقل في التطبيقات التي نظرت إليها ، فإن التنفيذ مبسط إلى حد ما - شيء ما في هذا الترتيب العام:

template <class inIt, class outIt>
outIt set_intersection(inIt start1, inIt end1, inIt start2, inIt end2, outIt out) {
    while (start1 != end1 && start2 != end2) {
       if (*start1 < *start2)
           ++start1;
       else if (*start2 < *start1)
           ++start2;
       else {                 // equal elements.
           *out++ = *start1;
           ++start1;
           ++start2;
       }
    }
    return out;
}

بالطبع ، أنا فقط أكتب هذا الجزء العلوي من رأسي - ربما لن يتم تجميعه ، وبالتأكيد ليس صحيحًا من الناحية البيضاء (على سبيل المثال ، يجب أن تستخدم وظيفة المقارنة بدلاً من استخدام operator< مباشرة ، وينبغي أن يكون لديك معلمة قالب آخر للسماح بأن يكون START1/END1 نوعًا مختلفًا من Start2/End2).

من وجهة نظر الخوارزمية ، ومع ذلك ، أعتقد أن معظم التطبيقات الحقيقية كما هو مذكور أعلاه.

Answer 2

لا تتطلب STL أي خوارزمية معينة ، فهي تحدد فقط قيودًا على التعقيد الخوارزمي لبعض العمليات. نظرًا لأن كل شيء يعتمد على القالب ، يمكنك بسهولة عرض المصدر لتطبيقك الخاص لمعرفة كيفية عمله.

Answer 3

مثير للاهتمام.لذا، فإن عدد المقارنات في الخوارزمية الخاصة بك يتدرج خطيًا مع عدد العناصر في كلتا المجموعتين.تعمل خوارزمية Baeza-Yates على النحو التالي (لاحظ أنها تفترض فرز مجموعتي الإدخال):

1) ابحث عن متوسط ​​المجموعة A (A هي المجموعة الأصغر هنا) 2) ابحث عن متوسط ​​A في B.إذا وجدت ، أضف إلى النتيجة الأخرى ، معروفة رتبة الإدراج للمتوسط ​​في B.3) قم بتقسيم المجموعة (أ) حول وسيطها إلى جزأين، والمجموعة (ب) حول رتبة إدراجها إلى جزأين، وكرر الإجراء بشكل متكرر على كلا الجزأين.تعمل هذه الخطوة لأن جميع العناصر الأقل من الوسيط في A ستتقاطع فقط مع تلك العناصر قبل رتبة الإدراج للوسيط A في B.

نظرًا لأنه يمكنك استخدام البحث الثنائي لتحديد متوسط ​​A في B، فمن الواضح أن عدد المقارنات في هذه الخوارزمية أقل من تلك التي ذكرتها.في الواقع، في الحالة "الأفضل"، يكون عدد المقارنات هو O(log(m) * log(n)) حيث m وn هما حجما المجموعات، وفي أسوأ الحالات، يكون عدد المقارنات هو يا (م + ن).كيف بحق السماء أفسدت التنفيذ بهذا السوء؟:(