مصفوفة ديناميكية

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

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

المصفوفة الديناميكية ليست هي نفسها المصفوفة المُخصصة ديناميكيًا أو المصفوفة ذات الطول المتغير ، فكلتاهما عبارة عن مصفوفة يكون حجمها ثابتًا عند تخصيصها، على الرغم من أن المصفوفة الديناميكية قد تستخدم مصفوفة ذات حجم ثابت كخلفية. [ 1 ]

المصفوفات الديناميكية ذات الحجم المحدود والسعة

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

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

يمكن حذف العناصر من نهاية المصفوفة الديناميكية في وقت ثابت، إذ لا يتطلب الأمر تغيير حجمها. يُعرف عدد العناصر المستخدمة في محتوى المصفوفة الديناميكية بحجمها المنطقي أو طولها ، بينما يُطلق على حجم المصفوفة الأساسية اسم حجمها الفعلي أو سعتها . السعة هي أقصى حجم ممكن دون نقل البيانات. [ 2 ]

تكفي المصفوفة ذات الحجم الثابت في التطبيقات التي يكون فيها الحد الأقصى للحجم المنطقي ثابتًا (مثلًا، وفقًا للمواصفات)، أو يمكن حسابه قبل تخصيص المصفوفة. وقد يُفضّل استخدام المصفوفة الديناميكية في الحالات التالية:

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

التوسع الهندسي والتكلفة المستهلكة

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

دالة insertEnd ( مصفوفة ديناميكية a ، عنصر e ) إذا كان (حجم a يساوي سعة a ) // قم بتغيير حجم a إلى ضعف سعتها الحالية: سعة a ← سعة a * 2 // (انسخ المحتويات إلى موقع الذاكرة الجديد هنا ) a [ حجم a ] ← e حجم a ← حجم a + 1

مع إدخال n عنصرًا، تتشكل السعات وفقًا لمتتالية هندسية . يضمن توسيع المصفوفة بنسبة ثابتة a أن يستغرق إدخال n عنصرًا وقتًا إجماليًا قدره O ( n ) ، أي أن كل عملية إدخال تستغرق وقتًا ثابتًا مُعدَّلًا (طالما أن أي تخصيص مُعطى يستغرق وقتًا قدره O ( 1 )). تقوم العديد من المصفوفات الديناميكية أيضًا بإلغاء تخصيص جزء من مساحة التخزين الأساسية إذا انخفض حجمها عن عتبة معينة، مثل 30% من السعة. يجب أن تكون هذه العتبة أصغر من 1/ a لتوفير التباطؤ (توفير نطاق مستقر لتجنب النمو والانكماش المتكررين) ودعم التسلسلات المختلطة من عمليات الإدخال والحذف بتكلفة ثابتة مُعدَّلة.

تُعد المصفوفات الديناميكية مثالاً شائعاً عند تدريس التحليل المُستهلك . [ 3 ] [ 4 ]

عامل النمو

يعتمد عامل النمو للمصفوفة الديناميكية على عدة عوامل، منها المفاضلة بين المساحة والوقت، والخوارزميات المستخدمة في مُخصِّص الذاكرة نفسه. بالنسبة لعامل النمو a ، يبلغ متوسط ​​زمن عملية الإدخال حوالي a /( a -1)، بينما يكون عدد الخلايا المهدرة محدودًا بـ ( a -1) n . إذا كان مُخصِّص الذاكرة يستخدم خوارزمية التخصيص الأولى ، فإن قيم عامل النمو مثل a = 2 قد تتسبب في نفاد الذاكرة أثناء توسيع المصفوفة الديناميكية، حتى مع وجود مساحة كبيرة متاحة. [ 5 ] وقد دارت نقاشات عديدة حول القيم المثالية لعامل النمو، بما في ذلك مقترحات النسبة الذهبية والقيمة 1.5. [ 6 ] مع ذلك، تستخدم العديد من الكتب الدراسية a = 2 للتبسيط ولأغراض التحليل. [ 3 ] [ 4 ]  

فيما يلي عوامل النمو المستخدمة في العديد من التطبيقات الشائعة:

