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

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

المصفوفة الديناميكية ليست هي نفسها المصفوفة المُخصصة ديناميكيًا أو المصفوفة ذات الطول المتغير ، فكلتاهما عبارة عن مصفوفة يكون حجمها ثابتًا عند تخصيصها، على الرغم من أن المصفوفة الديناميكية قد تستخدم مصفوفة ذات حجم ثابت كخلفية. ^{[ 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 ]}  

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

The dynamic array has performance similar to an array, with the addition of new operations to add and remove elements:

• Getting or setting the value at a particular index (constant time)
• Iterating over the elements in order (linear time, good cache performance)
• Inserting or deleting an element in the middle of the array (linear time)
• Inserting or deleting an element at the end of the array (constant amortized time)

Dynamic arrays benefit from many of the advantages of arrays, including good locality of reference and data cache utilization, compactness (low memory use), and random access. They usually have only a small fixed additional overhead for storing information about the size and capacity. This makes dynamic arrays an attractive tool for building cache-friendly data structures. However, in languages like Python or Java that enforce reference semantics, the dynamic array generally will not store the actual data, but rather it will store references to the data that resides in other areas of memory. In this case, accessing items in the array sequentially will actually involve accessing multiple non-contiguous areas of memory, so the many advantages of the cache-friendliness of this data structure are lost.

Compared to linked lists, dynamic arrays have faster indexing (constant time versus linear time) and typically faster iteration due to improved locality of reference; however, dynamic arrays require linear time to insert or delete at an arbitrary location, since all following elements must be moved, while linked lists can do this in constant time. This disadvantage is mitigated by the gap buffer and tiered vector variants discussed under Variants below. Also, in a highly fragmented memory region, it may be expensive or impossible to find contiguous space for a large dynamic array, whereas linked lists do not require the whole data structure to be stored contiguously.

A balanced tree can store a list while providing all operations of both dynamic arrays and linked lists reasonably efficiently, but both insertion at the end and iteration over the list are slower than for a dynamic array, in theory and in practice, due to non-contiguous storage and tree traversal/manipulation overhead.

Gap buffers are similar to dynamic arrays but allow efficient insertion and deletion operations clustered near the same arbitrary location. Some deque implementations use array deques, which allow amortized constant time insertion/removal at both ends, instead of just one end.

قدم جودريتش ^{[ 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 ] : 22}System.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على أنه قابل للتعديل وموقع الإدراج بواسطة مؤشر التعبئة .

• المكدس (نوع بيانات مجرد)
• قائمة الانتظار (نوع بيانات مجرد)

• NIST Dictionary of Algorithms and Data Structures: Dynamic array
• VPOOL - C language implementation of dynamic array.
• CollectionSpy — A Java profiler with explicit support for debugging ArrayList- and Vector-related issues.
• Open Data Structures - Chapter 2 - Array-Based Lists, Pat Morin