ملخص للمشاكل التي واجهتها في الفرز الأمامي

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

فرز الواجهة الأمامية

سيناريو الفرز الأمامي

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

تخيل سيناريو: عند استخدام تطبيق الطعام ، هل غالبًا ما تقوم بتبديل طريقة الفرز ، وفرزها حسب السعر ، ثم الفرز حسب التصنيف.

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

فرز خوارزمية

أشعر أنه لا توجد حاجة لتقديم هذا. كخوارزمية أساسية في علوم الكمبيوتر ، سيتم نسخ الوصف مباشرة من Wikipedia .

هذه الفقرة موجودة هنا بحتة لغرض ورث الأول (الرجل) والثاني (SHU).

فرز JavaScript

نظرًا لأننا نتحدث عن الفرز الأمامي ، فسوف نفكر بشكل طبيعي في مجموعة الواجهة الأصلية لـ Array.prototype.sort .

لقد كانت هذه الواجهة موجودة منذ ECMAScript 1st Edition . دعونا نرى كيف يبدو وصفه في أحدث المواصفات.

Array.prototype.sort المواصفات

Array.prototype.sort(compareFn)

نسخة الكود كما يلي:

يتم فرز عناصر هذه الصفيف. هذا النوع ليس مستقرًا (أي العناصر التي تقارن مساواة لا تظل بالضرورة في ترتيبها الأصلي). إذا لم تكن مقارنة غير محددة ، فيجب أن تكون دالة تقبل وسيطتين X و Y وإرجاع قيمة سالبة إذا كانت x <y أو صفر إذا كانت x = y أو قيمة موجبة إذا كانت x> y.

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

في هذا السياق ، يعتمد الفرز الأمامي فعليًا على التنفيذ المحدد لكل متصفح. لذا ، كيف تنفذ المتصفحات السائدة بالفرز؟ بعد ذلك ، نقارن بإيجاز Chrome و Firefox و Microsoft Edge على التوالي.

التنفيذ في الكروم

محرك JavaScript Chrome هو V8. نظرًا لأنه مفتوح المصدر ، يمكنك إلقاء نظرة على الشفرة المصدرية مباشرة.

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

التنفيذ في Firefox

ليس من الممكن تحديد خوارزمية فرز الصفيف التي سيكون محرك JavaScript من Firefox على وشك استخدامها. [3]

وفقًا للمعلومات الحالية ، تندمج Spidermoney Parering الفرز داخليًا.

التنفيذ في Microsoft Edge

تم فتح الجزء الأساسي من الكود لمحرك JavaScript Chakra من Microsoft Edge من الحصول على GitHub في أوائل عام 2016.

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

مشاكل فرز مجموعة JavaScript

كما نعلم جميعًا ، فإن الفرز السريع هو خوارزمية فرز غير مستقرة ، في حين أن فرز الدمج هو خوارزمية فرز مستقرة. نظرًا للاختلافات في اختيار الخوارزمية للمحركات المختلفة ، يعتمد الواجهة الأمامية على رمز JavaScript الذي تم تنفيذه بواسطة واجهة Array.Prototype.

يجب أن يتم تشغيل الاختلافات في ثبات الفرز بواسطة سيناريوهات محددة قبل وجود مشكلة ؛ في كثير من الحالات ، لن يكون للفرز غير المستقر أي تأثير.

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

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

على سبيل المثال:

القواعد الفائزة النهائية لنظام مزاد ترخيص السيارات في مدينة معينة هي:

1. الفرز حسب السعر في الاتجاه المعاكس ؛

2. سيتم فرز نفس السعر بشكل إيجابي وفقًا لأمر تقديم العطاءات (أي وقت تقديم السعر).

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

استكشف الاختلافات

قبل العثور على حل ، من الضروري استكشاف أسباب المشكلة.

لماذا يستخدم Chrome الفرز السريع

في الواقع ، كان هذا الوضع موجودًا منذ البداية.

