ترتيب LSD لحركة البت (ترتيب الجذر)

نشرت مؤخرا العديد من المقالات حول خوارزميات الفرز المختلفة ومقارنتها ، قررت أن أجعل مني خمسة سنتات.

أريد أن أخبركم عن الخوارزمية المفضلة لفرز LSD (معدل الأرقام الأقل أهمية - أولًا البتة الأقل أهمية) مع العد (ترتيب الفرز). تم إعادة النظر في الخوارزمية الكلاسيكية إلى حد ما من قبل المؤلف نحو بعض التحسينات لصالح التسارع والبساطة.

لذلك ، الفرز المقترح مستدام. سنقوم بفرز عدد صحيح 32 بت. للعمل ، تحتاج إلى ذاكرة (~ + 4 كيلوبايت) إضافية ، وهو أمر يضيع إلى حد ما ، ولكنه يتيح لك تحقيق بعض الزيادة في الأداء.

في هذا النوع من LSD ، لا تستخدم المقارنات والتبادلات ، الخوارزمية خطية تمامًا. التعقيد الحسابي O (N).

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

يتم الفرز محليًا لحفظ الذاكرة.

//================================================== // RADIX  (  by rebuilder) //   ,  . //   (n),   ~(n+4k) //================================================== procedure RSort(var m: array of Longword); //-------------------------------------------------- procedure Sort_step(var source, dest, offset: array of Longword; const num: Byte); var i,temp : Longword; k : Byte; begin for i := High(source) downto 0 do begin temp := source[i]; k := temp SHR num; dec(offset[k]); dest[offset[k]] := temp; end; end; //-------------------------------------------------- //    ,     var s : array[0..3] of array[0..255] of Longword; i,k : longword; //     k offset : array[0..3] of byte absolute k; m_temp : array of Longword; begin SetLength(m_temp, Length(m)); //    FillChar(s[0], 256 * 4 * SizeOf(Longword), 0); //   for i := 0 to High(m) do begin k := m[i]; Inc(s[0,offset[0]]); Inc(s[1,offset[1]]); Inc(s[2,offset[2]]); Inc(s[3,offset[3]]); end; //     for i := 1 to 255 do begin Inc(s[0,i], s[0,i-1]); Inc(s[1,i], s[1,i-1]); Inc(s[2,i], s[2,i-1]); Inc(s[3,i], s[3,i-1]); end; //         Sort_step(m, m_temp, s[0], 0); Sort_step(m_temp, m, s[1], 8); Sort_step(m, m_temp, s[2], 16); Sort_step(m_temp, m, s[3], 24); SetLength(m_temp, 0); end; //================================================== ... SetLength(m, n); for i := 0 to n - 1 do m[i] := Random(65536 * 65536); ... RSort(m); ... 

الرمز مكتوب باللغة Pascal ، لكن لن يكون من الصعب نقله إلى أي لغة مناسبة لك.

يتكون تسلسل التنفيذ من مرحلتين:

1. لكل كتلة (ثمانية أرقام ثنائية - 1 بايت (القيمة المثلى)) ، عن طريق العد ، يتم حساب موضعها في صفيف جديد.
2. بالتتابع لكل كتلة (من الأقل أهمية إلى الأعلى) ، ينتقل إلى الموضع المحسوب مسبقًا.

التحسينات:

1. بالنسبة لمجموعة من الإزاحات ، نستخدم المحاذاة في الذاكرة ، وبسبب الحجم الصغير الذي تم وضعه في L1 - ذاكرة التخزين المؤقت للمعالج.
2. يتم ملء صفيف الإزاحة على الفور لجميع الأرقام ، مما يسمح لك بالتجول في الصفيف لإجراء العد مرة واحدة فقط.
3. لا يبدأ حساب الموضع من رأس الصفيف ، ولكن من النهاية ، يحل هذا مشكلتين:
   
   • نهاية الصفيف في الممر الأول موجودة بالفعل في ذاكرة التخزين المؤقت "المحسنة" ، والتي مع صفائف كبيرة تعطي تسارعًا بسيطًا ؛
   • ثانياً ، تكون الدورة التنازلية إلى الصفر أقصر بواسطة تعليمة مجمع واحد ، في كل خطوة من مراحل الدورة ، بالنسبة إلى الدورة الصعودية.
4. لكل تكرار (من أصل أربعة) ، لا يتم استخدام حلقة متداخلة ، وإن كانت أقل جمالا ، ولكن يتم حفظ العديد من إرشادات المعالج الأخرى.

بسبب بساطته ، يكون الرمز متطابقًا تقريبًا في السرعة لكل من برنامج التحويل البرمجي 32 و 64 بت. إذا لزم الأمر ، فمن السهل أن نتخيل نسخة من الخوارزمية لأرقام 16 و 64 بت.

مقارنة خوارزمية أخذ العينات العشوائية مع الفرز السريع على منصة 64 بت (في المتوسط ​​، عشر تمريرات لكل منهما).



نرحب بالاقتراحات والتعليقات المتعلقة بالتحسينات.

شكرا لك