شرح الArrays كdata structure

 Arrays

صورة بسيطة تخيلية لشكل ال Array

مقدمة:

ال Array: هى واحدة من أكثر هياكل البيانات شيوعا على الإطلاق. وقد تلاحظ كثيرا، إذا ما بدأت تعلم أى لغة برمجة جديدة بالنسبة إليك، أن ال array هى واحدة من المفاهيم الرئيسية التي يتم شرحها تحت عنوان: "أنواع البيانات".

إلا أن شرح ال array المعتاد، في كورس تعلم لغة برمجة ما. يتسم بالسهولة والبساطة.

أما في هذه المقالة بإذن الله ندرسها بإسهاب وإطناب.

ال Array:

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

من التعريف السابق لل array يمكن أن نطرح عدة أسئلة:

أولا: ما هى هياكل البيانات (Data structure) ؟

هياكل البيانات هى طرق لترتيب  البيانات في الجهاز، بشكل يكون أكثر فاعلية.

من التعريف السابق لهياكل البيانات قد تتساءل حول:

ما المقصود ب"شكل يكون أكثر فاعلية":

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

ثانيا: ما المقصود بتخزين مجموعة من البيانات؟

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

لكن بمساعدة ال array، يمكنك تخزين جميع القيم الرقمية في متغير واحد.

قد يراودك تساؤل حول:

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

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

في لغات عديدة قديمة ك Cpp و ال Java وغيرهما، تشترط أن تعلن عن نوع القيم التي ستكون في الarray التي ستنشئها، وبالتالي تتكون الarray من عناصر جميعها من نفس النوع.

إلا أن اللغات الأحدث كال JavaScript وال Python وغيرهما، يمكنك من خلالهما إنشاء array تكون عناصرها من أنواع بيانات مختلفة.

ثالثا: ما المقصود ب"شكل متسلسل في ذاكرة الجهاز" ؟

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

باختصار:ذاكرة الكمبيوتر لها منافذ تخزن فيها البيانات، وكل منفذ له عنوان خاص به، وعنوان المنفذ الذي يلي أى منفذ = عنوان المنفذ + 1.

والمقصود بأن ال array تسجل البيانات بشكل متسلسل في الذاكرة: هذا يعني أن ال array تحجز مساحة في ذاكرة الجهاز = حجم البيانات التي ستضيفها او أضفتها. وتلك المساحة المحجوزة تتسم بأنها منذ بدايتها حتى نهايتها هى منافذ متتالية في الذاكرة لا يفرقها أى منفذ لا ينتمي لل array.

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

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

فيديو توضيحي  للفقرة السابقة

رابعا: ماذا تقصد ب"الجهاز"؟

أقصد بالجهاز، كل آلة لديها hardware.

ال Indexing:

هو ببساطة طريقة لترقيم مواقع مجموعة من البيانات، التي يهم ادراك أنها متتالية،ويبدأ الترقيم من 0 حتى نهاية هذه القيم، وكلما انتقلت من موقع إلى الموقع الذي يليه تضيف 1.

ولأن ال array كما سبق وأخبرت، أنها تخزن في الذاكرة بشكل متتابع أو متسلسل، فإن مواقع البيانات تكون بجانب بعضها البعض، مما يجعل طريقة ترتيب البيانات في ال array، تكون متوافقة مع مفهوم ال Indexing.

يمكن أن نقول أن array تتكون من 5 عناصر، يبدأ عنصرها الأول من ال Index صفر. وتنتهي مع عنصرها الأخير حيث ال Index أربعة.

وبما أن ال Indexing يبدأ دائما من القيمة صفر، فإن الIndex للقيمة الأخيرة لأى array يساوي: طول الarray ناقص 1.

فيديو توضيحي للفقرة السابقة

عمليات الإضافة والبحث في ال Array:

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

أولا : عمليات الإضافة:

يمكننا أن نقسم عمليات الإضافة في ال Array، إلى ثلاث عمليات رئيسية:

1- push/append:

صورة توضيحية لعملية ال push أو ال append

أقصد بعملية الpush أو الappend: هى عملية إضافة عنصر في نهاية الarray.

 

