متى يجب استخدام الرقم الأساسي النوع ؟

Question

يبدو Radix نوع جيد جدا متوسط حالة الأداء ، أي O(kN): http://en.wikipedia.org/wiki/Radix_sort

ولكن يبدو أن معظم الناس لا تزال تستخدم سريعة نوعا ما, أليس كذلك ؟

Answer 1

نوع سريع متوسط O(N logN), ولكن كما أن لديها أسوأ الأحوال O(N^2) حتى يرجع ذلك في معظم الحالات العملية أنها لن تحصل على ن^2, هناك دائما خطر أن المدخلات سوف يكون في "النظام السيئ" بالنسبة لك.هذا الخطر لا وجود له في radix النوع.أعتقد أن هذا يعطي ميزة كبيرة radix النوع.

Answer 2

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

Answer 3

التعديل وفقا تعليقاتكم:

• Radix نوع ينطبق فقط على الأعداد الصحيحة الثابتة حجم سلاسل, العائمة نقطة و "أقل من" ، "أكبر من" أو "lexicographic النظام" مقارنة المسندات ، في حين أن المقارنة بين أنواع يمكن أن تستوعب أوامر مختلفة.
• k يمكن أن يكون أكبر من سجل N.
• نوع سريع يمكن القيام به في المكان ، radix النوع يصبح أقل كفاءة.

Answer 4

إجابات أخرى هنا الرهيبة, أنها لا تعطي أمثلة من عند الرقم الأساسي نوع هو في الواقع تستخدم.

مثال على ذلك هو عندما خلق "لاحقة مجموعة" باستخدام الانحراف DC3 خوارزمية (Kärkkäinen-ساندرز-بيركهارت).الخوارزمية هي الخطية فقط إذا خوارزمية الفرز هو الخطية الوقت ، radix النوع هو ضروري ومفيد هنا لأن مفاتيح قصيرة قبل البناء (3-الصفوف من الأعداد الصحيحة).

Answer 5

إلا إذا كان لديك ضخمة قائمة أو صغيرة للغاية مفاتيح, log(N) هو عادة أصغر من ك ، فإنه نادرا ما يكون أعلى من ذلك بكثير.حتى اختيار الأغراض العامة خوارزمية الفرز مع O(N log N) متوسط حالة الأداء لا neccesarily أسوأ من استخدام الجذر النوع.

تصحيح:كما @مهرداد أشار في التعليقات ، حجة أعلاه ليس الصوت:أما المفتاح حجم ثابت ، ثم radix نوع O(N) أو المفتاح حجم k, ثم فرز سريع O(k N log N).لذلك من الناحية النظرية ، radix نوع حقا أفضل مقارب وقت التشغيل.

في الممارسة, أوقات التشغيل سوف تهيمن مصطلحات مثل:

• radix نوع:c1 k N

• فرز سريع:c2 k N log(N)

حيث c1 >> c2, لأن "استخراج" بت من أطول الرئيسية عادة ما تكون باهظة الثمن العملية تنطوي على بعض التحولات و العمليات المنطقية (أو على الأقل محاذاتها ذاكرة الوصول) ، في حين وحدات المعالجة المركزية الحديثة يمكن أن يقارن مع مفاتيح 64, 128 أو حتى 256 بت في عملية واحدة.لذلك لكثير من الحالات الشائعة ، إلا إذا ن عملاق, c1 سيكون أكبر من c2 log(N)

Answer 6

Radix نوع يأخذ O(ك*ن) مرة.ولكن عليك أن تسأل ما هو K.ك هو "عدد الأرقام" (التبسيط قليلا ولكن في الأساس شيء من هذا القبيل).

إذا كم عدد الأرقام لديك ؟ تماما الإجابة أكثر من log(n) (تسجيل الدخول باستخدام "أرقام" حجم قاعدة) مما يجعل الرقم الأساسي خوارزمية O(n log n).

لماذا هذا ؟ إذا كان لديك أقل من log(n) أرقام ، ثم لديك أقل من n عدد ممكن.ومن ثم يمكنك ببساطة استخدام "العد نوع" الذي يأخذ O(n) الوقت (فقط إحصاء عدد كل عدد لديك).لذلك أفترض أن لديك أكثر من ك>log(n) أرقام...

هذا هو السبب في الناس لا تستخدم الرقم الأساسي النوع كثيرا.على الرغم من أن هناك حالات حيث أنه من المفيد استخدامه في معظم الحالات سريعة النوع هو أفضل بكثير.

Answer 7

عندما n > 128 يجب علينا استخدام RadixSort

عند فرز int32s اخترت الرقم 256 ، لذلك ك = سجل(256, 2^32) = 4, وهو أمر مهم أصغر من سجل(2 n)

و في الاختبار ، radix النوع هو 7 مرات أسرع من فرز سريع في أفضل الأحوال.

public class RadixSort {
    private static final int radix=256, shifts[]={8,16,24}, mask=radix-1;
    private final int bar[]=new int[radix];
    private int s[] = new int[65536];//不使用额外的数组t，提高cpu的cache命中率

