4

Radix Sort تَنْفِيذي على لغة JavaScript

  • KernelCode

ماهي خوارزمية Radix Sort ؟

هي خورزميه يرجع عمرها الى 1887 عمل العالم : Herman Hollerith لاتعتمد على مقارنه القيم بل ترتب الارقام بالاعتماد على

مفاتيح للارقام الصحيحه من 0 الى 9 بالاعتماد على القيمه القصوى للرقم Least Significant Digit (LSD) او Most Significant Digit (MSD) وهي تعتبر من اسرع الخوارزمات الموجوده .

مقارنة السرعه بين الخوارزميات :

http://bigocheatsheet.com

معلومات اكثر :

https://en.wikipedia.org/wi...

الخوارزميه تم تنفيذها في لغة javascript .

الخوارزمية :

(function(){
    // mv - the maximum possible position of number in the array
    // ua - unsorted array

    function RadixSort(mv,ua){

        // part of the algorithm to get the position of the 
        var n = 1;

        // a 0 to 9 linked list queues FIFO
        var ll = Array(10);

        for(var i = 0; i < ll.length; i++ ){
            ll[i] = [];
        }

        // keep multiplying m and n until we sort the array!
        for( var m=10; m < mv; m *= 10, n *= 10 ){

            // push the number in array to our queue
            for( var i = 0; i < ua.length; i++ ){

                ll[ Math.floor( (ua[i] % m) / n) ].push( ua[i] );
            }

            // replace the arry with new values 
            var uai=0;

            for(var i=0;i<ll.length;i++){

                var cl = ll[i];

                while(cl.length>0){

                    var v = cl.shift();
                    ua[uai] = v;
                    uai++;

                }
            }

        }
        // return the new sorted array 
        return ua;
    }

    //create Random Array 
    function getRandomInt(min, max) {
        return Math.floor(Math.random() * (max - min + 1)) + min;
    }
    var ary=[];
    var max = 10000;
    var len = 700000;
    for(var i = 0 ;i<len;i++){
        ary.push(getRandomInt(10,max));
    }

    //Test Radix Sort 
    var start = new Date().getTime();

    RadixSort(max*10,ary);

    var end = new Date().getTime();
    var time = end - start;
    console.log('Radix Sort Time : ');
    console.log('Array Length = '+ary.length+',Execution time: ' + time);


    //Test Default Javascript Native Sort

    var ary2=[];
    for(var i = 0 ;i<len;i++){
        ary2.push(getRandomInt(10,max));
    }

    var start = new Date().getTime();

    RadixSort(max*10,ary);

    var end = new Date().getTime();
    var time = end - start;
    ary.sort();
    console.log('Default Javascript Sort Time: ');
    console.log('Array Length = '+ary.length+',Execution time: ' + time);

})();

Github :

يمكنك مشاهده كيفيه عمل الخوارزميه من هنا :

https://www.cs.usfca.edu/~g...
يرجى الدخول لحسابك أو تسجيل حساب لتستطيع إضافة تعليق
حساب جديد دخول

التعليقات

1
يوسف سيد أضف ردا

الخورزمية جيّدة، أريح بالي دائمًا وأستخدم quicksort :) مع أنها قد لا تكون الأفضل في كل الاستخدامات، ماذا تستخدم؟ وبمناسبة السرعة على الكثير من بيئات JS قد يكون استخدام sort القياسية أفضل من كتابة خوازرمية أخرى حتى ولو كانت أفضل، بعكس محركات كـV8 قد تتشابه بالـNative.

للمناسبة دخلتُ إلى حسابك على سبيل الفائدة والإطلاع؛ انتهى بي الأمر هنا:

لم ألعب لعبة مذ زمن :) لعبة بسيطة لكن جميلة :)

على الجانب لدي ملاحظتان ليستا مهمتين:

  1. لا أعرف التصميم الذي تعتمده في الـComments خصوصًا قبل الدالة، يوجد بعض الأدوات تساعد أثناء الكتابة وأخرى للتعرف على الشيفرة مثلًا لمعرفة الأنواع الصحيحة وإخراج الأخطاء لذا أظنُ عندما تكتب تلك الملاحظات يجب اتباعها إن كنت تريد مساعدة من سيستخدم الشيفرة :)، وأيضًا التصميم في الشيفرة لم أره من قبل فقط من أجل جماليات حمقاء -يقولون لتجعل الشيفرة قابلة للقراءة-.

  2. لما لم توفر عناء حساب وقت العمل وتستخدم console.time؟ ليست تعمل على كل المتصفحات لكنها كافية فيما يخص تجربة الشيفرة:

