الخوارزميات في جافا سكريبت - شرح البحث الثنائي

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

ماذا تفعل الدورة؟

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

ستعرف:

  • بحث ثنائي
  • تدوين Big O
  • كود الأمر
  • العودية
  • عودة الذيل
  • تقسيم المصفوفة
  • عرض صفيف
  • تقسيم

يتم تدريس كل خوارزمية على ثلاث مراحل:

  • شرح تفصيلي: يقدم جوناثان الخوارزمية من الناحية المفاهيمية.
  • التنفيذ: نتسخ أيدينا من خلال صياغة إصداراتنا الخاصة من الخوارزمية.
  • الحل: يوضح لنا جوناثان تنفيذه للمقارنة.

المتطلبات الأساسية

ستحصل على أقصى استفادة من هذه الدورة التدريبية إذا كان لديك فهم جيد لـ Javascript وكنت تعمل بالفعل كمطور أو خريج برنامج Bootcamp.

إذا لم تكن هناك بعد ، تحقق من البرامج التعليمية المجانية الرائعة لـ Scrimba مقدمة إلى JavaScript ومقدمة إلى ES6 +.

مقدمة إلى المدرب

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

مع العملاء بما في ذلك شركات مثل NASA و HP ، فهو الشخص الوحيد الذي سيأخذك خلال رحلة التعلم. اذا هيا بنا نبدأ!

بحث ثنائي

الرسم البياني لعمليات البحث الكناس مقابل الفاصل.

انقر على الصورة للوصول إلى الدورة.

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

تدوين Big-O هو وسيلة لوصف أداء الخوارزمية الأسوأ. يقول A Big O لـ O (n) أنه إذا كان طول المصفوفة n من العناصر ، فإن وقت التشغيل سيكون متناسبًا مع n. بعبارة أخرى ، ستأخذ مصفوفة من سبعة إدخالات 7 عمليات بحث في أسوأ الحالات ، تمامًا كما ستتخذ مصفوفة من 7 ملايين إدخال 7 ملايين إدخال في أسوأ الحالات. يمكننا أيضًا أن نقول أن وقت تشغيل هذه الخوارزمية خطي ، كما هو موضح في الرسم البياني أعلاه.

البحث الثنائي هو أحد الاستراتيجيات المتعددة للإجابة على السؤال "أين يظهر هذا العنصر في القائمة؟"

عند الإجابة على السؤال ، هناك طريقتان رئيسيتان:

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

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

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

في حين أن نهج الكناس لديه وقت تشغيل خطي (انظر الرسم البياني أعلاه) و Big O لـ O (n) ، فإن أسلوب التقسيم له وقت تشغيل شبه خطي و Big O of O (log n).

صيغة الامر

في التحدي الأول ، شجعنا جوناثان على جعل أيدينا متسخة من خلال تنفيذ بحث ثنائي بأسلوب تقليدي ، أي باستخدام Big O of O (n) ، باستخدام قدر ثابت من الذاكرة والحلقات.

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

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

العودية

في هذا طاقم العمل ، ننظر إلى تحسين بحثنا الثنائي من خلال تنفيذ إصدار جديد مع بعض القيود. في حين أن الحل الذي نقدمه يجب أن يحتوي على Big O لـ O (n) ، يجب ألا يستخدم الحلقات ويجب أن يستخدم العودية. يجب تهيئة جميع المتغيرات باستخدام constعامل التشغيل حتى لا يتم تغييرها.

بدأنا جونانثان بنسخة هيكلية من الحل ثم يشجعنا على تجربة التحدي بمفردنا:

let binarySearchWithRecursion = (array, element, compare = defaultCompare) => { return -1; }; export default binarySearchWithRecursion; 

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

عودة الذيل

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

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

تقسيم الصفيف

If you completed the previous challenge, you may have felt that we're still passing a lot of extra information into our binary search via recursion. This cast looks at a way of cleaning that up called array splitting.

We can think of array splitting in terms of our phone book example from earlier - whenever we decide that half the phone book is irrelevant, we just tear it off and throw it away. Similarly, our next solution should disregard any parts of the array which don't include our desired entry.

To help us achieve this, Jonathan starts us off with some skeleton code:

let binarySearchWithArraySplitting = ( array, element, compare = defaultCompare ) => { return -1; }; 

Then, as usual, he gives us free rein to try to the solution for ourselves before walking us through his own implementation.

Although this is an elegant method of binary search, because it involves making a copy of part of the array, it no longer has a Big O of O(n) and has a higher memory usage and slower run time. Continue with the course to find out whether there is a way to regain a higher performance with a similar code solution...

Array View

In this cast, we look for ways of merging the higher performance of our previous solutions with the elegance of array splitting. To do this, we create an array-like object that responds to the same methods as an array. We'll then inject this object in place of the original array.

Jonathan gets us started by initializing a function ArrayView which returns an object that expects three arguments: array, start and end. When invoked, ArrayView should return an object with four methods, length, toArray, slice and get.

export let ArrayView = ( array, start = 0, end = array.length, ) => ({ length: end - start, toArray: () => array.slice(start, end), slice: () => , get: () => , }); let binarySearchWithArrayView = (array, ...args) => binarySearchWithArraySplitting(ArrayView(array), ...args) 

Our challenge is to implement the slice and get methods of ArrayView without making a copy of the original array. Click through to try it out and then view Jonathan's walkthrough.

Although this solution produces better, more readable code, it is longer than some of our previous solutions. Continue with the course to find out if we can retain the benefits of ArrayView while lifting even more of the logic out of binary search code...

Array Partition

In the final challenge cast of the course, Jonathan gives us a goal of extracting some of the cryptic bounce logic in our previous version into a data structure.

For this, we need a simple data structure which returns the middle, left or right part of an array. To start us off, Jonathan sets up a function ArrayPartition:

export let ArrayPartition = (array, pivot) => ({ left: () => array.slice(0, pivot), middle: () => array.get(pivot), right: () => array.slice(pivot + 1, array.length), }); 

Next, Jonathan sets up a new version of binary search called binarySearchWithPartition, which has a starting signature the same as binarySearchWithArraySplitting:

let binarySearchWithPartition = (array, element, compare = defaultCompare) => { if (array.length === 0) { return -1; } const middle = Math.floor(array.length / 2); const comparison = compare(element, array.get(middle)); if (comparison === 0) { return middle; } //bounce logic const [left, right] = comparison === -1 ? [0, middle - 1] : [middle + 1, array.length]; //end of bounce logic const subIndex = binarySearchWithArraySplitting( array.slice(left, right), element, compare ); return subIndex === -1 ? -1 : left + subIndex; }; let binarySearchWithPartitionAndView = (array, ...args) => binarySearchWithPartition(ArrayView(array), ...args); 

Our challenge now is to rewrite binarySearchWithPartition with none of the bounce logic highlighted above, instead of creating an array partition and making calls to its left, middle and right methods.

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

يتم إحتوائه

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

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

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

ترميز سعيد :)