تم إصدار Chrome Beta في 2 سبتمبر 2008. ومع ذلك ، بعد فترة وجيزة من صدوره ، قدم بعض المطورين #90 ملاحظات الأخطاء إلى مجموعة تطوير الكروم. تطبيق فرز الصفيف لـ V8 ليس مستقرًا.

تمتد مناقشة قضية الأخطاء هذه كثيرًا. حتى 10 نوفمبر 2015 ، لا يزال المطورين يعلقون على تنفيذ فرز الصفيف في V8.

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

والاستنتاج النهائي لـ ES-Discuss

نسخة الكود كما يلي:

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

/أندرياس

كما هو موضح في مواصفات ECMASCRIPT 2015 التي تم ذكرها سابقًا في هذه المقالة.

خصائص العصر

IMHO ، تم الإبلاغ عن هذه المشكلة في بداية إطلاق Chrome ، والتي قد لها خصائصها الخاصة للعصر.

كما ذكر أعلاه ، تم إصدار الإصدار الأول من Chrome في سبتمبر 2008. وفقًا لإحصائيات StatCounter ، كان المتصفحان الذي يحمل أعلى حصة في السوق خلال تلك الفترة هو IE (فقط IE6 و IE7 في ذلك الوقت) و Firefox ، حيث بلغت حصة السوق 67.16 ٪ و 25.77 ٪ على التوالي. بمعنى آخر ، تتجاوز حصة السوق المشتركة للمتصفحين 90 ٪.

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

الامتثال للمواصفات

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

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

اعتبارات الأداء

بالإضافة إلى ذلك ، يعتقدون أن اعتبارًا مهمًا في تصميم V8 هو أداء المحرك.

يؤدي الفرز السريع أداءً بشكل عام أفضل من فرز الدمج:

كفاءة الحوسبة الأعلى. الفرز السريع أسرع في بيئة تنفيذ الكمبيوتر الفعلية من خوارزميات الفرز الأخرى مع نفس التعقيد في الوقت (في حالة عدم ضرب أسوأ مجموعة)

تكاليف المساحة المنخفضة. السابق ليس له سوى تعقيد الفضاء O (n) ، مقارنةً بتعقيد الفضاء الأخير O (n) ، يكون استهلاك الذاكرة أقل أثناء وقت التشغيل.

تحسين أداء V8 في خوارزمية فرز الصفيف

نظرًا لأن V8 مهتم جدًا بأداء المحرك ، فماذا يفعل في فرز الصفيف؟

من خلال قراءة رمز المصدر ، ما زلت أتعلم بعض المعرفة الأساسية.

مختلط الإدراج نوع

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

يتمثل التنفيذ الحالي لـ V8 في تعيين عتبة واستخدام فرز إدراج للصفائف الصغيرة من 10 أو أقل في الطبقة الأدنى.

وفقًا لتعليقات التعليمات البرمجية والأوصاف في ويكيبيديا ، على الرغم من أن متوسط ​​التعقيد الزمني لفرز الإدراج هو O (n²) أسوأ من الفرز السريع O (NN). ومع ذلك ، في البيئة الجارية ، تكون كفاءة استخدام فرز المصفوفات الصغيرة أكثر كفاءة من الفرز السريع ، لذلك لن يتم توسيعها هنا.

مثال رمز V8

 var QuickSort = function QuickSort (a ، from ، إلى) {... if (إلى - من <= 10) {insertionSort (a ، من ، إلى) ؛ يعود؛ } ......} ......} ؛

ثلاثة أرقام في

كما هو معروف ، فإن كعب أخيل الفرز السريع هو أن الخوارزمية تتدهور في مجموعة أسوأ مجموعة.

