المصفوفة

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

عمليات المصفوفة الشائعة

تهيئة المصفوفات

يمكننا الاختيار بين طريقتين لتهيئة المصفوفة حسب حاجتنا: مع قيم أولية أو دونها. وعندما لا تُحدَّد قيم أولية، تهيّئ معظم لغات البرمجة عناصر المصفوفة إلى $0$:

/* تهيئة المصفوفة */
var arr [5]int
// في Go، تحديد الطول ([5]int) ينشئ مصفوفة؛ وعدم تحديد الطول ([]int) ينشئ slice
// وبما أن مصفوفات Go مصممة بحيث يُحدَّد طولها في زمن الترجمة، فلا يمكن استخدام سوى الثوابت لتحديد الطول
// لتسهيل تنفيذ الدالة extend()، تُعامَل slices كمصفوفات فيما يلي
nums := []int{1, 3, 2, 5, 4}

/* تهيئة المصفوفة */
let arr: number[] = new Array(5).fill(0);
let nums: number[] = [1, 3, 2, 5, 4];

الوصول إلى العناصر

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

وبمراقبة الشكل أعلاه، نجد أن فهرس أول عنصر في المصفوفة هو $0$، وهو ما قد يبدو مخالفاً للحدس لأن العدّ من $1$ أكثر طبيعية. غير أنه من منظور صيغة حساب العنوان، ليس الفهرس في جوهره سوى إزاحة عن العنوان في الذاكرة. وإزاحة عنوان العنصر الأول هي $0$، فمن المنطقي أن يكون فهرسه $0$.

والوصول إلى عناصر المصفوفة عالي الكفاءة؛ إذ يمكننا الوصول العشوائي إلى أي عنصر في المصفوفة في زمن $O(1)$.

/* الوصول العشوائي إلى عنصر */
func randomAccess(nums []int) (randomNum int) {
	// اختيار عدد عشوائي في الفترة [0, nums.length)
	randomIndex := rand.Intn(len(nums))
	// استرجاع العنصر العشوائي وإعادته
	randomNum = nums[randomIndex]
	return
}

/* الوصول العشوائي إلى عنصر */
function randomAccess(nums: number[]): number {
    // اختيار عدد عشوائي في الفترة [0, nums.length)
    const random_index = Math.floor(Math.random() * nums.length);
    // استرجاع العنصر العشوائي وإعادته
    const random_num = nums[random_index];
    return random_num;
}

إدراج العناصر

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

وجدير بالذكر أنه بما أن طول المصفوفة ثابت، فسيؤدي إدراج عنصر حتماً إلى دفع العنصر الأخير خارج المصفوفة. وسنترك حل هذه المشكلة لمناقشته في فصل «القائمة».

/* إدراج العنصر num عند الفهرس index في المصفوفة */
func insert(nums []int, num int, index int) {
	// إزاحة جميع العناصر عند الفهرس index وما بعده موضعاً واحداً إلى الخلف
	for i := len(nums) - 1; i > index; i-- {
		nums[i] = nums[i-1]
	}
	// إسناد num إلى العنصر عند الفهرس index
	nums[index] = num
}

/* إدراج العنصر num عند الفهرس index في المصفوفة */
function insert(nums: number[], num: number, index: number): void {
    // إزاحة جميع العناصر عند الفهرس index وما بعده موضعاً واحداً إلى الخلف
    for (let i = nums.length - 1; i > index; i--) {
        nums[i] = nums[i - 1];
    }
    // إسناد num إلى العنصر عند الفهرس index
    nums[index] = num;
}

حذف العناصر

وبالمثل، وكما يوضح الشكل أدناه، لحذف العنصر عند الفهرس $i$، علينا إزاحة جميع العناصر بعد الفهرس $i$ موضعاً واحداً إلى الأمام.

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

/* حذف العنصر عند الفهرس index */
func remove(nums []int, index int) {
	// إزاحة جميع العناصر بعد الفهرس index موضعاً واحداً إلى الأمام
	for i := index; i < len(nums)-1; i++ {
		nums[i] = nums[i+1]
	}
}

/* حذف العنصر عند الفهرس index */
function remove(nums: number[], index: number): void {
    // إزاحة جميع العناصر بعد الفهرس index موضعاً واحداً إلى الأمام
    for (let i = index; i < nums.length - 1; i++) {
        nums[i] = nums[i + 1];
    }
}

إجمالاً، لعمليتي الإدراج والحذف في المصفوفة العيوب التالية:

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

اجتياز المصفوفات