تطبيقعامل النمو ( أ )
قائمة جافا [ 1 ]1.5 (3/2)
بايثون PyListObject [ 7 ]~1.125 (n + (n >> 3))
مايكروسوفت فيجوال سي++ 2013 [ 8 ]1.5 (3/2)
G++ 5.2.0 [ 5 ]2
Clang 3.6 [ 5 ]2
فيسبوك فولي/FBVector [ 9 ]1.5 (3/2)
محرك Unreal Engine TArray [ 10 ]~1.375 (n + ((3 * n) >> 3))
Rust Vec [ 11 ]2
شرائح جو [ 12 ]بين 1.25 و 2
تسلسلات نيم [ 13 ]2
متجهات SBCL ( لغة ليسب الشائعة ) [ 14 ]2
قائمة C# ( .NET 8)2

أداء

مقارنة هياكل بيانات القوائم
نظرة خاطفة (فهرس)قم بالتعديل (الإدراج أو الحذف) في …مساحة زائدة، متوسط
بدايةنهايةوسط
قائمة مرتبطةΘ( n )Θ(1)Θ(1)، العنصر النهائي المعروف؛ Θ( n )، عنصر نهائي غير معروفΘ( n )Θ( n )
المصفوفةΘ(1)غير متوفرغير متوفرغير متوفر0
مصفوفة ديناميكيةΘ(1)Θ( n )Θ(1) المستهلكةΘ( n )Θ( n ) [ 15 ]
شجرة متوازنةΘ(log n)Θ(log n)Θ(log n )Θ(log n )Θ( n )
قائمة الوصول العشوائيΘ(log n) [ 16 ]Θ(1)غير متوفر [ 16 ]غير متوفر [ 16 ]Θ( n )
شجرة المصفوفة المجزأةΘ(1)Θ( n )Θ(1) المستهلكةΘ( n )Θ(√ n )

تتمتع المصفوفة الديناميكية بأداء مشابه للمصفوفة العادية، مع إضافة عمليات جديدة لإضافة العناصر وإزالتها:

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

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

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

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

المتغيرات

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

قدم جودريتش [ 17 ] خوارزمية مصفوفة ديناميكية تسمى المتجهات المتدرجة والتي توفر أداء O ( n 1/ k ) للإدراجات والحذف من أي مكان في المصفوفة، و O ( k ) الحصول والتعيين، حيث k ≥ 2 هو معلمة ثابتة.

خوارزمية شجرة المصفوفة المُجزأة (HAT) هي خوارزمية مصفوفة ديناميكية نشرها سيتارسكي عام 1996. [ 18 ] تهدر هذه الخوارزمية مساحة تخزين تُقدّر بـ n 1/2 ، حيث n هو عدد عناصر المصفوفة. تتميز الخوارزمية بأداء O (1) عند إضافة سلسلة من العناصر إلى نهاية شجرة المصفوفة المُجزأة.

في ورقة بحثية نُشرت عام ١٩٩٩، [ ١٩ ] وصف برودنيك وآخرون بنية بيانات مصفوفة ديناميكية متعددة المستويات، لا تهدر سوى مساحة n 1/2 لـ n عنصرًا في أي لحظة زمنية، وأثبتوا حدًا أدنى يُبين أن أي مصفوفة ديناميكية يجب أن تهدر هذا القدر من المساحة لكي تظل العمليات ثابتة زمنيًا. بالإضافة إلى ذلك، قدموا صيغةً يكون فيها توسيع وتقليص المخزن المؤقت ليس فقط ثابتًا زمنيًا، بل ثابتًا في أسوأ الحالات.

قدم باجويل (2002) [ 20 ] خوارزمية VList، والتي يمكن تكييفها لتنفيذ مصفوفة ديناميكية.

