أيها الرفاق ، مساء الخير! لقد قمت بتفكيك النسخة الأولى من كتاب "
C ++ 17 STL. Standard Template Library " من قبلنا وأنت تستمر في تحليل الكتاب الثاني الذي قررنا أخيرًا أن نقدم هنا وجهة نظر بديلة. مؤلف مقال اليوم هو Ivan Čukić ، الذي يمتلك أيضًا كتاب
البرمجة الوظيفية في C ++ ، والذي يتم إعداده للنشر في Manning Publishing House. نحن نقدم لتقييم أفكاره المتشككة والشفرة والحسابات
الديباجةأردت تسمية هذا المنشور "على شر خوارزميات STL" لاختبار مهاراتي الخاصة في إثارة النقرات. ولكن بعد ذلك قرر أنه من الأفضل كتابة مقالة للجمهور المستهدف ، وعدم كتابة مثل هذا المنشور حيث يجتمع أولئك الذين يرغبون في الجدل حول أطروحاتي الشنيعة.
وبالتالي ، يمكنني أن أفترض أنك مهتم بالخوارزميات وتعقيدها وتريد كتابة الشفرة الأكثر مثالية.
الخوارزمياتفي مجتمع C ++ الاحترافي الحديث ، غالبًا ما ينصح الناس: بجعل برنامجك أكثر أمانًا وأسرع وأكثر تعبيرًا ، وما إلى ذلك. - استخدم الخوارزميات من المكتبة القياسية. أحاول أيضًا تعميم هذه النصيحة في كتبي وخطابي وندواتي ... أينما يكون هناك جمهور مناسب.
بالطبع ، من الصحيح تمامًا أنه إذا تم رسمنا لكتابة حلقة
for لحل المشكلة المعروضة علينا ، فإننا بحاجة أولاً إلى التفكير فيما إذا كانت الخوارزميات الحالية للمكتبة القياسية (أو التعزيز) مناسبة لذلك ، ولا تعمل بشكل أعمى.
ما زلنا بحاجة إلى معرفة كيفية تنفيذ هذه الخوارزميات ، وما هي المتطلبات والضمانات المرتبطة بها ، وما هو التعقيد المكاني والزمني.
عادة ، إذا واجهنا مهمة تلبي تمامًا متطلبات خوارزمية STL ، ويمكن تطبيقها مباشرة ، فإن هذه الخوارزمية ستكون الحل الأكثر فعالية.
قد تنشأ مشكلة إذا كنا بحاجة إلى إعداد البيانات بطريقة ما قبل تطبيق الخوارزمية.
تقاطع المجموعاتلنفترض أننا نكتب أداة لمطوري C ++ تقدم نصائح حول استبدال خيارات الالتقاط الافتراضية (نتحدث عن
[=] و
[&] ) في تعبيرات لامدا ، وستعرض بوضوح قائمة المتغيرات الملتقطة.
std::partition(begin(elements), end(elements), [=] (auto element) { ^~~ - - , [threshold] return element > threshold; });
عند تحليل ملف ، نحتاج إلى مجموعة تقوم بتخزين المتغيرات من النطاق الحالي والمجال المجاور. بمجرد أن نواجه تعبير لامدا مع التقاط افتراضي ، سنحتاج إلى معرفة المتغيرات المستخدمة هناك.
ونتيجة لذلك ، لدينا مجموعتان: في الأولى ستكون هناك متغيرات من مناطق الرؤية المحيطة ، وفي الأخرى ستكون هناك متغيرات مستخدمة في نص تعبير لامدا.
يجب أن تكون قائمة خيارات الالتقاط التي سنقدمها للاستبدال تقاطع هاتين المجموعتين (يمكن أن تستخدم تعبيرات لامدا المتغيرات العالمية التي لا تحتاج إلى التقاطها ، ولن يتم استخدام جميع المتغيرات من النطاق المحيط في تعبير لامدا).
وإذا كنا بحاجة إلى التقاطع ، فيمكننا استخدام
std::set_intersection .
هذه الخوارزمية جميلة جدًا في بساطتها. يقبل مجموعتين مفروشتين ويديرهما في نفس الوقت من البداية إلى النهاية:
- إذا كان العنصر الحالي في المجموعة الأولى يساوي العنصر الحالي في المجموعة الثانية ، يتم إضافته إلى النتيجة ، والتي تنتقل الخوارزمية ببساطة إلى العنصر التالي في كلتا المجموعتين ؛
- إذا كان العنصر الفعلي في المجموعة الأولى أقل من العنصر الفعلي في المجموعة الثانية ، فإن الخوارزمية تتخطى ببساطة العنصر الحالي في المجموعة الأولى ؛
- إذا كان العنصر الفعلي في المجموعة الأولى أكبر من العنصر الفعلي في المجموعة الثانية ، فإن الخوارزمية تتخطى ببساطة العنصر الحالي في المجموعة الثانية ؛
يتم تخطي عنصر واحد على الأقل (من مجموعة الإدخال الأولى أو الثانية) في كل تكرار - وبالتالي ، سيكون تعقيد الخوارزمية خطيًا -
O(m + n) ، حيث
m هو عدد العناصر في المجموعة الأولى و
n هو عدد العناصر في المجموعة الثانية .
بسيطة وفعالة. طالما يتم فرز مجموعات الإدخال.
الفرزإليك المشكلة: ماذا لو لم يتم فرز المجموعات مسبقًا؟
في المثال السابق ، سيكون من الحكمة تخزين المتغيرات من مناطق الرؤية المحيطة في بنية تشبه المكدس ، حيث يمكن للمحلل ببساطة إضافة عناصر جديدة تدخل إلى نطاق جديد وحذف متغيرات النطاق الحالي بمجرد مغادرته.
وبالتالي ، لن يتم فرز المتغيرات حسب الاسم ، ولن نتمكن من استخدام
std::set_intersection مباشرة للعمليات عليها. وبالمثل ، إذا قمت بتتبع المتغيرات في نص تعبير لامدا ، فإننا على الأرجح لن نتمكن من حفظها في شكل مفروز.
نظرًا لأن
std::set_intersection يعمل فقط مع المجموعات المصنفة ، يحدث هذا المبدأ في العديد من المشاريع: أولاً نقوم بفرز المجموعات ، ثم نطلق على
std::set_intersection .
إذا نسينا أن فرز مجموعة من المتغيرات في مثالنا يقلل من قيمة الاستخدام الكامل للمكدس الذي حددناه ، فإن خوارزمية التقاطع للمجموعات غير المصنفة ستبدو كما يلي:
template <typename InputIt1, typename InputIt2, typename OutputIt> auto unordered_intersection_1(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt dest) { std::sort(first1, last1); std::sort(first2, last2); return std::set_intersection(first1, last1, first2, last2, dest); }
ما هو تعقيد هذه الخوارزمية بأكملها؟ يستغرق الفرز وقتًا شبه خطي ، لذا فإن التعقيد العام لهذا النهج هو
O(n log n + m log m + n + m) .
الفرز أصغرهل من الممكن الاستغناء عن الفرز؟
إذا لم يتم فرز كلتا المجموعتين ، فسيتعين علينا الانتقال إلى المجموعة الثانية لكل عنصر من العنصر الأول - لتحديد ما إذا كان سيتم تضمينه في مجموعة النتائج. على الرغم من أن هذا النهج شائع جدًا في المشاريع الحقيقية ، إلا أنه أسوأ من النهج السابق - تعقيده هو
O(n * m) .
بدلاً من فرز كل شيء على التوالي ، أو عدم فرز أي شيء ، تذكر Zen واختر المسار الثالث - نقوم بفرز مجموعة واحدة فقط.
إذا تم فرز مجموعة واحدة فقط ، فيمكننا التكرار عبر جميع القيم من المجموعة التي لم يتم فرزها واحدة تلو الأخرى ولكل قيمة تحقق ما إذا كانت في المجموعة التي تم فرزها. للقيام بذلك ، قم بتطبيق بحث ثنائي.
في هذه الحالة ، سيكون تعقيد الوقت
O(n log n) لفرز المجموعة الأولى و
O (m log n) للفرز والتدقيق. سيكون التعقيد الكلي
O((n + m) log n) .
إذا قررنا فرز المجموعة الثانية ، وليس المجموعة الأولى ، فإن التعقيد سيكون
O((n + m) log m) .
لتحقيق أقصى قدر من الكفاءة ، نقوم دائمًا بفرز المجموعة التي تحتوي على عناصر أقل ، بحيث يكون التعقيد النهائي للخوارزمية لدينا
((m + n) log (min(m, n)) .
سيبدو التنفيذ كما يلي:
template <typename InputIt1, typename InputIt2, typename OutputIt> auto unordered_intersection_2(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt dest) { const auto size1 = std::distance(first1, last1); const auto size2 = std::distance(first2, last2); if (size1 > size2) { unordered_intersection_2(first2, last2, first1, last1, dest); return; } std::sort(first1, last1); return std::copy_if(first2, last2, dest, [&] (auto&& value) { return std::binary_search(first1, last1, FWD(value)); }); }
في مثالنا مع قوائم الالتقاط في تعبيرات لامدا ، يتم عادةً فرز مجموعة المتغيرات الموجودة في تعبير لامدا ، حيث من المحتمل أن تكون أصغر من مجموعة جميع المتغيرات من جميع النطاقات المحيطة.
التجزئةالخيار الأخير هو بناء
std::unordered_set (تطبيق مجموعة غير مرتبة على أساس التجزئة) من مجموعة أصغر ، بدلاً من فرزها. في هذه الحالة ، سيبلغ متوسط تعقيد عمليات البحث
O(1) ، ولكن سيستغرق بعض الوقت لبناء
std::unordered_set . يمكن أن يتراوح تعقيد البناء من
O(n) إلى
O(n*n) ، وهذه مشكلة محتملة.
template <typename InputIt1, typename InputIt2, typename OutputIt> void unordered_intersection_3(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt dest) { const auto size1 = std::distance(first1, last1); const auto size2 = std::distance(first2, last2); if (size1 > size2) { unordered_intersection_3(first2, last2, first1, last1, dest); return; } std::unordered_set<int> test_set(first1, last1); return std::copy_if(first2, last2, dest, [&] (auto&& value) { return test_set.count(FWD(value)); }); }
يفوز نهج التجزئة بالكامل عندما تحتاج إلى حساب تقاطعات عدة مجموعات مع مجموعة صغيرة محددة مسبقًا. بمعنى ، لدينا المجموعة
A ، المجموعات
B₁ ،
B₂… ونريد أن نحسب
A ∩ B₁, A ∩ B₂…في هذه الحالة ، يمكنك تجاهل تعقيد بنية
std::unordered_set ، وسيكون تعقيد حساب كل تقاطع خطيًا -
O(m) ، حيث
m هو عدد العناصر في المجموعة الثانية.
تحكمبالطبع ، من المفيد دائمًا التحقق من تعقيد الخوارزمية ، ولكن في مثل هذه الحالات ، من الحكمة أيضًا التحقق من الأساليب المختلفة باستخدام نقاط التفتيش. خاصة عند الاختيار من بين الخيارين الأخيرين ، حيث نقارن عمليات البحث الثنائية والمجموعات المستندة إلى التجزئة.
أظهر أبسط اختبار أجريته أن الخيار الأول ، حيث يتعين عليك فرز المجموعتين ، هو دائمًا الأبطأ.
يتفوق ترتيب مجموعة أصغر على
std::unordered_set قليلاً ، ولكن ليس بشكل خاص.
كلا الطريقتين الثانية والثالثة أسرع قليلاً من الأولى في الحالة عندما يكون لكل من المجموعتين عدد متساوٍ من العناصر ، وأسرع بكثير (حتى ست مرات) عندما يكون عدد العناصر في مجموعة واحدة حوالي 1000 مرة أكثر من الثاني.