يتمثل جوهر خوارزمية الفرز السريع في اختيار محور ، وتحلل الصفيف الذي تمت مقارنته وتبادله في منطقتين وفقًا للمرجعية للروح اللاحقة. تخيل لو أن العنصر الأول أو الأخير ، بالنسبة إلى صفيف تم طلبه بالفعل ، يتم تحديد العنصر الأول أو الأخير دائمًا في كل مرة يتم فيها تحديد العنصر المرجعي ، فستكون هناك مساحة أرقام فارغة في كل مرة ، وسيصل العدد العودية من الطبقات إلى N ، مما سيؤدي في النهاية إلى تدهور تعقيد وقت الخوارزمية إلى O (n²). لذلك ، فإن اختيار المحور مهم للغاية.

يستخدم V8 تحسين median-of-three : بالإضافة إلى العنصرين في البداية والنهاية ، يتم تحديد عنصر آخر للمشاركة في منافسة العنصر القياسي.

استراتيجية اختيار العنصر الثالث تقريبًا:

عندما يكون طول الصفيف أقل من أو يساوي 1000 ، حدد العنصر في الموضع نصف كعنصر الهدف.

عندما يتجاوز طول المصفوفة 1000 ، حدد عنصرًا واحدًا على مسافة 200-215 (غير ثابت ، ويتغير مع طول المصفوفة) لتحديد مجموعة من عناصر المرشح أولاً. ثم فرز عناصر المرشح في هذه الدفعة ، واستخدم القيمة المتوسطة الناتجة كعنصر مستهدف.

أخيرًا ، خذ القيمة المتوسطة للعناصر الثلاثة كمحور.