تُحافظ المصفوفات القابلة لتغيير الحجم البسيطة - والتي تُسمى أيضًا "أسوأ تطبيق" للمصفوفات القابلة لتغيير الحجم - على حجم المصفوفة المُخصص كافيًا تمامًا لجميع البيانات التي تحتويها، ربما عن طريق استدعاء دالة إعادة التخصيص (realloc) لكل عنصر يُضاف إلى المصفوفة. تُعد المصفوفات القابلة لتغيير الحجم البسيطة أبسط طريقة لتنفيذ مصفوفة قابلة لتغيير الحجم في لغة C. فهي لا تُهدر أي ذاكرة، ولكن إضافة عنصر إلى نهاية المصفوفة تستغرق دائمًا وقتًا مقداره Θ( n ). [ 18 ] [ 21 ] [ 22 ] [ 23 ] [ 24 ] أما المصفوفات المتنامية خطيًا، فتُخصص مسبقًا ("تهدر") مساحة مقدارها Θ(1) في كل مرة تُغير فيها حجم المصفوفة، مما يجعلها أسرع بكثير من المصفوفات القابلة لتغيير الحجم البسيطة - لا تزال إضافة عنصر إلى نهاية المصفوفة تستغرق وقتًا مقداره Θ( n ) ولكن بقيمة ثابتة أصغر بكثير. قد تكون المصفوفات البسيطة القابلة لتغيير الحجم والمصفوفات المتنامية خطيًا مفيدة عندما يحتاج تطبيق ذو مساحة محدودة إلى الكثير من المصفوفات الصغيرة القابلة لتغيير الحجم؛ كما أنها تُستخدم بشكل شائع كمثال تعليمي يؤدي إلى المصفوفات الديناميكية المتنامية أُسّيًا. [ 25 ]

الدعم اللغوي

تُعدّ لغتا C++std::vector و Ruststd::vec::Vec تطبيقات للمصفوفات الديناميكية، كما هو الحال في Java java.util.ArrayList[ 26 ] [ 27 ] : 236 وفي إطار عمل .NET . [ 28 ] [ 29 ] : 22System.Collections.ArrayList

تُنفَّذ الفئة العامة System.Collections.Generic.List<T>في الإصدار 2.0 من إطار عمل .NET باستخدام المصفوفات الديناميكية. مصفوفة SmalltalkOrderedCollection هي مصفوفة ديناميكية ذات فهرس بداية ونهاية ديناميكيين، مما يجعل حذف العنصر الأول عمليةً ذات تعقيد زمني ثابت O(1).

يُعدّ تطبيق نوع البيانات في بايثونlist عبارة عن مصفوفة ديناميكية، ونمط نموها هو: 0، 4، 8، 16، 24، 32، 40، 52، 64، 76، ... [ 7 ]

تُطبّق لغتا Delphi و D المصفوفات الديناميكية في صميم اللغة.

توفر حزمة Ada العامة Ada.Containers.Vectorsتطبيقًا للمصفوفة الديناميكية لنوع فرعي معين.

توفر العديد من لغات البرمجة النصية مثل بيرل وروبي المصفوفات الديناميكية كنوع بيانات أساسي مدمج .

توفر العديد من أطر العمل متعددة المنصات تطبيقات المصفوفات الديناميكية للغة C ، بما في ذلك CFArrayفي CFMutableArrayCore Foundation ، GArrayو GPtrArrayفي GLib .

توفر لغة Common Lisp دعمًا بدائيًا للمتجهات القابلة لتغيير الحجم من خلال السماح بتكوين النوع المدمج arrayعلى أنه قابل للتعديل وموقع الإدراج بواسطة مؤشر التعبئة .

انظر أيضاً