في معظم لغات البرمجة، يمكننا اجتياز المصفوفة إما بالفهرس وإما بالتكرار المباشر على كل عنصر في المصفوفة:

/* اجتياز المصفوفة */
func traverse(nums []int) {
	count := 0
	// اجتياز المصفوفة بالفهرس
	for i := 0; i < len(nums); i++ {
		count += nums[i]
	}
	count = 0
	// الاجتياز المباشر لعناصر المصفوفة
	for _, num := range nums {
		count += num
	}
	// اجتياز فهرس البيانات وعناصرها معاً
	for i, num := range nums {
		count += nums[i]
		count += num
	}
}

/* اجتياز المصفوفة */
function traverse(nums: number[]): void {
    let count = 0;
    // اجتياز المصفوفة بالفهرس
    for (let i = 0; i < nums.length; i++) {
        count += nums[i];
    }
    // الاجتياز المباشر لعناصر المصفوفة
    for (const num of nums) {
        count += num;
    }
}

البحث عن العناصر

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

وبما أن المصفوفة بنية بيانات خطية، تُسمى عملية البحث أعلاه «البحث الخطي».

/* البحث عن العنصر المحدد في المصفوفة */
func find(nums []int, target int) (index int) {
	index = -1
	for i := 0; i < len(nums); i++ {
		if nums[i] == target {
			index = i
			break
		}
	}
	return
}

/* البحث عن العنصر المحدد في المصفوفة */
function find(nums: number[], target: number): number {
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === target) {
            return i;
        }
    }
    return -1;
}

توسيع المصفوفات

في بيئات الأنظمة المعقّدة، لا تستطيع البرامج ضمان توفر مساحة الذاكرة بعد المصفوفة، مما يجعل توسيع سعة المصفوفة غير آمن. لذلك، في معظم لغات البرمجة، طول المصفوفة غير قابل للتغيير.

وإذا أردنا توسيع مصفوفة، فعلينا إنشاء مصفوفة جديدة أكبر ثم نسخ عناصر المصفوفة الأصلية إلى المصفوفة الجديدة عنصراً عنصراً. وهذه عملية بتعقيد $O(n)$، وتستهلك وقتاً طويلاً عندما تكون المصفوفة كبيرة. وتظهر الشيفرة أدناه:

/* توسيع طول المصفوفة */
func extend(nums []int, enlarge int) []int {
	// تهيئة مصفوفة بطول موسّع
	res := make([]int, len(nums)+enlarge)
	// نسخ جميع عناصر المصفوفة الأصلية إلى المصفوفة الجديدة
	for i, num := range nums {
		res[i] = num
	}
	// إعادة المصفوفة الجديدة الموسّعة
	return res
}

/* توسيع طول المصفوفة */
// ملاحظة: Array في TypeScript مصفوفة ديناميكية، ويمكن توسيعها مباشرةً
// لأغراض التعلّم، تتعامل هذه الدالة مع Array على أنها مصفوفة ثابتة الطول
function extend(nums: number[], enlarge: number): number[] {
    // تهيئة مصفوفة بطول موسّع
    const res = new Array(nums.length + enlarge).fill(0);
    // نسخ جميع عناصر المصفوفة الأصلية إلى المصفوفة الجديدة
    for (let i = 0; i < nums.length; i++) {
        res[i] = nums[i];
    }
    // إعادة المصفوفة الجديدة الموسّعة
    return res;
}

مزايا المصفوفات وحدودها

تُخزَّن المصفوفات في مساحة ذاكرة متجاورة بعناصر من النوع نفسه. ويحتوي هذا الأسلوب على معلومات مسبقة غنية يمكن للنظام استخدامها لتحسين كفاءة عمليات بنى البيانات.

• كفاءة مكانية عالية: تخصص المصفوفات كتل ذاكرة متجاورة للبيانات دون عبء بنيوي إضافي.
• دعم الوصول العشوائي: تتيح المصفوفات الوصول إلى أي عنصر في زمن $O(1)$.
• محلية ذاكرة التخزين المؤقت (cache locality): عند الوصول إلى عناصر المصفوفة، لا يحمّل الحاسوب العنصر فحسب، بل يخزّن البيانات المحيطة في ذاكرة التخزين المؤقت أيضاً، مستفيداً بذلك من الذاكرة المؤقتة لتحسين سرعة تنفيذ العمليات اللاحقة.

وتخزين البيانات في مساحة متجاورة سلاح ذو حدين، وله الحدود التالية:

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

التطبيقات النموذجية للمصفوفات

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

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