أثناء بناء الarray ، كلما أضيف لها عنصر، كلما زاد حجمها وسجل حجمها في واحدة من خصائصها وهى خاصية الطول (length) وغالبا ما نستدعيها بهاذا الشكل: array_name.length .
وقد علمنا مسبقا أن الarray تترتب عناصرها بمفهوم الIndexing، وأن ال index الخاص بآخر عنصر مضاف في الarray = طول الarray مطروح منها 1.

وبهاذا نستطيع أن نقول أن مكان العنصر الجديد = مكان العنصر الأخير + 1. وذلك ما يساويه طول الarray.
ولأننا نعلم الآن المكان الذي سيضاف فيه العنصر الجديد، وأن إضافة عنصر جديد لن يترتب عليها أى تغير في ترتيب عناصر الarray السابقة؛ يمكننا القول أن إضافة عنصر في نهاية الarray يستهلك نفس الوقت مهما كانت حجم ال array. وذلك نعبر عنه بالجملة التالية:"الوقت المستهلك لإضافة عنصر في نهاية array في أسوأ الأحوال = O(1)".

إن لم تفهم ما المقصود ب O(1) حتى الآن فلا تقلق، الأمر سيصبح أبسط كلما قرأت الفقرة السابقة، والفقرات اللاحقة. كما أنه حتى لو لم تستوعبها بشكل واف، يمكنك البحث حول: "تحليل الخوارزميات".

فيديو توضيحي للفقرة السابقة

2- unshift:

صورة توضيحية لعملية الunshift

أقصد بعملية الunshift : هى عملية إضافة بيان في بداية الarray.

إذا كان لديك array تحوي 5 عناصر، وأردت إضافة عنصر سادس، لكن ذلك العنصر تريده أن يقع في مكان الIndex صفر، أى في بداية الarray. فهاذا ما يجب أن يحدث:

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

2 - ستحتاج أن تحرك آخر عناصر ال array خطوة إلى الخلف فيصبح مكانه الجديد = الIndex الحالي + 1. وكذالك للعنصر قبل الأخير، فيحل محل المحل القديم للعنصر الأخير، وهكذا. حتى يصبح مكان الIndex صفر فارغا.

3 - حينها تعلن أن array[0] (يعبر عنها ب الIndex صفر للarray) تساوي قيمتها قيمة البيان الجديد.

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

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

تلاحظ: أنه لإضافة عنصر في بداية الarray، تحتاج لتحريك جميع العناصر الأخرى مرة للخلف. أى لو أن حجم الarray يساوي 6 عناصر، ستحتاج أن تحرك 6 عناصر مرة للخلف لتضيف العنصر الجديد.

لذا فإنا نَصف التعقيد الزمني لهذه الخوارزمية بهذا الرمز : O(n) وهاذا يعني، أنه في كل مرة ستضيف عنصرا إلى بداية ال array سيكلفك ذلك أن تمر على جميع عناصر ال array لتجري عليها العمليات.

بما أنك اطلعت سابقا على O(1)، فمن الملاحظ أنها تعبر عن خورزميات أسرع من الخوارزميات التي يعبر عنها ب O(n).

ملحوظة: تقرأ O(n) هكذا: Big O of N.

فيديو توضيحي للفقرة السابقة

3- Insert:

ثلاثة خطوات يوضح فيها مفهوم الInsert  لإضافة العنصر 100 مكان الIndex اثنان.

أقصد بعملية الInsert: هى عملية إضافة بيان في أى مكان في ال array.

بالطبع علمت مسبقا مالذي يحدث عند إضافة عنصر في نهاية الarray، وبدايتها، وما تكلفة كلا من العمليتين. ( O(1) , O(n) ).

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

 ألن يدفعك إلى الخلف ليصبح هو الثاني، وأنت الثالث، بينما الرجل الأول بالتأكيد، لم يتغير مكانه، فهو ما زال في الأول؟

ذلك هو ما يحدث بالضبط، إذا كان لديك array بحجم عنصرين مثلا، وأردت وضع عنصر مكان العنصر الثاني، حينها ستضطر أن تقوم بالتالي:

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

2 - ستحتاج أن تحرك آخر عناصر ال array خطوة إلى الخلف  والذي هو العنصر الثاني، ماذا لو كنت تمتلك 3 عناصر بدل 2؟ ستضطر إلى تحريك الثالث والثاني، المهم مهما كان حجم ال array، ستضطر إلى تحريك جميع العناصر بداية من العنصر الاخير مرة إلى الخلف، حتى يصبح المكان الذي تريد أن تضيف فيه العنصر الجديد فارغا.

