نموّ الترميز الكبير: ما تكلّفه فعلًا كل فئة تعقيد

البيانات الخاصة بك

خوارزميتان وجهًا لوجه

الثابت هو كل ما يرميه الترميز: تخصيص الذاكرة، وإخفاقات المخبأ، والعمل داخل كل خطوة. أعطِ إحدى الخوارزميتين ثابتًا أثقل وانظر أين يكفّ عن الأهمية.

هذه الصفحة لا تقرأ حلقتك. فتخمين التعقيد من الشيفرة تخمينٌ يرتدي ثوب القياس: قد تخرج الحلقة مبكرًا، وقد يخفي نداء واحد بداخلها الكلفة الحقيقية، والعَوْد نادرًا ما يُقرأ كما يفعل. أنت تختار الفئة، وما تحسبه الصفحة بعد ذلك دقيق.

نتائج

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

كل فئة عند هذا الحجم

العمود الأخير هو ما يستحق التحديق، لأنه العمود الذي لا يحمله أحد في رأسه. العمل الخطي يتضاعف. والتربيعي يصير أربعة أضعاف. أما الأسّي فيُربَّع: فمع ألف عنصر في اللعب أصلًا، تضاعفُ الدخل يضرب الكلفة في اثنين أُس ألف، وهو عدد من ثلاثمئة ورقمين.

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

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

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