تسريع JavaScript باستخدام ضبط نوع البيانات

يقول مؤلف المادة ، التي نُنشر ترجمتها اليوم ، إنه واثق من أن العديد من مطوري JavaScript يستخدمون أنواع البيانات بشكل أساسي مثل Number ، String ، Object ، Array Boolean . في معظم الحالات ، هذا يكفي. ولكن إذا كنت بحاجة إلى جعل الشفرة سريعة وقابلة للتطوير قدر الإمكان ، فإن استخدام أنواع البيانات هذه ليس دائمًا مبررًا.



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

ما الفرق بين أنواع البيانات Array و Set؟

الميزة الرئيسية لنوع بيانات Array (سوف نسمي كائنات من هذا النوع "صفائف") هي أن الصفائف هي مجموعات مفهرسة من القيم. هذا يعني أنه يتم تخزين البيانات في المصفوفات باستخدام الفهارس.

 const arr = [A, B, C, D]; console.log(arr.indexOf(A)); // : 0 console.log(arr.indexOf(C)); // : 2 

على عكس المصفوفات ، فإن الكائنات من النوع Set (نسميها "المجموعات") هي مجموعات تحتوي على بيانات بتنسيق المفتاح / القيمة. بدلاً من استخدام الفهارس ، تخزن المجموعات العناصر باستخدام المفاتيح. يمكن فرز العناصر المخزنة في المجموعة بالترتيب الذي تم إضافتها فيه ، بينما لا يمكن للمجموعة تخزين نفس العناصر. بمعنى آخر ، يجب أن تكون جميع عناصر المجموعة فريدة من نوعها.

ما هي نقاط القوة الرئيسية للمجموعات؟

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

• البحث عن العناصر. أساليب الصفيف indexOf() includes() ، وتستخدم للبحث عن العناصر والتحقق مما إذا كان العنصر يحتوي على عنصر ، والعمل ببطء.
• إزالة العناصر. يمكن حذف عنصر في المجموعة بناءً على قيمته. في صفيف ، سيكون مكافئ مثل هذا الإجراء هو استخدام طريقة splice() ، استنادًا إلى فهرس العنصر. كما هو الحال مع البحث عن العناصر ، فإن إزالة العناصر باستخدام الفهارس عملية بطيئة.
• إدراج عنصر. يعد إضافة عنصر إلى المجموعة أسرع بكثير من استخدام طرق مثل push() و unshift() في صفيف.
• العمل مع قيمة NaN . لا يمكن استخدام طريقة indexOf() للعثور على قيمة NaN في صفيف ، بينما باستخدام طريقة الجمع has() يمكنك معرفة ما إذا كانت تحتوي على NaN .
• إزالة العناصر المكررة. Set الكائنات فقط تخزين القيم الفريدة. إذا كنت بحاجة إلى تجنب حفظ العناصر المكررة في بعض بنية البيانات ، فهذه ميزة كبيرة مقارنة بالصفائف. عند العمل مع المصفوفات لإزالة العناصر المكررة سيتعين عليك كتابة كود إضافي.

يمكن العثور هنا على قائمة كاملة بالطرق المدمجة للكائنات من النوع Set .

في الوقت تعقيد الخوارزميات

الطرق التي تستخدمها المصفوفات للبحث عن العناصر لها تعقيد زمني خطي - O (N). بمعنى آخر ، يكون وقت بحث العنصر متناسقًا مع حجم المصفوفة.

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

هنا يمكنك قراءة المزيد حول التعقيد الزمني للخوارزميات.

ما مدى سرعة المجموعات من الصفائف؟

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

preparation اختبار الإعداد

قبل إجراء أي اختبارات ، لنقم بإنشاء مصفوفة تحتوي على مليون عنصر ونفس المجموعة. من أجل البساطة ، سوف نستخدم دورة ، ستكون قيمة العداد الأولى 0 ، والأخيرة - 999999:

 let arr = [], set = new Set(), n = 1000000; for (let i = 0; i < n; i++) { arr.push(i); set.add(i); } 

No. الاختبار رقم 1: التحقق من وجود عنصر في صفيف وفي مجموعة

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

 let result; console.time('Array'); result = arr.indexOf(123123) !== -1; console.timeEnd('Array'); console.time('Set'); result = set.has(123123); console.timeEnd('Set'); 

فيما يلي نتائج هذا الاختبار:

 Array: 0.173ms Set: 0.023ms 

المجموعة أسرع بـ 7.54 مرة من المجموعة.

