ज्यादातर PHP डेवलपर (और स्वयं सिखाया गया) होने के नाते, मेरे पास वास्तव में एल्गोरिदम को सॉर्ट करने जैसी चीज़ों के पीछे एल्गोरिदम को जानने या समझने का कोई कारण नहीं था, सिवाय इसके कि क्विकॉर्ट औसतन सबसे तेज़ है, और यह आमतौर पर PHP के सॉर्ट फ़ंक्शंस के पीछे एल्गोरिदम है।

लेकिन मेरे पास एक लंबित साक्षात्कार जल्द ही आ रहा है, और वे इस तरह के बुनियादी एल्गोरिदम को समझने की सलाह देते हैं। इसलिए मैंने खुला तोड़ दिया http://www.geeksforgeeks.org/quick-sort/ और अपने स्वयं के QuickSort और विभाजन कार्यों को लागू किया, निश्चित रूप से अभ्यास के लिए, एक सरणी को इसके मूल्यों में से एक द्वारा क्रमबद्ध करने के लिए। मैं इसके साथ आया (मैं PHP 7.1 का उपयोग कर रहा हूं, इसलिए वाक्यविन्यास का एक अच्छा सा अपेक्षाकृत नया है)

function Partition(array &$Array, $Column, int $Low, int $High): int {
    $Pivot = $Array[$High][$Column];

    $i = $Low - 1;

    for ($j = $Low; $j <= $High - 1; $j++) {
        if ($Array[$j][$Column] > $Pivot) {
            $i++;
            [$Array[$i], $Array[$j]] = [$Array[$j], $Array[$i]];
        }
    }

    [$Array[$i + 1], $Array[$High]] = [$Array[$High], $Array[$i + 1]];
    return $i + 1;
}

function QuickSort(array &$Array, $Column, int $Low = 0, ?int $High = null): void {
    $High = $High ?? (count($Array) - 1);

    if ($Low < $High) {
        $PartitionIndex = Partition($Array, $Column, $Low, $High);

        QuickSort($Array, $Column, $Low, $PartitionIndex - 1);
        QuickSort($Array, $Column, $PartitionIndex + 1, $High);
    }
}

और यह काम करता है! विस्मयकारी! और इसलिए मैंने सोचा, इसका उपयोग करने के लिए कोई वास्तविक बिंदु नहीं है, क्योंकि इस एल्गोरिदम का PHP व्याख्या किया गया संस्करण संकलित सी संस्करण से तेज़ नहीं है (जैसे कि usort में क्या उपयोग किया जाएगा)। लेकिन इसके लिए, मैंने दो दृष्टिकोणों को बेंचमार्क करने का फैसला किया।

और मेरे आश्चर्य के लिए, मेरा तेज़ है!

$Tries = 1000;
$_Actions = $Actions;

$Start = microtime(true);
for ($i = 0; $i < $Tries; $i++) {
    $Actions = $_Actions;
    usort($Actions, function($a, $b) {
        return $b['Timestamp'] <=> $a['Timestamp'];
    });
}
echo microtime(true) - $Start, "\n";

$Start = microtime(true);
for ($i = 0; $i < $Tries; $i++) {
    $Actions = $_Actions;
    QuickSort($Actions, 'Timestamp');
}
echo microtime(true) - $Start, "\n";

यह मुझे पहले के लिए 1.274071931839 और दूसरे के लिए 0.87327885627747 के आसपास लगातार संख्या देता है।

क्या कोई मूर्खतापूर्ण बात है जो मुझे याद आ रही है जो इसका कारण बनेगी? क्या usort वास्तव में Quicksort के कार्यान्वयन का उपयोग नहीं करता है? क्या ऐसा इसलिए है क्योंकि मैं सरणी कुंजियों को ध्यान में नहीं रख रहा हूं (मेरे मामले में मुझे वही रहने के लिए कुंजी/मूल्य जोड़े की आवश्यकता नहीं है)?


बस अगर कोई PHP में समाप्त क्विकॉर्ट फ़ंक्शन चाहता है, तो मैंने यही समाप्त किया है, जो मूल usort के रूप में लगभग आधे समय में कॉलम, अवरोही द्वारा सरणी को सॉर्ट करता है। (पुनरावर्ती, पुनरावर्ती नहीं, और विभाजन फ़ंक्शन भी इनलाइन था)

