نظرة عامة حول كيفية عمل المصفوفات

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

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

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

وقت الترجيع

يتم تخزين الكائنات والوظائف وكل ما نعرفه عن أجهزة الكمبيوتر بشكل أساسي في وحدات بت وبايت في الكمبيوتر.

في لغات مثل Java و C ، عليك أن تعلن بوضوح عن حجم المصفوفة مسبقًا.

اصمد ولكن روبي لا تفعل ذلك؟

في Ruby ، ​​نستخدم Arrayهياكل البيانات الخطية. يمكننا إضافة أشياء لا نهائية على ما يبدو إلى مصفوفة روبي ولن يكون الأمر مهمًا بقدر ما نشعر بالقلق.

هذا رائع أليس كذلك ؟! هذا يعني أن المصفوفات كبيرة بشكل لا نهائي ، أليس كذلك؟ وتلك روبي هي اللغة المتفوقة؟ محظوظا لنا!

لكن ليس بهذه السرعة. * تنبثق فقاعتك *

لا توجد مصفوفات ذات حجم لانهائي ؛ ما تراه في روبي هو ما نسميه بالمصفوفة الديناميكية ، وهو يأتي بتكلفة.

لفهم ماهية المصفوفات الديناميكية ، دعنا أولاً نلقي نظرة على كيفية تمثيل المصفوفات في الذاكرة. نظرًا لأن MRI Ruby (مترجم Matz 'Ruby) يجمع وصولاً إلى كود C ، سننظر في كيفية تمثيل المصفوفات في C.

سي جي هو تصديق

سنغوص في القليل من التعليمات البرمجية C لمساعدتنا بشكل أفضل قليلاً ... :)

في لغات المستوى الأدنى مثل C ، عليك أن تتعامل مع المؤشرات وتخصيص الذاكرة بنفسك. حتى إذا لم تكن قد تعاملت مع C من قبل (d isclaimer - ولا أنا كذلك ) ، فقد يكون لديك C-een أحد أكثر الأمثلة شهرة (في) أدناه:

دعنا نكسر هذا الجزء من الكود:

  • malloc ليس له أي معنى سحري وراءه ، فهو يمثل حرفياً memory allocation
  • malloc إرجاع مؤشر
  • malloc يأخذ في حجة ، وهو حجم الذاكرة التي تريد أن يخصصها لك البرنامج.
  • 100 * sizeof(int) يخبر البرنامج أننا نريد تخزين 100 عدد صحيح ، لذا خصص لنا 100 * حجم ما سيشغله كل عدد صحيح.
  • ptr/ يخزن المؤشر إشارة إلى عنوان الذاكرة.

تيمي يخزن الأمتعة!

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

  • يذهب تيمي إلى المنضدة ، ويخبر البواب أن لديه قطعتان من الأمتعة ، حول هذا الحجم الكبير ، وأنه يود تخزينهما في المخزن.
  • يلقي الكونسيرج نظرة على غرفة المتجر ويذهب "نعم ، لدينا بعض المساحة في B4المنطقة المخصصة وسوف نخصص تلك المساحة لتخزين أمتعتك".
  • يسلمون تيمي بطاقة صغيرة مع المنطقة المخصصة عليها ، B4في حالتنا.
  • تيمي سعيد ، يتجول ويفعل أي شيء ، وعندما يريد استلام حقائبه ، يعود إلى المنضدة ويظهر لهم بطاقة الاستلام الخاصة به . " هل لديك C-een أمتعتي؟ "

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

من خلال إظهار بطاقة العداد ( البرنامج ) تيمي ( المؤشر / عنوان الذاكرة ) ، يستطيع تيمي استرداد أمتعته ( البيانات ). علاوة؟ لأنهم يعرفون بالضبط مكان تخزين حقيبة تيمي - B4وهذا يعني أنه يمكنهم استرداد جميع أمتعة تيمي بسرعة نسبيًا!

أيضًا ، هل تساءلت يومًا عن سبب وصولك إلى عناصر في مصفوفة مع فهرس ، مثل ذلك؟

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

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

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

ما هي المصفوفات الديناميكية إذن؟

لقد أخبرتكم قليلاً عن كيفية تمثيل المصفوفات في الذاكرة ، ولكن حان الوقت الآن للتحدث عن بعض السلبيات.

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