مراجع

  1. 1 2 انظر، على سبيل المثال، إلى الكود المصدري لفئة java.util.ArrayList من OpenJDK 6 .
  2. ↑ لامبرت، كينيث ألفريد (2009)، "الحجم المادي والحجم المنطقي" ، أساسيات بايثون: من البرامج الأولى إلى هياكل البيانات ، سينجايج ليرنينج، ص  510، ISBN 978-1423902188
  3. 1 2 جودريتش، مايكل تي .؛ تاماسيا، روبرتو (2002)، "1.5.2 تحليل تطبيق مصفوفة قابلة للتوسيع"، تصميم الخوارزميات: الأسس والتحليل وأمثلة الإنترنت ، وايلي، ص 39-41 .
  4. 1 2 كورمن، توماس هـ .؛ ليسرسون، تشارلز إي .؛ ريفست، رونالد ل .؛ شتاين، كليفورد (2001) [1990]. "17.4 الجداول الديناميكية". مقدمة في الخوارزميات ( الطبعة الثانية). مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل. الصفحات 416-424 . ISBN   0-262-03293-7.
  5. 1 2 3 "متجه STL في لغة C++: التعريف، عامل النمو، الدوال الأعضاء" . مؤرشف من الأصل بتاريخ 2015-08-06 . تم الاطلاع عليه بتاريخ 2015-08-05 .
  6. ↑ "معامل نمو متجهي 1.5" . comp.lang.c++.moderated . مجموعات جوجل. مؤرشف من الأصل بتاريخ 22-01-2011 . تم الاطلاع عليه بتاريخ 05-08-2015 .
  7. 1 2 "cpython/Objects/listobject.c at bace59d8b8e38f5c779ff6296ebdc0527f6db14a - python/cpython" . GitHub . تم الاسترجاع في 27-03-2026 .
  8. ↑ برايس، هادي (15 نوفمبر 2013). "تشريح متجه STL في لغة C++: الجزء 3 - السعة والحجم" . ميكروميستريز . تم الاسترجاع في 5 أغسطس 2015 .
  9. ↑ "facebook/folly" . GitHub . تم الاسترجاع في 2015-08-05 .
  10. ↑ "مصفوفات T المتداخلة في الهياكل والذاكرة" . منتديات مجتمع مطوري Epic . 2025-02-26 . تم الاطلاع عليه بتاريخ 2025-05-26 .
  11. ↑ "rust-lang/rust" . GitHub . تم الاسترجاع في 2026-03-01 .
  12. ↑ "golang/go" . GitHub . تم الاسترجاع في 14-09-2021 .
  13. ↑ "نموذج ذاكرة نيم" . zevv.nl. تم الاطلاع عليه بتاريخ 24-05-2022 .
  14. ↑ "sbcl/sbcl" . GitHub . تم الاسترجاع في 15 فبراير 2023 .
  15. ↑ برودنيك، أندريه؛ كارلسون، سفانتي؛ سيدجويك، روبرت ؛ مونرو، جي آي؛ ديمين، إي دي (1999)، المصفوفات القابلة لتغيير الحجم في الوقت والمساحة الأمثلين (تقرير فني CS-99-09) (PDF) ، قسم علوم الحاسوب، جامعة واترلو
  16. 1 2 3 كريس أوكازاكي (1995). "قوائم الوصول العشوائي الوظيفية البحتة". وقائع المؤتمر الدولي السابع حول لغات البرمجة الوظيفية وهندسة الحاسوب : 86-95 . doi : 10.1145/224164.224187 .
  17. ↑ غودريتش، مايكل ت .؛ كلوس الثاني، جون ج. (1999)، "المتجهات المتدرجة: مصفوفات ديناميكية فعالة للتسلسلات القائمة على الرتب" ، ورشة عمل حول الخوارزميات وهياكل البيانات ، سلسلة محاضرات في علوم الحاسوب، المجلد 1663، الصفحات 205-216 ، doi : 10.1007/3-540-48447-7_21 ، ISBN   978-3-540-66279-2
  18. 1 2 سيتارسكي، إدوارد (سبتمبر 1996)، "HATs: أشجار المصفوفات المجزأة" ، زقاق الخوارزميات، مجلة دكتور دوب ، 21 (11)
  19. ↑ برودنيك، أندريه؛ كارلسون، سفانتي؛ سيدجويك، روبرت ؛ مونرو، جي آي؛ ديمين، إي دي (1999)، المصفوفات القابلة لتغيير الحجم في الوقت والمساحة الأمثلين (ملف PDF) (تقرير فني CS-99-09)، قسم علوم الحاسوب، جامعة واترلو
  20. ↑ باجويل، فيل (2002)، قوائم وظيفية سريعة، قوائم تجزئة، قوائم انتظار مزدوجة، ومصفوفات ذات أطوال متغيرة ، EPFL
  21. ↑ مايك لام. "المصفوفات الديناميكية" .
  22. ↑ "الوقت المستهلك" .
  23. ↑ "شجرة المصفوفة المجزأة: تمثيل فعال للمصفوفة" .
  24. ↑ "مفاهيم مختلفة للتعقيد" .
  25. ↑ بيتر كانكوفسكي. "المصفوفات الديناميكية في لغة C" .
  26. ↑ Javadoc onArrayList
  27. ↑ بلوخ، جوشوا (2018). "جافا الفعّالة: دليل لغة البرمجة" ( الطبعة الثالثة). أديسون-ويسلي. ISBN  978-0134685991.
  28. ↑ فئة ArrayList
  29. ↑ سكيت، جون (23 مارس 2019). لغة سي شارب بتفصيل . مانينغ. ISBN 978-1617294532.