function array_column_sort_QuickSort_desc(array &$Array, $Column, int $Start = 0, int $End = null): void {
    $End = $End ?? (count($Array) - 1);

    $Stack = [];
    $Top = 0;

    $Stack[$Top++] = $Start;
    $Stack[$Top++] = $End;

    while ($Top > 0) {
        $End = $Stack[--$Top];
        $Start = $Stack[--$Top];

        if ($Start < $End) {
            $Pivot = $Array[$End][$Column];

            $PartitionIndex = $Start;

            for ($i = $Start; $i < $End; $i++) {
                if ($Array[$i][$Column] >= $Pivot) {
                    [$Array[$i], $Array[$PartitionIndex]] = [$Array[$PartitionIndex], $Array[$i]];
                    $PartitionIndex++;
                }
            }

            [$Array[$End], $Array[$PartitionIndex]] = [$Array[$PartitionIndex], $Array[$End]];

            $Stack[$Top++] = $Start;
            $Stack[$Top++] = $PartitionIndex - 1;

            $Stack[$Top++] = $PartitionIndex + 1;
            $Stack[$Top++] = $End;
        }
    }
}
4
Brian Leishman 16 अक्टूबर 2017, 20:29
$Actionsमें कितनी प्रविष्टियां हैं?
 – 
NineBerry
16 अक्टूबर 2017, 20:41
इस विशिष्ट मामले में, 198.
 – 
Brian Leishman
16 अक्टूबर 2017, 20:41
अगर मैं इसे एक ही प्रयास के लिए 20183 तत्व देता हूं तो मुझे क्रमशः 0.24767899513245 और 0.15674591064453 मिलते हैं
 – 
Brian Leishman
16 अक्टूबर 2017, 20:46

1 उत्तर

सबसे बढ़िया उत्तर

आप अपने QuickSort को दिए गए तर्कों और usort() को दिए गए तर्कों के बीच अंतर पर विचार करें। usort() में एक अधिक सामान्य इंटरफ़ेस है, जो एक तुलना फ़ंक्शन के संदर्भ में संचालित होता है। आपका QuickSort आपके विशेष प्रकार के डेटा के लिए और > ऑपरेटर के माध्यम से तुलना करने के लिए विशिष्ट है।

बहुत संभव है, प्रदर्शन में अंतर व्यक्तिगत > संचालन के मूल्यांकन के सापेक्ष फ़ंक्शन कॉल के मूल्यांकन की बहुत अधिक लागत के कारण है। यह अंतर किसी भी अंतर्निहित दक्षता लाभ को आसानी से बदल सकता है जो usort() हो सकता है। इसके अलावा, इस पर विचार करें, क्योंकि यह PHP में लिखे गए एक तुलना फ़ंक्शन पर निर्भर करता है, usort() के संचालन में बहुत सारे PHP चलाना शामिल है, न कि केवल संकलित C कोड।

यदि आप इसे और अधिक एक्सप्लोर करना चाहते हैं तो उसी इंटरफ़ेस को प्रस्तुत करने के लिए अपने कार्यान्वयन को संशोधित करने पर विचार करें जो usort() करता है। मैं यह अनुमान लगाने के लिए इच्छुक हूं कि usort() इस तरह के एक हाथ से लुढ़का हुआ बदलाव के साथ एक सेब-से-सेब की तुलना में जीत जाएगा, लेकिन प्रदर्शन की भविष्यवाणी करना बेहद मुश्किल है। यही कारण है कि हम परीक्षण करते हैं।

2
John Bollinger 16 अक्टूबर 2017, 20:48
यह निश्चित रूप से समझ में आता है। मैंने अपने दिमाग में यह भी योजना बनाने की कोशिश करना शुरू कर दिया था कि एक पूर्ण उपयोगकर्ता-शैली के फ़ंक्शन को कैसे लिखा जाए और यह वास्तविक रूप से जटिल हो गया। तो मुझे लगता है कि अब मेरे पास कॉलम द्वारा कुंजी-कम सरणी को सॉर्ट करने का एक तेज़ तरीका है :)
 – 
Brian Leishman
16 अक्टूबर 2017, 21:09