No. الاختبار رقم 2: إدخال عنصر

الآن دعونا نحاول إضافة عناصر إلى المصفوفات والمجموعات.

 console.time('Array'); arr.push(n); console.timeEnd('Array'); console.time('Set'); set.add(n); console.timeEnd('Set'); 

إليك ما حدث:

 Array: 0.018ms Set: 0.003ms 

المجموعة 6.73 مرات أسرع من الصفيف.

3 الاختبار 3: حذف عنصر

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

 const deleteFromArr = (arr, item) => { let index = arr.indexOf(item); return index !== -1 && arr.splice(index, 1); }; 

وهنا هو رمز الاختبار:

 console.time('Array'); deleteFromArr(arr, n); console.timeEnd('Array'); console.time('Set'); set.delete(n); console.timeEnd('Set'); 

والنتيجة هي ما يلي:

 Array: 1.122ms Set: 0.015ms 

في هذه الحالة ، كانت المجموعة أسرع بنسبة 74.13 مرة من المجموعة!

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

مثال رقم 1: إزالة القيم المكررة من صفيف

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

 const duplicateCollection = ['A', 'B', 'B', 'C', 'D', 'B', 'C']; //       let uniqueCollection = new Set(duplicateCollection); console.log(uniqueCollection) // : Set(4) {"A", "B", "C", "D"} //        let uniqueCollection = [...new Set(duplicateCollection)]; console.log(uniqueCollection) // : ["A", "B", "C", "D"] 

مثال 2: مقابلة مهمة في جوجل

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

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

▍ المهمة

إعطاء صفيف لم يتم فرزها من الأعداد الصحيحة وقيمة sum . اكتب دالة تُرجع بشكل true إذا ، نتيجة لإضافة أي عنصرين من هذه المجموعة ، نحصل على قيمة sum . في حالة عدم وجود مثل هذه العناصر في الصفيف ، يجب أن ترجع الدالة false .

اتضح ، على سبيل المثال ، أنه إذا تم إعطاؤنا صفيفًا [3, 5, 1, 4] وكانت قيمة sum تساوي 9 ، فيجب أن ترجع الدالة true ، لأن 4+5=9 .

▍Reshenie

يمكنك التعامل مع هذه المشكلة باستخدام الفكرة التالية: تحتاج إلى التكرار على المصفوفة ، وإنشاء بنية Set البيانات أثناء مرورها ، والتي سيتم فيها إضافة القيم التي تكمل القيم الموجودة في قيمة sum .

دعنا نحلل هذه الفكرة باستخدام مثال الصفيف أعلاه. عندما نلتقي 3 ، يمكننا إضافة الرقم 6 إلى المجموعة ، لأننا نعلم أننا بحاجة إلى إيجاد رقمين في المجموع 9 . ثم ، في كل مرة نصل فيها إلى قيمة جديدة من الصفيف ، يمكننا التحقق من المجموعة ومعرفة ما إذا كانت موجودة. عندما نلتقي بالرقم 5 ، سنضيف 4 إلى المجموعة. وعندما نصل في النهاية إلى الرقم 4 ، نجدها في المجموعة ويمكن أن نعود إلى true .

إليك ما قد يبدو عليه حل لهذه المشكلة:

 const findSum = (arr, val) => { let searchValues = new Set(); searchValues.add(val - arr[0]); for (let i = 1, length = arr.length; i < length; i++) {   let searchVal = val - arr[i];   if (searchValues.has(arr[i])) {     return true;   } else {     searchValues.add(searchVal);   } }; return false; }; 

وهنا حل أكثر إيجازاً:

 const findSum = (arr, sum) => arr.some((set => n => set.has(n) || !set.add(sum - n))(new Set)); 

نظرًا لأن التعقيد الزمني Set.prototype.has() هو O (1) ، فإن استخدام بنية Set البيانات لتخزين الأرقام التي تكمل الأرقام الموجودة في المصفوفة على قيمة معينة تسمح لك بإيجاد حل في الوقت الخطي (O (N)).

إذا كان الحل يعتمد على طريقة Array.prototype.indexOf() أو على طريقة Array.prototype.includes() ، فإن تعقيد الوقت لكل منها هو O (N) ، فإن التعقيد الزمني الكلي للخوارزمية سيكون O (N ² ). نتيجة لذلك ، سوف يصبح أبطأ بكثير.

النتائج

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

أعزائي القراء! كيف يمكنك تطبيق بنية Set البيانات في التعليمات البرمجية الخاصة بك؟