تعرف على أساسيات الترميز: الاختلافات الرئيسية بين المجموعات والمصفوفات

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

للإجابة على هذا السؤال ، علينا أن نفهم الاختلافات الأساسية بين المجموعة والمصفوفة.

إذا كنت متعلمًا بصريًا وتفضل شرحًا بالفيديو ، فإليك مقطع فيديو مدته 3 دقائق يشرح الإجابة (وإن كان ذلك بعمق أقل).

كانت المصفوفات من أولى هياكل البيانات التي تعلمت كيفية استخدامها.

إنها ليست فقط بنية بيانات أساسية تُستخدم في كل تطبيق ترميز تقريبًا ، ولكن يسهل فهمها أيضًا.

لم أتمكن من التعرف على ابن عم المصفوفة الغريب ، ولكن السحري ، إلا بعد فترة طويلة في مسيرتي المهنية البرمجية:

مجموعة.

المجموعات تشبه المصفوفات ... إلا أنها ليست كذلك.

دعنا نذكر أنفسنا بسرعة بكيفية عمل المصفوفة

المصفوفات:

  • أمرت
  • لها مؤشرات تبدأ من 0
  • يمكن أن تحتوي على عناصر مكررة
  • احصل على وقت بحث O (n) عندما تبحث عن عنصر

ومع ذلك ، تتصرف المجموعات بشكل مختلف قليلاً

مجموعات:

  • و غير مرتبة (في جميع اللغات تقريبا)
  • لديها مؤشرات مجزأة
  • لا يمكن أن تحتوي على عناصر مكررة
  • لديهم O (1) بحث الوقت عند البحث عن عنصر

دعنا نلقي نظرة أكثر تعمقًا.

1. يعين إدراج عن طريق التجزئة

يتم تخزين العناصر في المجموعة بشكل مختلف تمامًا عن تلك الموجودة في المصفوفة.

الطريقة التي تخزن بها المجموعة عناصرها هي عن طريق التجزئة.

لنفترض أنك تريد تخزين الحرف "أ" في مجموعة ومصفوفة.

سوف تجد المصفوفة ببساطة الفهرس المتاح التالي ، ما لم يتم تحديد خلاف ذلك ، وتضع العنصر في هذا الفهرس.

مع التجزئة ، تبدو الأشياء مختلفة بعض الشيء.

كيف يعمل Hashing

التجزئة هي عملية أخذ المدخلات (س) ، وتشويهها بوظيفة تجزئة محددة (ح) ، والحصول على الناتج النهائي (ص).

أساسا ح (س) = (ص)

يبدو قليلا مربكا ، أليس كذلك؟

لا تقلق! هذا يجب أن يوضح الأمور.

مثال سهل لوظيفة التجزئة (h) يمكن أن يكون إلحاق "asdf" بنهاية الإدخال (x).

إذا كانت (x) تساوي "A" وإلحاق "asdf" يساوي (h) ، فسيكون الناتج (y) كما يلي:

"A" + "asdf" ← "Aasdf"

لذا فإن "Aasdf" ستكون (y).

إذن ، كيف تستخدم المجموعة التجزئة؟

تستخدم المجموعة التجزئة لتحديد مكان تخزين الإدخال (x).

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

هذا هو سبب عدم ترتيب المجموعات في معظم اللغات.

فهرسة المصفوفة سهلة ، من 0 إلى n ، لذا يمكنك بسهولة تذكر ما سيأتي بعد ذلك.

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

2. لا يمكن أن تحتوي المجموعات على تكرارات

صحيح!

يمكن أن تحتوي المجموعة على عناصر فريدة فقط.

على عكس ما يبدو عليه الأمر ، يمكن أن يكون هذا مفيدًا للغاية في الواقع في الكثير من المواقف ، بما في ذلك أسئلة المقابلة من Google.

لماذا تفعل ذلك ، تسأل؟

حسنًا ، بسبب التجزئة!

نظرًا لأن وظيفة التجزئة (h) الخاصة بي ستظل متسقة أثناء تشغيل البرنامج ، فإن إدخال نفس (x) سيمنحك دائمًا نفس (y).

هذا يعني أنه إذا حاولت إدخال "A" ثانٍ ، فإن وظيفة التجزئة الخاصة بي ستخرج نفس العنوان مثل "A" الأول ، وستقوم ببساطة بالكتابة فوقه!

باستخدام مصفوفة ، فإنها ستلحق ببساطة "A" الثاني بالفهرس المتاح التالي.

3. المجموعات لها O (1) وقت البحث

لنفترض أن لديك مصفوفة من عناصر n ، حيث يمثل n عددًا كبيرًا ، وأردت معرفة ما إذا كان الحرف "A" موجودًا في تلك المصفوفة.

حسنًا ، أسوأ سيناريو ، "أ" غير موجود.

ومعرفة ذلك، سيكون لديك لتكرار خلال كل ن تلك العناصر!

هذا يعطي المصفوفة تعقيدًا زمنيًا لـ O (n) عندما يتعلق الأمر بالبحث عن عنصر.

يمكننا توفير الكثير من الوقت مع مجموعة

إذا أردنا معرفة ما إذا كان العنصر موجودًا أم لا في مجموعتنا ، فكل ما علينا فعله هو تجزئة هذا العنصر والتحقق من الفهرس!

تذكر: الفهرس الذي يتم تخزين العنصر فيه متصل بالعنصر نفسه.

لذلك ، إذا أردنا معرفة ما إذا كان الحرف "A" موجودًا في مجموعتنا أم لا ، فسيتعين علينا فقط تجزئته (+ "asdf") والتحقق من هذا الفهرس!

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

هذا يعني أن المجموعة لديها تعقيد زمني لـ O (1) عندما يتعلق الأمر بالبحث عن عنصر ... وهو تحسن كبير!

هل يمكنك التفكير في أي مواقف يكون فيها هذا مفيدًا؟

إذا لم تستطع ، فتحقق من سؤال المقابلة في Google حيث تصنع المجموعة كل الفرق!

شكرا للقراءة!

ملاحظة - لمزيد من البرامج التعليمية حول هياكل البيانات والخوارزميات ، والتحضير للمقابلة ، راجع www.TheForge.ca!

نحن نساعد الطلاب والخريجين الجدد في الحصول على وظيفة برنامج أحلامهم!