1. مقدمة لفرز الجرافة
نوع دلو هو خوارزمية الفرز القائمة على العد. يتمثل مبدأ العمل في تقسيم البيانات إلى عدد محدود من الدلاء ، ثم يتم فرز كل دلو بشكل منفصل (من الممكن استخدام خوارزميات الفرز الأخرى أو الاستمرار في الفرز بطريقة متكررة). عندما يتم توزيع القيم في البيانات المراد فرزها بالتساوي ، يكون تعقيد وقت فرز الجرافة θ (n). يختلف فرز الجرافة عن الفرز السريع ، فهو ليس فرزًا للمقارنة ، ولا يتأثر بالحد الأدنى لتعقيد الوقت O (NLOGN).
يتم فرز الجرافة في الخطوات الأربع التالية:
(1) تعيين عدد ثابت من الدلاء الفارغة.
(2) ضع البيانات في الدلو المقابل.
(3) فرز البيانات في كل دلو غير فارغ.
(4) قم بصق البيانات من الجرافة غير الفارغة للحصول على النتيجة.
يعد فرز الجرافة مناسبًا بشكل أساسي لبيانات عدد صحيح صغير المدى ، ويتم توزيعه بشكل مستقل ومتساوي. كمية البيانات التي يمكن حسابها كبيرة وتفي بالوقت المتوقع الخطي.
2. دليل خوارزمية فرز دلو
على سبيل المثال ، هناك الآن مجموعة من البيانات [7 ، 36 ، 65 ، 56 ، 33 ، 60 ، 110 ، 42 ، 42 ، 94 ، 59 ، 22 ، 83 ، 84 ، 63 ، 77 ، 67 ، 101]. كيفية فرزها من صغيرة إلى كبيرة؟
خطوات العملية:
(1) قم بتعيين عدد الدلاء على 5 دلاء فارغة ، ابحث عن القيمة القصوى 110 والقيمة الدنيا 7 ، ومدى كل دلو هو 20.8 = (110-7+1)/5.
(2) اجتياز البيانات الأصلية ، ضعها في الدلو المقابل مع بنية قائمة مرتبطة. الرقم 7 ، قيمة فهرس الجرافة هي 0 ، صيغة الحساب هي الأرضية ((7 7) / 20.8) ، الرقم 36 ، قيمة فهرس الجرافة هي 1 ، أرضية صيغة الحساب ((36 7) / 20.8).
(3) عند إدخال البيانات على الدلو مع نفس الفهرس في المرة الثانية ، وتحديد حجم الأرقام الحالية والأرقام التي تم إدراجها حديثًا في الدلو ، وأدخلها بالترتيب من اليسار إلى اليمين ، من صغير إلى كبير. على سبيل المثال: عند إدراج الدلو مع الفهرس 2 ، عند إدخال 63 ، يوجد بالفعل 4 أرقام 56 و 59 و 60 و 65 في الجرافة ، ثم يتم إدخال الرقم 63 على يسار 65.
(4) دمج دلاء غير فارغة ، دمج 0 و 1 و 2 و 3 و 4 دلاء بالترتيب من اليسار إلى اليمين.
(5) احصل على بنية نوع الدلو
3. تنفيذ برنامج NodeJS
ليس من الصعب تنفيذ خوارزميات ناضجة مثل فرز دلو. وفقًا للأفكار المذكورة أعلاه ، كتبت برنامجًا بسيطًا لتنفيذها. أشعر أن الجزء الأكثر إزعاجًا هو استخدام JavaScript لمعالجة القائمة المرتبطة.
الرمز الفعلي كما يلي:
'يستخدم حازم'؛//////////////////////////////////////////////////////// ) ) ) ) ) ) ///////////////////////////////////////////////////////////////// SITE ([1،4،1،5،3،2،3،3،2،5،2،8،2،2،1]] ، 5) * SITE ([1،4،1،5،3،2،3،3،2،2،5،2،2،8،9،2،1] ، 5،0،5) */exports.sor = function ، count) العد = العد || (العد> 1؟ العد: 10) ؛ // القاضي الحد الأقصى والحد الأدنى للقيم var min = arr [0] ، max = arr [0] ؛ لـ (var i = 1 ؛ i <arr.length ؛ i ++) {min = min <arr [i]؟ مين: arr [i] ؛ Max = max> arr [i]؟ ماكس: arr [i] ؛ } var delta = (max - min + 1) / count ؛ // console.log (min+"،"+max+"،"+delta) ؛ // تهيئة دلو الجرافات var = [] ؛ // بيانات التخزين إلى دلو لـ (var i = 0 ؛ i <arr.length ؛ i ++) {var idx = math.floor ((arr [i] - min) /delta) ؛ // فهرس دلو if (دلو [idx]) {// دلو غير فارغ var bucket = buckets [idx] ؛ var insert = false ؛ // أدخل حجر العلم l.retraversal (دلو ، الدالة (العنصر ، تم) {if (arr [i] <= item.v) {// أصغر من ، إدراج l.append (العنصر ، _val (arr [i])) ؛ insert = true ؛ inse () ؛ // exit traversal}}) ؛ if (! insert) {// أكبر من ، إدراج l.append (دلو ، _val (arr [i])) ؛ }} else {// bucket var bucket = l.init () ؛ l.append (دلو ، _val (arr [i])) ؛ دلاء [idx] = دلو ؛ // تنفيذ قائمة الارتباط}} var result = [] ؛ لـ (var i = 0 ، j = 0 ؛ i <count ؛ i ++) {l.retraversal (buckets [i] ، function (item) {// console.log (i+": } نتيجة الإرجاع ؛} // وظيفة كائن تخزين قائمة المرتبطة _val (v) {return {v: v}}تشغيل البرنامج:
var algo = require ('./ index.js') ؛ var data = [7 ، 36 ، 65 ، 56 ، 33 ، 60 ، 110 ، 42 ، 42 ، 94 ، 59 ، 22 ، 83 ، 84 ، 63 ، 77 ، 67 ، 101] ؛ console.log (data) ؛ console. console.log (algo.bucketsort.sort (البيانات ، 10)) ؛ // 10 دلاءالإخراج:
7 ، 22 ، 33 ، 36 ، 42 ، 42 ، 56 ، 67 ، 67 ، 77 ، 83 ، 84 ، 94 ، 101 ، 110] [7 ، 22 ، 33 ، 36 ، 42 ، 42 ، 63 ، 65 ، 67 ، 77 ، 83 ، 84 ، 94 ، 101 ، 110] [7 ، 22 ، 33 ، 36 ، 42 ، 42 ، 56 ، 59 ، 60 ، 63 ، 65 ، 67 ، 77 ، 83 ، 84 ، 94 ، 101 ، 110] 84 ، 94 ، 101 ، 110] [7 ، 22 ، 33 ، 36 ، 42 ، 42 ، 56 ، 59 ، 60 ، 63 ، 65 ، 67 ، 77 ، 83 ، 84 ، 94 ، 101 ، 110] [7 ، 22 ، 33 ، 36 ، 42 ،
ما يجب شرحه هو:
(1) يمكن تنفيذ الفرز في الدلو أثناء عملية الإدراج كما هو موضح في البرنامج ؛ أو يمكن إدراجها دون الفرز ، ثم فرزها أثناء عملية الدمج ، ويمكن استدعاء الفرز السريع.
(2) قائمة مرتبطة. في واجهة برمجة التطبيقات الأساسية للعقدة ، هناك تطبيق للقائمة المرتبطة. لم أستخدمه مباشرة ، لكنني أسميها من خلال حزمة LinkList: https://github.com/nodejs/node-v0.x-archive/blob/master/lib/_linklist.js
4. الحالة: إحصائيات فرز الجرافات حول درجات امتحان القبول في الكلية
أحد أشهر سيناريوهات التطبيق لفرز الجرافات هو حساب عشرات امتحان القبول في الكلية. عدد المرشحين لامتحان القبول في الكلية الوطنية في عام واحد هو 9 ملايين ، والنتائج قياسية ، مع ما لا يقل عن 200 و 900 كحد أقصى. لا يوجد عشري. إذا تم فرز هذه الأرقام الـ 9 ملايين ، فماذا يجب أن نفعل؟
تحليل الخوارزمية:
(1) إذا كنت تستخدم الفرز المستند إلى المقارنة ، والفرز السريع ، فإن متوسط تعقيد الوقت هو O (nlogn) = O (9000000*log9000000) = 144114616 = 144 مليون مقارنة.
(2) إذا كنت تستخدم الفرز المستند إلى العد ، وفرز الجرافة ، والتعقيد المتوسط ، يمكنك التحكم في التعقيد الخطي. عند إنشاء 700 دلو ، دلو واحد من 200 دقيقة إلى 900 دقيقة ، O (n) = O (90000000) ، فإنه يعادل مسح 900 واط من البيانات مرة واحدة.
ندير برنامجًا لمقارنة فرز الفرز السريع وفرز الجرافة في وقت واحد.
// قم بإنشاء قطعة 100 واط من البيانات في [200،900] فاصل زمني مغلق data = algo.data.randomdata (1000*1000،200،900) ؛ var s1 = تاريخ جديد (). getTime () دلاء var s3 = new date (). getTime () ؛ console.log ("وقت Quicksort: ٪ sms" ، s2-s1) ؛ console.log ("دلو الوقت: ٪ sms" ، S3-S2) ؛الإخراج:
وقت Quicksort: 14768msbucket الوقت: 1089ms
لذلك ، بالنسبة لحالة تسجيل امتحان القبول في الكلية ، فإن فرز دلو أكثر ملاءمة! سيؤدي استخدامنا للخوارزميات المناسبة في السيناريوهات المناسبة إلى تحقيق تحسينات في الأداء على البرنامج خارج الأجهزة.
5. تحليل تكلفة فرز الجرافة
لكن...
يستخدم فرز الجرافة علاقة تعيين الوظائف ، مما يقلل من جميع أعمال المقارنة تقريبًا. في الواقع ، فإن حساب قيمة F (k) لفرز الجرافة تعادل القسم بالترتيب السريع ، وقسمت كمية كبيرة من البيانات إلى كتل البيانات المطلوبة بشكل أساسي (دلاء). ثم تحتاج فقط إلى إجراء مقارنات متقدمة وفرز كمية صغيرة من البيانات في الدلو.
يتم تقسيم التعقيد الزمني لفرز الدلو n الكلمات الرئيسية إلى جزأين:
(1) حلقة لحساب وظيفة تعيين الجرافة لكل كلمة رئيسية ، وهذا التعقيد هذا الوقت هو o (n).
(2) استخدم خوارزمية فرز المقارنة المتقدمة لفرز جميع البيانات في كل دلو ، مع تعقيد زمني لـ ∑o (ni*logni). حيث Ni هو كمية بيانات الدلو I-Th.
من الواضح ، الجزء (2) هو المحدد لأداء فرز الجرافة. إن تقليل كمية البيانات في الدلو هو الطريقة الوحيدة لتحسين الكفاءة (لأن أفضل تعقيد وقت متوسط استناد على فرز المقارنة يمكن أن يصل فقط إلى O (n*logn)). لذلك ، نحتاج إلى بذل قصارى جهدنا للقيام بالنقطتين التاليتين:
(1) يمكن لدالة التعيين f (k) تخصيص بيانات n إلى دلاء M بالتساوي ، بحيث يكون لكل دلو أحجام بيانات [n/m].
(2) حاول زيادة عدد البراميل. في الحالة القصوى ، يمكن لكل دلو الحصول على بيانات واحدة فقط ، والتي تتجنب تمامًا تشغيل "مقارنة" تشغيل البيانات في الدلو. بالطبع ، ليس من السهل القيام بذلك. عندما تكون كمية البيانات ضخمة ، فإن وظيفة f (k) ستجعل عدد مجموعات الجرافات ضخمة وتكون نفايات الفضاء خطيرة. هذه مفاضلة بين تكلفة الزمان والمكان.
لكي يتم فرز بيانات N ودلوال M ، فإن متوسط تعقيد وقت فرز الجرافة لكل بيانات دلو [N/M] هو:
o (n)+o (m*(n/m)*log (n/m)) = o (n+n*(logn-logm)) = o (n+n*logn-n*logm)
عندما n = m ، هذا هو ، عندما يكون هناك بيانات واحدة فقط لكل دلو تحت الحد. يمكن أن تصل أفضل كفاءة لفرز الجرافة إلى O (N).
6. ملخص
متوسط تعقيد الوقت لفرز الجرافة هو خطي O (n+c) ، حيث c = n*(logn-logm). إذا كان عدد البراميل M أكبر بالنسبة لنفس N ، فكلما ارتفعت كفاءته ، وأفضل تعقيد الوقت يصل إلى O (N). بالطبع ، تعقيد الفضاء لفرز الجرافة هو O (n+m). إذا كانت بيانات الإدخال كبيرة جدًا وكان عدد الدلاء كبيرًا جدًا ، فإن تكلفة المساحة باهظة الثمن بلا شك. بالإضافة إلى ذلك ، فإن نوع الدلو مستقر.
في الواقع ، لدي شعور آخر: من بين خوارزميات البحث ، فإن أفضل تعقيد وقت لخوارزمية البحث المستندة إلى المقارنة هو O (logn). على سبيل المثال ، فإن البحث نصف الدعامة ، والأشجار الثنائية المتوازنة ، والأشجار الحمراء والأسود ، وما إلى ذلك ، ومع ذلك ، فإن جدول التجزئة له كفاءة البحث الخطي O (ج) (تصل كفاءة البحث إلى O (1) في حالة عدم وجود تعارض). دعونا نلقي نظرة جيدة على: هل الأفكار وفرز دلو لجداول التجزئة نفس الأغنية؟