ـ

console.time("mytest");
var str = "string allocation!";
console.timeEnd("mytest");

يوجد بعض من العمليات البرمجية الممكن اختصارها من الشيفرة ماذا ترى؟

2
KernelCode أضف ردا

الخورزمية جيّدة، أريح بالي دائمًا وأستخدم quicksort :) مع أنها قد لا تكون الأفضل في كل الاستخدامات، ماذا تستخدم؟ وبمناسبة السرعة على الكثير من بيئات JS قد يكون استخدام sort القياسية أفضل من كتابة خوازرمية أخرى حتى ولو كانت أفضل، بعكس محركات كـV8 قد تتشابه بالـNative.

الـ quicksort رائعه بالفعل تستخدم المقارنه بالتقسيم والجمع .. انا استخدم الmergsort غالباً وكذالك ال javascript sort تستخدم خوارزميه mergsort .. قمت بتنفيذه ال Radix Sort لاعجابي بسرعتها بدون مقارنه بين القيم !! شاهد هذا الفيديو الرائع جدا! :

xD يكفي فقط الصوت للخوارزميه -جرانديزر يستعد للتحليق عالياً-

للمناسبة دخلتُ إلى حسابك على سبيل الفائدة والإطلاع؛ انتهى بي الأمر هنا:

لم ألعب لعبة مذ زمن :) لعبة بسيطة لكن جميلة :)

شكراً على تجربه اللعبه .. هذه اللعبة قمت بعمل نسخه ثلاثيه الابعاد منها ولم انشرها بعد ربما لم يحن الموعد لنشرها (تحتاج الكثير من التعديل) .. عندما انشرها ساذكرك في الموضوع لتجربها ربما تعجبك ايضاً :) .

لا أعرف التصميم الذي تعتمده في الـComments خصوصًا قبل الدالة، يوجد بعض الأدوات تساعد أثناء الكتابة وأخرى للتعرف على الشيفرة مثلًا لمعرفة الأنواع الصحيحة وإخراج الأخطاء لذا أظنُ عندما تكتب تلك الملاحظات يجب اتباعها إن كنت تريد مساعدة من سيستخدم الشيفرة :)، وأيضًا التصميم في الشيفرة لم أره من قبل فقط من أجل جماليات حمقاء -يقولون لتجعل الشيفرة قابلة للقراءة-.

شكراً على النصيحه .. صراحه لاهتم كثيراً بكتابه التعليقات و ال docs للاكواد التي اقوم بها للمتعه .. لاكن في اعمالي التجاريه استخدم عدة برامج مثل phpdoc.org , في هذه الخوارزميه بذات قمت بكتابها سريعاً لكي اطبقها واختبر سرعتها لذالك لم اهتم باسماء المتغيرات وكذالك يوجد بعض التعديلات .

لما لم توفر عناء حساب وقت العمل وتستخدم console.time؟ ليست تعمل على كل المتصفحات لكنها كافية فيما يخص تجربة الشيفرة:

لم اكن اعرف هذه الداله الرائعه ساقوم باستخدامها في المره القادمه :) .

يوجد بعض من العمليات البرمجية الممكن اختصارها من الشيفرة ماذا ترى؟

نعم مثلاً يمكنك استخدام ال Bitwise operations بدل استخدام ال linked list queue .

1
يوسف سيد أضف ردا

يبدو أنه كان لديك مشكلة في حساب الوقت، لاحظ أنّك تستخدم دالتك مرة أخرى في وقت الافتراضية، عدلتُ الجزء الأخير إلى:

var ary=[];
var max = 10000;
var len = 700000;
for(var i = 0 ;i<len;i++){
    ary.push(getRandomInt(10,max));
}

//Test Radix Sort

console.time("RadixSort");
RadixSort(max*10,ary);
console.timeEnd("RadixSort");


//Test Default Javascript Native Sort

var ary2=[];
for(var i = 0 ;i<len;i++){
    ary2.push(getRandomInt(10,max));
}

console.time("Array.sort");
ary2.sort();
console.timeEnd("Array.sort");

الـNative كانت أسرع على V8:

RadixSort: 3806.000ms
Array.sort: 1676.000ms
1
KernelCode أضف ردا

الـNative كانت أسرع على V8

لماذا بعتقادك ؟ D: .

1
يوسف سيد أضف ردا

عملية التفسير والترجمة بداخل المحرك تأخذ بعض الوقت، ربما تكون أسرع بالـWebAssembly أسرع في التفسير بداخل المحرّك.