ترتيب الصفوف والأعمدة

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

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

يُعدّ تخطيط البيانات أمرًا بالغ الأهمية لتمرير المصفوفات بشكل صحيح بين البرامج المكتوبة بلغات برمجة مختلفة. كما أنه مهمٌّ للأداء عند اجتياز المصفوفة، لأن وحدات المعالجة المركزية الحديثة تعالج البيانات المتسلسلة بكفاءة أعلى من البيانات غير المتسلسلة. ويعود ذلك أساسًا إلى التخزين المؤقت لوحدة المعالجة المركزية الذي يستغلّ خاصية التوطين المكاني للمرجعية . ^{[ 1 ]} بالإضافة إلى ذلك، يُتيح الوصول المتجاور استخدام تعليمات SIMD التي تعمل على متجهات البيانات. في بعض وسائط التخزين، مثل أشرطة التخزين المغناطيسية ، يكون الوصول المتسلسل أسرع بكثير من الوصول غير المتسلسل.

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

في حالة المصفوفات، تكون السمات هي المؤشرات على طول كل بُعد. بالنسبة للمصفوفات في الترميز الرياضي، يشير المؤشر الأول إلى الصف ، ويشير الثاني إلى العمود ، على سبيل المثال، بالنظر إلى مصفوفة${\displaystyle A}$، المدخل${\displaystyle a_{1,2}}$يقع في الصف الأول والعمود الثاني. وقد تم اعتماد هذا الاصطلاح في بناء الجملة في لغات البرمجة، ^{[ 2 ]} على الرغم من أن الفهارس تبدأ غالبًا من 0 بدلاً من 1. ^{[ 3 ]}

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

على سبيل المثال، المصفوفة

${\displaystyle A=a_{y,x}={\begin{bmatrix}\color {Blue}a_{11}&\color {Blue}a_{12}&\color {Blue}a_{13}\\\color {Orange}a_{21}&\color {Orange}a_{22}&\color {Orange}a_{23}\end{bmatrix}}}$

يمكن تخزينها بطريقتين محتملتين:

عنوان	ترتيب الصفوف الرئيسية	ترتيب الأعمدة
0	${\displaystyle \color {Blue}a_{11}}$	${\displaystyle \color {Blue}a_{11}}$
1	${\displaystyle \color {Blue}a_{12}}$	${\displaystyle \color {Orange}a_{21}}$
2	${\displaystyle \color {Blue}a_{13}}$	${\displaystyle \color {Blue}a_{12}}$
3	${\displaystyle \color {Orange}a_{21}}$	${\displaystyle \color {Orange}a_{22}}$
4	${\displaystyle \color {Orange}a_{22}}$	${\displaystyle \color {Blue}a_{13}}$
5	${\displaystyle \color {Orange}a_{23}}$	${\displaystyle \color {Orange}a_{23}}$

تتعامل لغات البرمجة مع هذا الأمر بطرق مختلفة. في لغة C ، يتم تخزين المصفوفات متعددة الأبعاد بترتيب الصفوف، وتُكتب فهارس المصفوفة من الصف الأول (ترتيب الوصول المعجمي):

ج: ترتيب الصفوف (ترتيب الوصول المعجمي)، الفهرسة التي تبدأ من الصفر

عنوانx + N_x*y	وصولA[y][x]	قيمة${\displaystyle a_{y,x}}$
0	A[0][0]	${\displaystyle a_{11}}$
1	A[0][1]	${\displaystyle a_{12}}$
2	A[0][2]	${\displaystyle a_{13}}$
3	A[1][0]	${\displaystyle a_{21}}$
4	A[1][1]	${\displaystyle a_{22}}$
5	A[1][2]	${\displaystyle a_{23}}$

من ناحية أخرى، في لغة فورتران ، يتم تخزين المصفوفات بترتيب الأعمدة، بينما لا تزال فهارس المصفوفة تُكتب من الصف الأول (ترتيب الوصول المعجمي):

فورتران: ترتيب الأعمدة (ترتيب الوصول المعجمي)، فهرسة تبدأ من واحد

عنوانy + N_y*(x-1)	وصولA(y,x)	قيمة${\displaystyle a_{y,x}}$
1	A(1,1)	${\displaystyle a_{11}}$
2	A(2,1)	${\displaystyle a_{21}}$
3	A(1,2)	${\displaystyle a_{12}}$
4	A(2,2)	${\displaystyle a_{22}}$
5	A(1,3)	${\displaystyle a_{13}}$
6	A(2,3)	${\displaystyle a_{23}}$