مثال رمز V8

 var getthirdIndex = function (a ، from ، to) {var t_array = new internalArray () ؛ // استخدم كل من "من" و "إلى" لتحديد المرشحين المحوريين. VAR ZENMENT = 200 + ((إلى - من) و 15) ؛ var J = 0 ؛ من += 1 ؛ إلى -= 1 ؛ لـ (var i = from ؛ i <to ؛ i += styrement) {t_array [j] = [i ، a [i]] ؛ J ++ ؛ } t_array.sort (function (a ، b) {return comparefn (a [1] ، b [1]) ؛}) ؛ var third_index = t_array [t_array.length >> 1] [0] ؛ return Third_index ؛} ؛ var QuickSort = function QuickSort (a ، from ، إلى) {...... بينما (صحيح) {...... if (to - from> 1000) {third_index = getThirdIndex (a ، from ، from) ؛ } آخر {third_index = من + ((إلى - من) >> 1) ؛ }} ......} ؛

فرز في المكان

أثناء مراجعة خوارزمية الفرز السريع ، رأيت العديد من الأمثلة على التنفيذ باستخدام JavaScript على الإنترنت.

لكنني وجدت أن جزءًا كبيرًا من تطبيق الكود هو كما يلي

 var QuickSort = function (arr) {if (arr.length <= 1) {return arr ؛ } var pivotindex = math.floor (arr.length / 2) ؛ var pivot = arr.splice (pivotindex ، 1) [0] ؛ var left = [] ؛ var right = [] ؛ لـ (var i = 0 ؛ i <arr.length ؛ i ++) {if (arr [i] <pivot) {left.push (arr [i]) ؛ } آخر {right.push (arr [i]) ؛ }} إرجاع Quicksort (يسار) .concat ([pivot] ، Quicksort (يمين)) ؛} ؛

المشكلة الرئيسية في الكود أعلاه هي: استخدام منطقتي الرقمين اليسرى واليمين لتخزين العودية الفرعية العودية ، لذلك يتطلب مساحة تخزين إضافية من O (n). هذا فرق كبير مقارنة مع متوسط ​​التعقيد المكاني النظري O (N).

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

يتمثل التنفيذ في رمز المصدر V8 في تبادل العناصر على الصفيف الأصلي.

لماذا يستخدم Firefox فرز دمج

هناك أيضا قصة وراءها.

في الواقع ، عندما تم إصدار Firefox في البداية ، لم تستخدم خوارزمية فرز مستقرة لتنفيذ فرز الصفيف ، وهو موثق جيدًا.

كانت خوارزمية فرز الصفيف التي تم تنفيذها بواسطة الإصدار الأصلي من Firefox (Firebird) فرز الكومة ، وهي أيضًا خوارزمية فرز غير مستقرة. لذلك ، قدم شخص ما في وقت لاحق خطأ.

أجرى فريق Mozilla Development سلسلة من المناقشات حول هذه القضية.

من عملية المناقشة ، يمكننا رسم بعض النقاط

1. منافس موزيلا خلال نفس الفترة كان IE6. من الإحصاءات المذكورة أعلاه ، يمكننا أن نرى أن IE6 مستقر في الفرز.

2. Brendan Eich ، والد JavaScript ، يعتقد أن الاستقرار جيد

3. يستخدم Firefox الفرز السريع قبل فرز الكومة

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

حل الاختلافات في فرز الاستقرار

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

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

حل

في الواقع ، فكرة حل هذه المشكلة بسيطة نسبيا.

يختار المتصفح خوارزميات فرز مختلفة لاعتبارات مختلفة. قد يميل البعض إلى متابعة الأداء الشديد ، بينما يميل البعض الآخر إلى توفير تجربة تنمية جيدة ، ولكن هناك قواعد متابعة.

انطلاقًا من الموقف المعروف الحالي ، يمكن لجميع المتصفحات الرئيسية (بما في ذلك IE6 ، 7 ، 8) تعداد تنفيذ خوارزميات فرز الصفيف بشكل أساسي:

1. دمج الفرز/تيمسورت

2. نوع سريع

لذلك ، يمكننا فقط تحويل الفرز السريع إلى فرز مستقر؟

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

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

تستخدم طريقة المقارنة المخصصة CompareFN دائمًا الترتيب الطبيعي كبعد الحكم الثاني عندما يكون الحكم المسبق متساويًا.

عند مواجهة التطبيقات مثل دمج الفرز ، نظرًا لأن الخوارزمية نفسها مستقرة ، فإن مقارنة الترتيب الطبيعي الإضافي لن تغير نتيجة الفرز ، وبالتالي فإن توافق المخطط أفضل.

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

مثال رمز المخطط

 "استخدام صارم" ؛ const index = symbol ('index') ؛ function getComparer (قارن) {return function (يسار ، يمين) {let result = compare (يسار ، يمين) ؛ نتيجة العودة === 0؟ اليسار [الفهرس] - اليمين [الفهرس]: النتيجة ؛ } ؛} function sort (Array ، Compare) {Array = Array.Map ((item ، index) => {if (typeof item === 'Object') {item [index] = index ؛} return item ؛}) ؛ return array.sort (getComparer (مقارنة)) ؛}

ما سبق هو مجرد مثال تعديل خوارزمية بسيط يرضي الفرز المستقر.

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

علامة

1. الواجهة الأمامية هي الآن مفهوم واسع نسبيا. يشير الواجهة الأمامية في هذه المقالة بشكل أساسي إلى البيئة باستخدام المتصفح باعتباره شركة النقل وجافا سكريبت كلغة برمجة.

2. هذه المقالة لا تنوي إشراك الخوارزمية ككل. أرغب في استخدام خوارزميات الفرز الشائعة كنقطة الدخول.

3. عند تأكيد الخوارزمية التي تنفذها فرز مجموعة Firefox ، تم العثور على خطأ مرتبط بالفرز في Spidermoney. بشكل عام ، أثناء المناقشة ، اقترح شخص ما استخدام خوارزمية Timsort بأداء أفضل في الحالات القصوى لاستبدال فرز الدمج ، لكن مهندسي Mozilla قالوا إنه نظرًا لمشكلة ترخيص ترخيص خوارزمية Timsort ، لا توجد طريقة لاستخدام خوارزمية Mozilla في برنامج Mozilla وانتظر الرد اللاحق للطرف الآخر.

لخص

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