    public void ensureSort(int len){
        if(s.length < len)
            s = new int[len];
    }   

    public void sort(int[] a){
        int n=a.length;
        ensureSort(n);
        for(int i=0;i<radix;i++)bar[i]=0;
        for(int i=0;i<n;i++)bar[a[i]&mask]++;//bar存放了桶内元素数量
        for(int i=1;i<radix;i++)bar[i]+=bar[i-1];//bar存放了桶内的各个元素在排序结果中的最大下标+1
        for(int i=0;i<n;i++)s[--bar[a[i]&mask]]=a[i];//对桶内元素，在bar中找到下标x=bar[slot]-1, 另s[x]=a[i]（同时--bar[slot]将下标前移，供桶内其它元素使用）

        for(int i=0;i<radix;i++)bar[i]=0;
        for(int i=0;i<n;i++)bar[(s[i]>>8)&mask]++;
        for(int i=1;i<radix;i++)bar[i]+=bar[i-1];
        for(int i=n-1;i>=0;i--)a[--bar[(s[i]>>8)&mask]]=s[i];//同一个桶内的元素，低位已排序，而放入t中时是从t的大下标向小下标放入的，所以应该逆序遍历s[i]来保证原有的顺序不变

        for(int i=0;i<radix;i++)bar[i]=0;
        for(int i=0;i<n;i++)bar[(a[i]>>16)&mask]++;
        for(int i=1;i<radix;i++)bar[i]+=bar[i-1];
        for(int i=n-1;i>=0;i--)s[--bar[(a[i]>>16)&mask]]=a[i];//同一个桶内的元素，低位已排序，而放入t中时是从t的大下标向小下标放入的，所以应该逆序遍历s[i]来保证原有的顺序不变

        for(int i=0;i<radix;i++)bar[i]=0;
        for(int i=0;i<n;i++)bar[(s[i]>>24)&mask]++;
        for(int i=129;i<radix;i++)bar[i]+=bar[i-1];//bar[128~255]是负数，比正数小
        bar[0] += bar[255];
        for(int i=1;i<128;i++)bar[i]+=bar[i-1];     
        for(int i=n-1;i>=0;i--)a[--bar[(s[i]>>24)&mask]]=s[i];//同一个桶内的元素，低位已排序，而放入t中时是从t的大下标向小下标放入的，所以应该逆序遍历s[i]来保证原有的顺序不变      
    }
}

Answer 8

ك = "طول أطول قيمة في صفيف فرز"

n = "طول المصفوفة"

O(k*n) = "أسوأ حالة تشغيل"

ك * ن = ن^2 (إذا كان k = n)

حتى عند استخدام الجذر نوع تأكد "أطول صحيح هو أقصر من حجم الصفيف" أو العكس بالعكس.ثم أنت ذاهب للفوز فرز سريع!

العيب هو:معظم الوقت كنت لا يمكن أن أؤكد كم كبير الصحيحه تصبح, ولكن إذا كان لديك نطاق محدد من الأرقام الرقم الأساسي النوع يجب أن يكون وسيلة للذهاب.

Answer 9

وهنا الرابط الذي يقارن فرز سريع و radixsort:

هو الرقم الأساسي النوع أسرع من فرز سريع لعدد صحيح المصفوفات? (نعم هو, 2-3x)

وهنا رابط آخر الذي يحلل تشغيل مرات عدة خوارزميات:

سؤال من نوع:

وهو أسرع على نفس البيانات ؛ O(n) نوع أو O(nLog(ن)) نوع ؟

الجواب:ذلك يعتمد.ذلك يعتمد على كمية البيانات التي يتم فرزها.ذلك يعتمد على الأجهزة كونها تعمل على, و ذلك يعتمد على تنفيذ خوارزميات.

Answer 10

Radix النوع ليس المقارنة على أساس النوع فقط نوع عددي أنواع مثل الأعداد الصحيحة (بما في ذلك مؤشر عناوين) و النقطة العائمة, و انها قليلا من الصعب portably الدعم النقطة العائمة.

ربما لأنه لديه مثل هذه مجموعة ضيقة من انطباق أن العديد من المكتبات القياسية اختيار إسقاطها.فإنه لا يمكن حتى تمكنك من توفير الخاصة بك المقارنة لأن بعض الناس قد لا يريدون حتى نوع الأعداد الصحيحة مباشرة بقدر ما باستخدام الأعداد الصحيحة كما المؤشرات إلى شيء آخر أن تستخدم مفتاح الفرز مثلاالمقارنة على أساس أنواع تسمح كل هذه المرونة لذلك فمن المحتمل حالة فقط وفضلت المعمم الحل المناسب 99% من احتياجات الناس اليومية بدلا من الخروج من الطريق لتلبية إلى أن 1%.

وقال على الرغم من ضيق تطبيق في المجال العثور على مزيد من استخدام الجذر أنواع من introsorts أو quicksorts.أنا في هذا 1% بالكاد من أي وقت مضى العمل مع سلسلة المفاتيح, ولكن في كثير من الأحيان العثور على حالات الاستخدام الأرقام التي تستفيد من فرز.أنه بسبب تعليمات البرمجة الأساسية تدور حول مؤشرات الكيانات والمكونات (كيان مكون النظام) وكذلك أشياء مثل فهرسة تنسجم و هناك الكثير من البيانات الرقمية.