لاحظ كيف أن استخدام A[i][j]الفهرسة متعددة الخطوات كما في لغة C، على عكس الترميز المحايد كما A(i,j)في لغة Fortran، يُشير حتمًا تقريبًا إلى ترتيب الصفوف لأسباب نحوية، لأنه يُمكن إعادة كتابته على النحو التالي: ويمكن حتى إسناد جزء (A[i])[j]الصف A[i]إلى متغير وسيط يتم فهرسته لاحقًا في تعبير منفصل. (لا ينبغي افتراض أي دلالات أخرى، على سبيل المثال، لا تعتمد لغة Fortran على ترتيب الأعمدة لمجرد ترميزها ، بل يُمكن تجاوز الدلالة المذكورة أعلاه عمدًا في لغة جديدة).

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

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

يُستخدم ترتيب الصفوف الرئيسي في لغات C / C++ / Objective-C (للمصفوفات على نمط C)، و PL/I ، ^{[ 4 ]} و Pascal ، ^{[ 5 ]} و Speakeasy ، ^{[ 6 ]} و SAS . ^{[ 7 ]}

يُستخدم ترتيب الأعمدة في لغات البرمجة التالية: Fortran ، ^{[ 8 ] [ 9 ]} IDL ، ^{[ 8 ]} MATLAB ، ^{[ 9 ]} GNU Octave ، Julia ، ^{[ 10 ]} S ، S-PLUS ، ^{[ 11 ]} R ، ^{[ 12 ]} Scilab ، ^{[ 13 ]} Yorick ، و Rasdaman . ^{[ 14 ]}

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

على سبيل المثال، يتم تمرير علامات إلى وظائف البرامج الفرعية للجبر الخطي الأساسي تشير إلى المصفوفات التي يتم تبديلها. ^{[ 25 ]}

يمكن تعميم هذا المفهوم ليشمل المصفوفات ذات الأبعاد التي تزيد عن بعدين.

بالنسبة لـ d- الأبعاد${\displaystyle N_{1}\times N_{2}\times \cdots \times N_{d}}$مصفوفة ذات أبعاد N _k ( حيث k = 1 ... d )، ويتم تحديد عنصر معين من هذه المصفوفة بواسطة مجموعة.${\displaystyle (n_{1},n_{2},\ldots ,n_{d})}$من مؤشرات d (التي تبدأ من الصفر)${\displaystyle n_{k}\in [0,N_{k}-1]}$.

في ترتيب الصفوف، يكون البعد الأخير متجاورًا، وبالتالي فإن إزاحة الذاكرة لهذا العنصر تُعطى بالصيغة التالية: $${\displaystyle n_{d}+N_{d}\cdot (n_{d-1}+N_{d-1}\cdot (n_{d-2}+N_{d-2}\cdot (\cdots +N_{2}n_{1})\cdots ))=\sum _{k=1}^{d}\left(\prod _{\ell =k+1}^{d}N_{\ell }\right)n_{k}}$$

في ترتيب الأعمدة، يكون البعد الأول متجاورًا، وبالتالي فإن إزاحة الذاكرة لهذا العنصر تُعطى بالصيغة التالية: $${\displaystyle n_{1}+N_{1}\cdot (n_{2}+N_{2}\cdot (n_{3}+N_{3}\cdot (\cdots +N_{d-1}n_{d})\cdots ))=\sum _{k=1}^{d}\left(\prod _{\ell =1}^{k-1}N_{\ell }\right)n_{k}}$$ حيث يكون الناتج الفارغ هو العنصر المحايد الضربي ، أي${\textstyle \prod _{\ell =1}^{0}N_{\ell }=\prod _{\ell =d+1}^{d}N_{\ell }=1}$.

بالنسبة لترتيب معين، يتم تحديد الخطوة في البعد k بواسطة قيمة الضرب الموجودة بين قوسين قبل الفهرس n _k في عمليات الجمع على الجانب الأيمن أعلاه.

بشكل عام، هناك d! ترتيب ممكن لمصفوفة معينة، واحد لكل تبديل للأبعاد (مع ترتيب الصفوف وترتيب الأعمدة حالتين خاصتين فقط)، على الرغم من أن قوائم قيم الخطوة ليست بالضرورة تباديل لبعضها البعض، على سبيل المثال، في مثال 2×3 أعلاه، تكون الخطوات (3،1) لترتيب الصفوف و(1،2) لترتيب الأعمدة.

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

• دونالد إي. كنوث، فن برمجة الحاسوب المجلد 1: الخوارزميات الأساسية ، الطبعة الثالثة، القسم 2.2.6 (أديسون-ويسلي: نيويورك، 1997).