تبديل عكس البت

في الرياضيات التطبيقية ، يُعرف تبديل عكس البتات بأنه تبديل لتسلسل من${\displaystyle n}$العناصر، حيث${\displaystyle n=2^{k}}$هو قوة للعدد اثنين . يتم تعريفه بفهرسة عناصر المتتالية بالأرقام من${\displaystyle 0}$ل${\displaystyle n-1}$، وتمثيل كل من هذه الأرقام بتمثيلها الثنائي (مع إضافة حشو ليكون طولها بالضبط${\displaystyle k}$), وتعيين كل عنصر للعنصر الذي يحتوي تمثيله على نفس البتات بترتيب معكوس.

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

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

لنفترض تسلسل الأحرف الثمانية abcdefgh . مؤشرات هذه الأحرف هي الأعداد الثنائية 000، 001، 010، 011، 100، 101، 110، و111، والتي عند عكسها تصبح 000، 100، 010، 110، 001، 101، 011، و111. بالتالي، يُنقل الحرف a في الموضع 000 إلى نفس الموضع (000)، ويُنقل الحرف b في الموضع 001 إلى الموضع الخامس (المرقم 100)، وهكذا، مما يُعطي التسلسل الجديد aecgbfdh . بتكرار نفس التبديل على هذا التسلسل الجديد، نحصل على التسلسل الأصلي.

كتابة أرقام الفهرس بالنظام العشري (ولكن، كما سبق، بدءًا من الموضع 0 بدلاً من البداية التقليدية 1 للتبديل)، تبديلات عكس البتات على${\displaystyle n=2^{k}}$بنود، لـ${\displaystyle k=0,1,2,3,\dots }$، هي: ^{[ 1 ]}

${\displaystyle k}$	${\displaystyle n=2^{k}}$	التبديل
0	1	0
1	2	0 1
2	4	0 2 1 3
3	8	0 4 2 6 1 5 3 7
4	16	٠ ٨ ٤ ١٢ ٢ ١٠ ٦ ١٤ ١ ٩ ٥ ١٣ ٣ ١١ ٧ ١٥

يمكن توليد كل تبديل في هذه المتتالية بدمج سلسلتين من الأرقام: التبديل السابق، مع مضاعفة قيمه، ونفس المتتالية مع زيادة كل قيمة بمقدار واحد. على سبيل المثال، مضاعفة التبديل ذي الطول 4، 0 2 1 3 ، يعطي 0 4 2 6 ، وإضافة واحد يعطي 1 5 3 7 ، ودمج هاتين السلسلتين يعطي التبديل ذي الطول 8، 0 4 2 6 1 5 3 7. ^{[ 2 ]}

التعميم إلى الجذر${\displaystyle b}$التمثيلات، من أجل${\displaystyle b>2}$و إلى${\displaystyle n=b^{k}}$، هو تبديل عكسي للأرقام ، حيث الأساس-${\displaystyle b}$يتم عكس أرقام فهرس كل عنصر للحصول على الفهرس المُبدَّل. ويمكن تعميم الفكرة نفسها على أنظمة الأعداد ذات الأساس المختلط . في هذه الحالات، يجب أن يعكس تبديل عكس الأرقام أرقام كل عنصر وأساس نظام الأعداد في آنٍ واحد، بحيث يبقى كل رقم معكوس ضمن النطاق المحدد بأساسه. ^{[ 3 ]}

يمكن استخدام التبديلات التي تعمم تبديل عكس البتات عن طريق عكس كتل البتات المتجاورة داخل التمثيلات الثنائية لمؤشراتها لدمج سلسلتين متساويتين في الطول من البيانات في مكانهما. ^{[ 4 ]}

يوجد امتدادان لتبديل عكس البتات ليشمل متواليات ذات أطوال عشوائية. يتطابق هذان الامتدادان مع عكس البتات للمتواليات التي يكون طولها قوة للعدد 2، وهدفهما فصل العناصر المتجاورة في المتوالية لتحسين كفاءة خوارزمية كاتشمارز . الامتداد الأول، المسمى الترتيب الفعال ، ^{[ 5 ]} يعمل على الأعداد المركبة، ويعتمد على تحليل العدد إلى مكوناته الأولية.