ونتيجة لذلك ، radix النوع يصبح من المفيد لجميع أنواع الأشياء في حالتي.أحد الأمثلة الشائعة في حالتي هو القضاء على تكرار الأرقام القياسية.في هذه الحالة لا تحتاج حقا نتائج فرز ولكن غالبا ما يكون الرقم الأساسي النوع يمكن القضاء على التكرارات أسرع من البدائل.

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

آخر هو عمق الفرز على مستوى أعلى من الأوليات z شبه السليم الشفافية ألفا إذا نحن لن نفعل ذلك في فرج تظليل.وينطبق ذلك أيضا على واجهات ومكافحة ناقلات الرسومات برنامج z-ترتيب العناصر.

هو آخر مخبأ الصديقة الوصول المتسلسل باستخدام قائمة من المؤشرات.إذا كانت مؤشرات اجتاز عدة مرات ، فإنه غالبا ما يحسن الأداء إذا كنت radix فرزها في وقت مبكر حيث أن اجتياز يتم في ترتيب تسلسلي بدلا من ترتيب عشوائي.هذا الأخير يمكن أن متعرج ذهابا وإيابا في الذاكرة ، طرد البيانات من ذاكرة التخزين المؤقت خطوط فقط إلى تحميل نفس الذاكرة المنطقة مرارا وتكرارا في نفس الحلقة.عندما radix فرز المؤشرات الأولى قبل الوصول إليها مرارا وتكرارا ، أن يتوقف عن أن يحدث وأنا يمكن أن تقلل من ذاكرة التخزين المؤقت يفتقد إلى حد كبير.هذا هو في الواقع أكثر شيوعا استخدام الجذر أنواع وانها مفتاح بلدي ECS كونها ذاكرة التخزين المؤقت الصديقة عندما نظم ترغب في الوصول إلى كيانات مع اثنين أو أكثر من المكونات.

في حالتي لدي مؤشرات الرقم الأساسي النوع التي تستخدم في كثير من الأحيان.بعض المعايير:

--------------------------------------------
- test_mt_sort
--------------------------------------------
Sorting 1,000,000 elements 32 times...

mt_radix_sort: {0.234000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]

std::sort: {1.778000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]

qsort: {2.730000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]

أستطيع أن متوسط شيئا مثل 6-7 ms لفرز مليون الأرقام مرة واحدة على دينكي الأجهزة التي ليس بالسرعة التي أود منذ 6-7 ميلي ثانية لا يزال يمكن أن يكون لاحظت من قبل المستخدمين أحيانا في سياقات تفاعلية, ولكن لا يزال أفضل بكثير من 55-85 ms كما في حالة C++'s std::sort أو ج qsort والتي من شأنها أن تؤدي حتما إلى واضحة جدا السقطات في معدلات الإطار.حتى أنني سمعت من الناس تنفيذ radix أنواع استخدام SIMD, رغم أن ليس لدي أي فكرة كيف تمكنوا من ذلك.أنا لست ذكيا بما يكفي أن تأتي مع مثل هذا الحل ، على الرغم من بلدي ساذجة قليلا radix نوعا ما يفعله بشكل جيد جدا بالمقارنة مع المكتبات القياسية.

Answer 11

مثال: عند فرز مجموعة كبيرة جدا أو مجموعة من الأعداد الصحيحة.وهو الرقم الأساسي نوع وأي أنواع أخرى توزيع أنواع سريعة للغاية منذ عناصر البيانات هي أساسا يجري enqueued إلى مجموعة من قوائم الانتظار(الحد الأقصى 10 طوابير من أجل LSD radix نوع) و إعادة تعيين إلى مختلف مؤشر موقع إدخال نفس البيانات التي يتم فرزها.لا توجد حلقات متداخلة حتى الخوارزمية يميل إلى التصرف أكثر خطيا عدد من إدخال البيانات الصحيحة على أن يتم فرز يصبح أكبر بكثير.على عكس غيرها من أساليب الفرز ، مثل غير فعالة للغاية bubbleSort الأسلوب ، radix النوع لا تنفذ عمليات المقارنة إلى النوع.مجرد عملية بسيطة من الخارطه الصحيحه مختلفة مؤشر المناصب حتى الإدخال أخيرا فرز.إذا كنت ترغب في اختبار من LSD radix نوع لنفسك ، وقد كتبت واحدة وتخزينها على جيثب والتي يمكن بسهولة اختبارها على الانترنت شبيبة ide مثل بليغ جافا سكريبت هو الترميز رمل.لا تتردد للعب مع حولها ومشاهدة كيف يتصرف مع اختلاف الأرقام ن.لقد اختبرت مع ما يصل إلى 900 ، 000 لم يتم فرزها الصحيحه مع وقت التشغيل < 300ms.هنا هو الرابط إذا كنت ترغب في اللعب مع حولها.

https://gist.github.com/StBean/4af58d09021899f14dfa585df6c86df6