بناء QuickSort مع PHP

Question

لقد قرأت مؤخرا عن QuickSort وكانت أتساءل عما إذا كان الأمر ذكيا لبناء وظيفتي الخاصة لفرز الأشياء مع QuickSort أو إذا كان الأمر كذلك سيكون من غير فعال. ما رأيك هو وظيفة فرز مبنية أفضل من وظيفة QuickSort Selfbuilt؟

Answer 1

من عند http://php.net/sort.

ملاحظة: مثل معظم وظائف فرز PHP، يستخدم فرز () تنفيذ »QuickSort.

سيتم تنفيذ وظائف PHP الأساسية في C، بدلا من PHP، لذلك يجب أن تكون بشكل عام أسرع بكثير من أي شيء يمكنك كتابته بنفسك في PHP. ستكون هناك حالات حيث تكون أسرع لكتابة بنفسك، لكنني أعتقد أن هذه ستكون عندما يكون لديك حالة محددة للغاية ويمكنك إجراء تحسينات خاصة بك لذلك. أعتقد أنه من غير المرجح أن يكون الأمر كذلك هنا.

Answer 2

في الواقع، فعلت هذا لنقطة بيانات حول عرض تقديمي، أتعرض معا. يفرز الاختبار مجموعة من 250،000 صحيحة باستخدام وظيفة الفرز الأصلية وتنفيذ خوارزمية QuickSort المكتوبة في PHP. محتويات الصفيف هي بالضبط نفس الشيء بالنسبة لكلا التشغيلين، يتم اختيارها البيانات عشوائية، والوقت المبلغ عنه هو فقط لأداء الفرز، وليس المعالجة الأخرى اللازمة لاستدعاء مترجم فب.

نتائج:

 تنفيذ الفرز الأصلي: 1.379 ثانية تنفيذ QuickSort PHP: 30.615 ثانية

بالتأكيد استخدام التنفيذ الأصلي. يجب أن يكون هذا هو الحال لأي لغة تفسير.

توفر النتائج لللغات الأخرى التي قمت باختبارها بنفس الشروط باستخدام نفس التنفيذ على نفس الأجهزة والنظام التشغيل، مقارنة أداء مثيرة للاهتمام ووضع نتيجة PHP في المنظور:

 ج: 0.107 ثانية جافا: 0.250 ثانية جافا سكريبت (FF3): 4.401 ثانية

بالذكر أن الكروم والسفن السفاري كثيراً بشكل أسرع لاختبار JavaScript، لكنني لا أقوم بتضمين تلك الموجودة هنا لأن هذه الاختبارات تم تسجيلها في بيئة مختلفة.

Answer 3

عصا مع وظيفة الفرز المدمجة. QuickSort عبارة عن خوارزمية بسيطة، ولكن للحصول على أداء جيد على أجهزة الكمبيوتر التي تستخدم في الواقع في الاستخدام قليلا من براعة. إنه أكثر من المحتمل أن تكون الوظيفة المدمجة أكثر أمديا بالفعل من أي شيء ستكتب فيه في فترة زمنية معقولة. (تسرع عامل ثابت من المكتوبة في C بدلا من PHP هو أيضا مفيد.)

إذا كنت تقوم بفرز العديد من العناصر التي تباطأت بها بواسطة وظيفة الفرز، فمن المحتمل أن تفعل شيئا خاطئا. (هذا هو PHP بعد كل شيء. يجب عليك استخدام لغة للأغراض العامة لمعالجة مكثفة البيانات. سيكون من الأسهل كتابة التعليمات البرمجية الخاصة بك، وسيتم تشغيله بشكل أسرع.)

Answer 4

للإشارة هناك تنفيذ PHP هنا:

https://en.wikibooks.org/wiki/algorithm_implementation/sorting/quicksorthphp.

Answer 5

هناك شيء واحد عن PHP Quick Trans (Astort، Arsort، إلخ) هو أنهم يفسدون قيمك المتساوية، وهذا يعني أن القيم مع مفاتيح مختلفة ستقوم بشكل عشوائي المباديل، حتى بين عمليات تشغيل مختلفة. مذهلة أن الرمز يمكن أن ينتج طلبا مختلفا باستخدام نفس البيانات مرارا وتكرارا. في النهاية اضطررت إلى تطبيق فرزتي السريعة الخاصة بي لإزالة هذا الشذوذ.

Answer 6

فقط للمتعة، إليك نسخة مطبقة من QuickSort في PHP وصلت إليها. الحيلة هنا هي تمرير الصفيف المراد فرزها كمرجع.

function partition(&$arr,$leftIndex,$rightIndex)
{
    $pivot=$arr[($leftIndex+$rightIndex)/2];

    while ($leftIndex <= $rightIndex) 
    {        
        while ($arr[$leftIndex] < $pivot)             
                $leftIndex++;
        while ($arr[$rightIndex] > $pivot)
                $rightIndex--;
        if ($leftIndex <= $rightIndex) {  
                $tmp = $arr[$leftIndex];
                $arr[$leftIndex] = $arr[$rightIndex];
                $arr[$rightIndex] = $tmp;
                $leftIndex++;
                $rightIndex--;
        }
    }
    return $leftIndex;
}

function quickSort(&$arr, $leftIndex, $rightIndex)
{
    $index = partition($arr,$leftIndex,$rightIndex);
    if ($leftIndex < $index - 1)
        quickSort($arr, $leftIndex, $index - 1);
    if ($index < $rightIndex)
        quickSort($arr, $index, $rightIndex);
}

Answer 7

يرجى الاطلاع أدناه على الطبقة لتنفيذ الفرز السريع في PHP -

            <?php
            class quickSort{
            /* low  --> Starting index,  high  --> Ending index */
                public $arr;
                public function __construct($arr){
                    $this->arr = $arr;
                }
                public function qsort($low,$high){
                    if($low===null || $high===null){    
                        return false;
                    }
                    if($low < $high){           
                        $pi = $this->partition($low,$high);
                        $this->qsort($low,$pi-1); /*before pivot*/
                        $this->qsort($pi+1,$high); /*before pivot*/
                    }
                }

                /* This function takes last element as pivot, places
                   the pivot element at its correct position in sorted
                    array, and places all smaller (smaller than pivot)
                   to left of pivot and all greater elements to right
                   of pivot */
                public function partition($low,$high){
                    if($low===null || $high===null){
                        return false;
                    }
                    $pivot = $this->arr[$high];
                    $i = $low-1; /*index of smaller element*/

                    for($j = $low; $j <= $high-1; $j++)
                    {
                        // If current element is smaller than or equal to pivot

                        if($this->arr[$j] <= $pivot)
                        {
                            $i++;    // increment index of smaller element
                            $this->swap($i,$j);         
                        }
                    }
                    //swap arr[i + 1] and arr[high])
                    $this->swap($i+1,$high);

                    return $i+1;    
                }

                public function swap($i,$j){
                    $p=$this->arr[$i];
                    $q=$this->arr[$j];
                    $this->arr[$i]=$q;
                    $this->arr[$j]=$p;      
                }
            }
            $arr = array(10, 80, 30, 90, 40, 50, 70);
            $obj = new quickSort($arr);
            $obj->qsort(0,6);
            print_r($obj->arr);


            ?>