3 - ستضيف العنصر الجديد مكان ال Index الفارغ واحد (وهو ال Index الذي كان يقع العنصر الثاني سابقا عنده. وذلك لأن العنصر الأول يقع في ال Index صفر).

تلاحظ: أنه لو أردنا أن نضيف العنصر لنهاية الarray فإن ذلك لن يكلفنا تحريك أى عنصر كما سلف وشرحنا في الجزء الخاص بالعمليات ( push/append ) وأنه لو أردنا أن نضيف العنصر في بداية الarray كان ليكلفنا ذلك تحريك كل العناصر وذلك كما سلف في شرح العملية (unshift)، أما لو أردنا أن نضيف العنصر في أى مكان آخر، فسيكلفنا ذالك تحريك جميع العناصر التي تقع خلف المكان الذي نريد أن نضيف فيه العنصر الجديد، إضافة إلى العنصر الذي يقع في ذلك المكان، مرة للخلف ثم نضيف العنصر الجديد.

قد تتسائل طبقا لما لاحظناه سابقا، هل لهذه العملية أكثر من تعقيد زمنى، في حقيقة الأمر عندما نقرر أن نَصف التعقيد الزمنى لأى خوارزمية\عملية فإننا نصفها بأسوأ إحتمال لها (الإحتمال الذي يجعل الخوارزمية تأخذ أطول وقت ممكن). وفي هذه الخوارزمية أنت مخير بين هاذين الوصفين  ( O(1) , O(n) ). وبالطبع الوصف الأنسب هو O(n).

فيديو توضيحي للفقرة السابقة

ثانيا : عمليات الإزالة:

يمكننا أن تقسم عمليات الإزالة في الArray، إلى ثلاث عمليات رئيسية:

1- pop:

صورة توضيحية لعملية الpop

أقصد بعملية الpop: هى عملية حذف عنصر من نهاية الarray.

 

علمنا مسبقا أنه: يمكننا الإطلاع مباشرة على آخر عنصر في ال array؛ لأنه دائما ما يقع آخر عنصر عند ال Index الذي تساوي قيمته: حجم ال array ناقص 1.

وبهاذا فيمكنني بعد تحديد العنصر الأخير. أن أغير قيمة العنصر إلى Null مثلا. ثم ننقص من الحجم ما مقداره واحد؛ لأننا حذفنا عنصرا واحدا.

ولأننا دائما ما نعلم مكان العنصر الأخير بشكل مباشر، دون الحاجه للمرور بعناصر أخرى. وأن حذف العنصر الأخير لن يترتب عليه أى تغير في ترتيب عناصر الarray؛ يمكننا القول أن حذف عنصر من نهاية الarray يستهلك نفس الوقت مهما كانت حجم الarray. وذلك نعبر عنه بالجملة التالية: "الوقت المستهلك لحذف عنصر من نهاية array في أسوأ الأحوال = O(1)".

فيديو توضيحي للفقرة السابقة

2- shift:

صورة توضيحية لعملية الshift

أقصد بعملية الshift: هى عملية حذف عنصر من بداية الarray.

إذا كان لديك array تحوي 5 عناصر، وأردت حذف العنصر الأول، لكن من المنطقي أن لا يكون الIndex الأول (0) فارغا. أى يجب أن أحذف أول عنصر في ال array، وفي نفس الوقت يجب أن يكون الIndex الأول للarray ليس فارغا إذا كان حجمها بالطبع أكبر من 1.ولفعل ذلك فهذا ما سيحدث:

1 - أن تحدد العنصر الأول، وذلك يمكن تحديده مباشرة :لأن من المتعارف عليه أن أول عنصر في أى array، يقع عند الIndex صفر، وبالطبع أنت مدرك لتفسير ذلك من فقرة الIndexing.

2 - بعد ذلك ستغير قيمته إلى قيمة لن تستعملها غالبا مثل Null أو undefined، أو يمكن أن تبدأ بالخطوة 3 مباشرة.

3 - انقل العنصر الثاني إلى الindex الأول(0) عن طريق هذا التعبير في الغالب: array[0] = قيمة العنصر الثاني.

 أو طبقا لما يوافق لغة البرمجة التي تستعملها. ثم انقل العنصر الثالث إلى ال index الثاني(1) وهكذا.