بالعودة إلى تشبيه الأمتعة لدينا: فكر في الأمر كما لو كان تيمي سيخزن قطعتين من الأمتعة ، B4ويمكنه تخزين قطعتين من الأمتعة بالضبط ، لذا خصصوا ذلك لتيمي. الآن لسبب ما يريد تيمي تخزين قطعة أخرى من الأمتعة ، لكن B4لا يمكنه تخزين 3 قطع ، قطعتان فقط ، فماذا يفعلون؟

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

هذه عملية باهظة الثمن ولكنها بالضبط كيف تعمل الذاكرة أيضًا!

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

ما تفعله المصفوفة الديناميكية هو أنه إذا اقتربت المصفوفة من سعتها الكاملة ، فسوف تعلن تلقائيًا عن مصفوفة جديدة أكبر وتنقل جميع العناصر الموجودة فيها ، ثم يتم جمع المصفوفة القديمة. كم أكبر؟ عادة ما يكون عامل النمو 2 ؛ ضعف حجم المصفوفة الحالية.

في الحقيقة ، لا تأخذ كلامي على محمل الجد .

لدى Ruby وحدة ObjectSpace تسمح لنا بالتفاعل مع الكائنات الحالية التي تعيش في الذاكرة. يمكننا استخدام هذه الوحدة لإلقاء نظرة خاطفة على استخدام الذاكرة لمصفوفة ديناميكية لدينا - تبدو تمامًا مثل ما نريد!

لقد كتبت نصًا صغيرًا من Ruby يقوم بحساب عامل نمو المصفوفة الديناميكية. لا تتردد في إلقاء نظرة عليها هنا ، وإذا قمت بذلك ، يمكنك أن ترى أن مصفوفات Ruby لها عامل نمو 1.5x (أي أنها تصنع مصفوفة أكبر بنسبة 50٪ في كل نسخة).

أعرف ما هي المصفوفات ، ما هي القوائم المرتبطة؟

ضع في اعتبارك أنه على الرغم من اعتبار كل من المصفوفات والقوائم المرتبطة هياكل بيانات خطية ، إلا أن هناك فرقًا كبيرًا بينهما.

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

يبدو الأمر كما لو أن تيمي يحاول تخزين 5 قطع من الأمتعة ، وليس لدى الكونسيرج مساحة ويقرر تركها في كل مكان. يبدو غير منظم؟

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

تتكون العقدة في القائمة المرتبطة من جزأين - جزء البيانات ومؤشر إلى العقدة التالية. هذه هي الطريقة التي يمكنهم بها الحفاظ على linearالجزء منه - لا يزال لديهم مفهوم النظام ، ولا يتعين عليهم تخزينها بالترتيب حرفيًا!

node = [ data | pointer ]

على سبيل المثال ، بالنظر إلى المثال التالي المخزن في الذاكرة:

[C | D] [A | B] [B | C] [D | nil]

تبدو هذه البتات وكأنها معطلة - ولكن إذا أخبرتك أن العنصر الأول هو A، فستتمكن من إخباري بالترتيب الدقيق للقائمة:

list = [A -> B -> C ->د -> لا شيء]

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

شكراً ، التالي: مقدمة للقوائم المرتبطة

في هذا المنشور ، سنتحدث عن بنية بيانات القائمة المرتبطة بلغة "شكرًا لك ، التالي" بقلم… dev.to

يمكنك أيضًا قراءة المزيد حول List / Cons on Wiki هنا.

ملاحظة ختامية

كتبت هذا المقال في البداية عن موضوع مختلف قليلاً - [إكسير | لماذا القوائم المرتبطة؟] ، ولكن وجدت أن الأمر استغرق وقتًا طويلاً لشرح كيفية عمل المصفوفات قبل أن أتمكن من شرح استكشاف سبب استخدام Elixir للقوائم المرتبطة. لذا فقد فصلتهم إلى مقالتين.

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

[إكسير | لماذا القوائم المرتبطة؟ ]

لطالما اعتقدت أن هياكل البيانات رائعة ، لكنك تعرف ما هو الأفضل؟ نراهم في البرية! أثناء المرور… dev.to

المصادر

  1. //medium.com/@rebo_dood/ruby-has-a-memory-problem-part-1-7887bbacc579 - هنا اكتشفت ObjectSpaceطرقًا إضافية من خلال طلبها

نشرت أصلا على dev.to