الامتداد الثاني، المسمى EBR (انعكاس البت الموسع)، مشابه في جوهره لانعكاس البت. بالنظر إلى مصفوفة بحجم${\displaystyle n}$، يقوم EBR بملء المصفوفة بتبديل الأرقام الموجودة في النطاق${\displaystyle 0\ldots n-1}$في زمن خطي. يتم فصل الأرقام المتتالية في التبديل بما لا يقل عن${\displaystyle \lfloor n/4\rfloor }$[ ^{6 ]​}

يُعدّ عكس البتات بالغ الأهمية في خوارزميات تحويل فورييه السريع (FFT) من نوع كولي-توكي ذات الأساس 2 ، حيث تتضمن المراحل التكرارية للخوارزمية، التي تعمل في مكانها ، عكس بتات المدخلات أو المخرجات. وبالمثل، يحدث عكس الأرقام في خوارزميات تحويل فورييه السريع (FFT) من نوع كولي-توكي ذات الأساس المختلط. ^{[ 7 ]}

كما تم استخدام تبديل عكس البتات لوضع حدود دنيا في الحوسبة الموزعة. ^{[ 8 ]}

تتكون متتالية فان دير كوربوت ، وهي متتالية منخفضة التباين من الأرقام في الفترة 1 ، من خلال إعادة تفسير مؤشرات تبديل عكس البتات كتمثيلات ثنائية ثابتة النقطة للأعداد النسبية الثنائية .

تُستخدم تباديل عكس البتات غالبًا في إيجاد الحدود الدنيا لهياكل البيانات الديناميكية . على سبيل المثال، مع مراعاة افتراضات معينة، فإن تكلفة البحث عن الأعداد الصحيحة بين${\displaystyle 0}$و${\displaystyle n-1}$، بما في ذلك، في أي شجرة بحث ثنائية تحتوي على تلك القيم، هو${\displaystyle \Omega (n\log n)}$عند الاستعلام عن تلك الأرقام بترتيب معكوس بتيًا. ينطبق هذا الحد حتى على الأشجار مثل الأشجار المتفرعة التي يُسمح لها بإعادة ترتيب عقدها بين عمليات الوصول. ^{[ 9 ]}

وبسبب أهمية خوارزميات تحويل فورييه السريع ، تم ابتكار العديد من الخوارزميات الفعالة لتطبيق تبديل عكس البتات على سلسلة. ^{[ 2 ]}

نظرًا لأن تبديل عكس البتات هو عملية عكسية، يمكن إجراؤه بسهولة في مكانه (دون نسخ البيانات إلى مصفوفة أخرى) عن طريق تبديل أزواج من العناصر. في آلة الوصول العشوائي الشائعة الاستخدام في تحليل الخوارزميات، فإن خوارزمية بسيطة تفحص الفهارس بترتيب الإدخال وتُبدّل كلما صادفت فهرسًا يكون عكسه أكبر، ستُجري عددًا خطيًا من عمليات نقل البيانات. ^{[ 10 ]} مع ذلك، قد يستغرق حساب عكس كل فهرس عددًا غير ثابت من الخطوات. يمكن لخوارزميات بديلة إجراء تبديل عكس البتات في وقت خطي باستخدام حسابات فهارس بسيطة فقط. ^{[ 11 ]} نظرًا لإمكانية تكرار تبديلات عكس البتات عدة مرات كجزء من عملية حسابية، فقد يكون من المفيد فصل خطوات الخوارزمية التي تحسب بيانات الفهرس المستخدمة لتمثيل التبديل (على سبيل المثال، باستخدام طريقة المضاعفة والدمج) عن الخطوات التي تستخدم نتائج هذا الحساب لتبديل البيانات (على سبيل المثال، عن طريق مسح فهارس البيانات بالترتيب وإجراء تبديل كلما كان الموقع المُبدَّل أكبر من الفهرس الحالي، أو باستخدام عمليات تشتيت وتجميع متجهات أكثر تعقيدًا ). ^{​​[ 2 ]}

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

حظي تحسين أداء عمليات عكس البتات باهتمام كبير في مجال الحوسبة عالية الأداء. ويُعدّ تطوير خوارزميات تراعي بنية النظام أمرًا بالغ الأهمية لتمكين الاستخدام الأمثل لموارد الأجهزة وبرامج النظام، مثل الذاكرة المؤقتة (الكاش) وذاكرة الترجمة السريعة (TLB) والمعالجات متعددة النوى. ^{[ 13 ]}