4 - قصر طول الarray بمقدار 1.

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

- بالطبع لا: أنت أيضا حينما تقدم الرجل الثاني ليأخذ مكان الرجل الأول، تقدمت خطوة لأن المكان الثاني أصبح فارغا. هاذا ما يحدث بالضبط في عملية ال shift.

تلاحظ: أنه لحذف عنصر من بداية ال array، تحتاج لتحريك جميع العناصر الاخرى مرة للأمام. أى لو أن حجم ال array يساوي 6 عناصر، ستحتاج أن تحرك 5عناصر مرة للخلف لتحذف العنصر الأول.

لذا فإنا نصف التعقيد الزمني لهذه الخوارزمية بهذا الرمز : O(n) وهاذا يعني، أنه في كل مرة ستضيف عنصرا إلى بداية ال array سيكلفك ذلك أن تمر على جميع عناصر ال array لتجري عليها العمليات.

فيديو توضيحي للفقرة السابقة

3- Remove:

صورة توضيحية لعملية الremove/delete

أقصد بعملية الremove : هى عملية حذف أى عنصر من أى مكان في الarray.

بالطبع علمت مسبقا مالذي يحدث عند حذف عنصر من نهاية ال array، وبدايتها، وما تكلفة كلا من العمليتين. ( O(1) , O(n) ).

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

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

ذلك هو ما يحدث بالضبط، إذا كان لديك array بحجم أكثر من ثلاثة عناصر مثلا، وأردت حذف العنصر الثاني، حينها ستضطر أن تقوم بالتالي:

1 - أن تحدد العنصر الثاني والذي يقع عند الIndex واحد بالطبع.

2 - ستحرك جميع العناصر خلف الIndex واحد خطوة للأمام.

3 - عندما تنتهي من نقل آخر عناصر ال array تقلل من حجمها بيمقدار 1.

تلاحظ: أنه لو أردنا أن نمحو عنصر من نهاية array فإن ذلك لن يكلفنا تحريك أى عنصر كما سلف وشرحنا في الجزء الخاص بالعمليات (pop) وأنه لو أردنا أن نحذف عنصر من بداية الarray كان ليكلفنا ذلك تحريك كل العناصر وذلك كما سلف في شرح العملية (shift)، أما لو أردنا أن نحذف العنصر من أى مكان آخر، فسيكلفنا ذالك تحريك جميع العناصر التي تقع خلف المكان الذي نريد أن نحذف منه العنصر، مرة للأمام.

مثل خوارزمية الInsert التي درستها مسبقا تشعر بوجود أكثر من تعقيد زمنى، لكن هذه المرة لن تتساءل حول إن كان لهذه العملية أكثر من تعقيد زمنى، ﻷنك تعلم أنه عندما نقرر أن نصف التعقيد الزمنى لأى خوارزمية\عملية فإننا نصفها بأسوأ إحتمال لها (الإحتمال الذي يجعل الخوارزمية تأخذ أطول وقت ممكن). وفي هذه الخوارزمية أنت مخير بين هاذين الوصفين  ( O(1) , O(n) ). وبالطبع الوصف الأنسب هو O(n) لأنه يصف الحالة الاسوء والتي تأخذ أطول وقت ممكن.

فيديو توضيحي للفقرة السابقة

الخاتمة:

ما زال للarray العديد من الخوارزميات، أو العمليات التي يمكن أن تقوم بها، لكن ما ذكرته هو ما يختص بالإضافة والحذف ﻷن هاتان العمليتان هما عصب التعامل مع البيانات عموما.

لكن لو أردت أمثلة للخوارزميات التي قد تساهم الarray في تنفيذها فلديك مثلا:

• خوارزميات البحث.
• خوارزميات الترتيب.
• خوارزميات رياضية إحصائية ك: إيجاد الوسيط لمجموعة رقمية، أو المتوسط الحسابي، أو أعظم قيمة أو أصغر قيمة.

والخوارزميات التي يمكن أن تنفذها بالarray لا حصر لها.

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

لو لديك أى ملحوظة ممكن أن تفيدني في كتابة مقالات مستقبلية شاركها في التعليقات، 

وشكرا...