मेरा पसंदीदा एल्गोरिदम: linear-time median finding (2018)

 (rcoh.me)
2 पॉइंट द्वारा GN⁺ 2024-07-26 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • Median को sort करके आसानी से निकाला जा सकता है, लेकिन sorting cost के कारण single element selection problem में भी O(n log n) की सीमा लग जाती है
  • quickselect केवल ज़रूरी हिस्से को recursively search करके average O(n) में kth element या median ढूंढ सकता है
  • Random pivot practical use में अच्छा काम करता है, लेकिन अगर लगातार खराब pivot चुने जाएं, तो हर बार केवल एक element हटता है और complexity O(n²) तक बिगड़ सकती है
  • median-of-medians 5-5 के groups के medians में से फिर median चुनता है, जिससे worst case में भी कम-से-कम 30% elements हटाए जा सकते हैं
  • वास्तविक implementation में pivot calculation cost ज्यादा हो सकती है, इसलिए C++ standard library की तरह quickselect और heapselect को combine करने वाला introselect ज्यादा practical choice हो सकता है

Sorting से median खोजने की सीमा

  • Median निकालने का सबसे सरल तरीका list को sort करने के बाद middle index की value चुनना है
  • Odd length वाली list में बीच का element return किया जाता है, और even length वाली list में बीच के दो elements का average return किया जाता है
  • Comparison-based sorting की सबसे तेज time complexity O(n log n) है, इसलिए इस approach का running time भी sorting से dominate होता है
  • Code सरल होने का फायदा है, लेकिन सिर्फ एक median खोजने के लिए यह जरूरत से ज्यादा काम करता है

Average O(n) बनाने वाला quickselect

  • quickselect Tony Hoare द्वारा बनाया गया recursive algorithm है, और यह median के अलावा list का कोई भी kth element खोज सकता है
  • इसका basic flow pivot के आधार पर list को split करने के बाद केवल उसी side को लगातार search करना है जिसमें kth element है
    • List में से एक pivot चुनें
    • List को pivot से छोटे या बराबर elements और pivot से बड़े elements में बांटें
    • जिस kth element को खोज रहे हैं वह किस side में है, यह तय करके केवल उस sublist पर recursive call करें
    • Right sublist में जाते समय पहले से exclude किए गए left elements की संख्या के हिसाब से k value adjust करें
  • Example list [9,1,0,2,3,4,6,8,7,10,5] में length 11 है, इसलिए 6th smallest element खोजते हैं, और pivot के हिसाब से range narrow करके अंत में 5 return होता है
  • quickselect_median में अगर list length odd है तो एक middle index को quickselect से खोजा जाता है, और अगर even है तो बीच के दो indices खोजकर उनका average निकाला जाता है
  • अगर pivot list को लगभग आधा-आधा बांटता है, तो workload n + n/2 + n/4 + ... = 2n हो जाता है, यानी O(n)

Worst case से बचने के लिए अच्छा pivot चाहिए

  • quickselect का average O(n) इस assumption पर निर्भर करता है कि pivot selection पर्याप्त अच्छा है
  • अगर बदकिस्मती से हर step पर maximum value को pivot चुना जाए, तो हर step में केवल एक element हटता है और complexity O(n²) हो जाती है
  • Worst case में भी linear time guarantee करने के लिए, quickselect को linear time में पर्याप्त अच्छा pivot देना होगा
  • यह pivot selection algorithm 1973 में Blum, Floyd, Pratt, Rivest, Tarjan ने develop किया था, और संबंधित paper 1973 paper पर उपलब्ध है

median-of-medians pivot selection

  • median-of-medians quickselect के लिए अच्छा pivot चुनने की प्रक्रिया है
  • Implementation flow इस प्रकार है
    • अगर elements 5 से कम हैं, तो existing sorting-based median function का उपयोग करें
    • List को 5-5 elements के groups में बांटें
    • 5 elements से कम वाले incomplete groups को simplification के लिए छोड़ दें
    • हर group को sort करें और index 2 वाला median collect करें
    • Collected medians की list में फिर median खोजकर उसे pivot के रूप में return करें
  • हर group का size fixed 5 है, इसलिए group-wise sorting को constant time माना जाता है और कुल मिलाकर यह O(n) काम है
  • Medians के median को खोजने वाली recursive call को size n/5 वाले subproblem के रूप में analysis में शामिल किया जाता है

कम-से-कम 30% क्यों हटाए जा सकते हैं

  • 5-element groups को sort करके columns की तरह रखें, और हर column के median को फिर sort करके medians का median चुनें, तो pivot की quality analyze की जा सकती है
  • Worst case में, जहां pivot जितना संभव हो उतना आगे की तरफ skewed हो, तब भी किसी खास quadrant के elements pivot से छोटे या बड़े होने की guarantee होती है
  • हर column से 3 elements लें और columns के आधे हिस्से को consider करें, तो कम-से-कम 3/5 * 1/2 * n = 3/10 n elements हटाए जा सकते हैं
  • Removal guarantee ratio: {p:30}
  • कुल running time को निम्न recurrence relation से व्यक्त किया जाता है
T(n) = n + T(n/5) + T(7n/10)
  • यहां n partitioning work है, T(n/5) median-of-medians calculation है, और T(7n/10) quickselect की recursive search है
  • इस recurrence में दो recursive terms हैं, इसलिए simple master theorem apply नहीं किया जा सकता, और induction एक intuitive proof method है

Combination result: linear-time median finding

  • quickselect पर्याप्त अच्छा pivot मिलने पर median को linear time में खोज सकता है
  • median-of-medians quickselect के लिए आवश्यक अच्छा pivot O(n) में चुन सकता है
  • दोनों algorithms को combine करने पर median या list का nth element linear time में खोजने वाला algorithm बनता है

Real-world implementation में choice

  • Practical scenarios में random pivot selection लगभग हमेशा पर्याप्त होता है
  • median-of-medians भी linear time है, लेकिन असल में pivot calculation cost ज्यादा होने से यह slow हो सकता है
  • C++ standard library introselect का उपयोग करती है, जो heapselect और quickselect को combine करता है और O(n log n) upper bound रखता है
  • introselect आमतौर पर fast लेकिन खराब upper bound वाले algorithm से शुरू करता है, और जब effective pivot नहीं चुन पाता, तो धीमे लेकिन अच्छे upper bound वाले algorithm पर switch करता है
  • quickselect function द्वारा देखे गए elements की संख्या की तुलना में deterministic pivot ने random pivot की तुलना में लगभग हमेशा कम elements consider किए, लेकिन इस comparison में median-of-medians calculation cost शामिल नहीं है
  • 2017 में आया new paper median-of-medians approach को दूसरे selection algorithms के साथ competitive बनाने की बात करता है

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2024-07-26
Hacker News की राय

  • करीब 4 साल पहले मैंने कई median algorithms की तुलना की थी, और पोस्ट उम्मीद से कहीं ज़्यादा लंबी हो गई थी :)
    https://danlark.org/2020/11/11/miniselect-practical-and-generic-selection-algorithms/

    • इनमें से क्या कोई ऐसा algorithm है जिसे आसानी से arg-median, यानी median वाला index लौटाने के लिए बदला जा सके?

  • 10–15 साल पहले, मुझे multi-kilobyte log entries से parse किए गए अरबों values का median नियमित रूप से निकालना पड़ता था। उस समय large-scale processing के लिए हम MapReduce इस्तेमाल कर रहे थे, और इतने data पर केवल linear time ही नहीं, बल्कि संभव हो तो single pass में कई machines पर distributed तरीका चाहिए था
    यह मददगार था कि हमें data की precision और range पता थी। values integer milliseconds में timings थीं, इसलिए negative नहीं थीं, और हमें यह भी पता था कि 90th percentile 1 second से काफी कम है
    आम तौर पर median निकालने के लिए sorting जैसा काम चाहिए होता है, लेकिन इन conditions में bucket sort संभव हो जाता है। key को integer millisecond timing और value को occurrence count रखकर एक dictionary, यानी histogram बनाना होता है
    maximum timing पता नहीं था, इसलिए dictionary का size बहुत न बढ़े, इसके लिए 999ms से ऊपर की सभी values को 999ms bucket में डाल दिया; इससे 0–999 keys और values मिलाकर कुल करीब 2000 integers तक सीमा रहती थी। यह हिस्सा सामान्य bucket sort से अलग था, और MapReduce से distribute करने पर भी single pass में बहुत आसानी से process हो जाता था; उसके बाद histogram से median निकाल लेते थे

    • क्या सच में अरबों values का exact median चाहिए था? या 49.9% और 50.1% के बीच की value काफी थी? अगर दूसरा, तो यह बहुत आसान है। random uniform तरीके से 10,000 samples लें और उनका median इस्तेमाल करें
      10,000 संख्या मैंने बस यूँ ही उदाहरण के लिए दी है, लेकिन desired confidence level के लिए ज़रूरी sample count statistically calculate किया जा सकता है, और शायद वह बहुत बड़ा नहीं होगा
    • पक्का नहीं कह सकता, लेकिन बाहर से देखने पर यह Prometheus के अंदरूनी तरीके जैसा लगता है
      जिन कुछ systems के साथ मैंने काम किया, उनमें Prometheus latency पर लगभग 10-second limit लगाता हुआ लगता था। इसलिए उस limit से ऊपर के requests, असल में और लंबे हो सकते थे, फिर भी सभी 10 seconds के रूप में दर्ज होते थे। दिलचस्प है
    • क्या आप availability metrics बना रहे थे, और उस समय intern थे? वह system, उhm, बहुत परिचित लग रहा है
    • समझ नहीं आया कि 0…999 keys वाली dictionary क्यों इस्तेमाल की। 0…999 से indexed array इस्तेमाल कर सकते थे, नहीं?

  • 2017 में एक नया paper आया था जिसने median-of-medians approach को दूसरे selection algorithms के मुकाबले competitive बना दिया, और postscript में लिखा है कि paper के author Andrei Alexandrescu ने यह बताया था
    उन्होंने 2016 में अपने algorithm पर talk भी दी थी। वे entertaining speaker हैं, इसलिए जोरदार recommend करता हूँ
    There's Treasure Everywhere - Andrei Alexandrescu
    https://www.youtube.com/watch?v=fd1_Miy1Clg

    • Andrei Alexandrescu कमाल के हैं। 2000 के आसपास उन्होंने lock-free, wait-free algorithms पर presentation दी थी, और हमने उसे उस समय एक बड़े C++ industrial control networking project में सीधे apply किया था
      अगर आप software इस्तेमाल करते हैं, तो Andrei की जितनी writings और talks मिल सकें, सब सुनने और पढ़ने की सलाह दूँगा। यह talk भी सचमुच एक treasure है
    • computer science के standards से भी वे काफी बहुज्ञानी व्यक्ति हैं, यह हैरान करता है। मैं उन्हें template metaprogramming के लिए जानता था, लेकिन यहाँ वे programming languages से algorithms की तरफ जा रहे हैं

  • undergrad में मैंने median-of-medians quickselect algorithm सीखा था और वह वाकई प्रभावशाली लगा। मैंने खुद implement करके देखा, लेकिन वह भयानक रूप से slow था। runtime linear तरीके से बढ़ता था, लेकिन उसका मतलब तभी बनता जब list में कम से कम अरबों items हों
    इस बारे में graduate student दोस्त से बात करते हुए उसने कुछ ऐसा कहा: “धीमा तो है, लेकिन अहम बात यह है कि यह साबित करता है कि unsorted list से selection O(n) time में किया जा सकता है। एक समय हमें पता भी नहीं था कि यह संभव है या नहीं, और अब जब पता है कि संभव है, तो faster linear algorithms भी हो सकते हैं”
    यह इतना simple और फिर भी गहरा lesson था कि मैं लगभग grad school में apply करने वाला था। पता नहीं उस दोस्त को यह बातचीत याद है या नहीं, लेकिन मेरी education में यह एक turning point जैसा moment था

    • क्या किसी एक linear time algorithm का अस्तित्व faster linear time algorithm के अस्तित्व का संकेत देता है? अगर नहीं, तो इस knowledge से क्या फायदा मिलता है?
      “क्योंकि हमें पता है कि कोई algorithm पहले से मौजूद है, इसलिए faster algorithm भी हो सकता है” ऐसा भी सोचा जा सकता है। O(n) algorithm का existence, O(n log n) algorithm के existence से ज़्यादा मजबूत संकेत क्यों है?
    • मुझे लगता है मैंने computer science के fourth year में यह algorithm सीखा था। जैसा कहा गया, इसके theoretical aspect पर बात हुई थी, लेकिन इसे इस example के रूप में भी इस्तेमाल किया गया था कि real-world के अधिकतर cases में slow linear algorithm, fast n log n algorithm से तेज़ नहीं होता
      मुझे लगता है इस algorithm का constant factor करीब 22 था, हालांकि शायद वह कोई related algorithm रहा हो

  • median-of-medians एल्गोरिदम की एक दिलचस्प बात यह है कि इसके authors की सूची पूरी तरह स्टार-स्टडेड है
    Manuel Blum - 1995 के Turing Award विजेता
    Robert Floyd - 1978 के Turing Award विजेता
    Ron Rivest - 2002 के Turing Award विजेता
    Bob Tarjan - 1986 के Turing Award विजेता और 1982 के पहले Nevanlinna Prize विजेता
    Vaughan Pratt - सूची में अकेले ऐसे व्यक्ति जो Turing Award विजेता नहीं हैं, लेकिन Stanford में professor emeritus हैं, Sun Microsystems बनने से पहले SUN project का नेतृत्व किया, Sun के शुरुआती दिनों में research head और Sun logo designer के रूप में अहम भूमिका निभाई, और Pratt primality certificates जैसी कई शानदार चीजें छोड़ीं
    चार स्वतंत्र Turing Awards और SPARCstation तक—इस पेपर में सब कुछ है

    • नए frontend developer के interview का सवाल: “अगले 30 मिनट में चार Turing Award विजेताओं का काम फिर से बनाइए। आपके पास एक गंदा whiteboard और सूखा pen है। समय अब शुरू होता है”
    • original paper पढ़ना चाहने वालों के लिए direct link: https://people.csail.mit.edu/rivest/pubs/BFPRT73.pdf
      authors की सूची सचमुच प्रभावशाली है
    • Pratt का एक और शानदार काम Pratt parsing है। HN discussion: https://news.ycombinator.com/item?id=39066465
      KMP algorithm में “P” भी Pratt ही हैं

  • return l[len(l) / 2]
    मैं Python expert नहीं हूँ, लेकिन Python में / operator floating-point value लौटाता है, नहीं? array index के लिए floating-point इस्तेमाल करने के बजाय integer division // क्यों नहीं इस्तेमाल किया गया?
    बहुत बड़े array न हों तो शायद समस्या न बने, फिर भी इसमें काफी code smell है। अगर आप Python beginner हैं और नहीं जानते कि ये दोनों operators अलग-अलग हैं, तो बात समझ आती है, लेकिन लेख में एक branch में integer division और दूसरी branch में floating-point division इस्तेमाल करने वाला और भी अजीब code है
    def quickselect_median(l, pivot_fn=random.choice):
    if len(l) % 2 == 1:
    return quickselect(l, len(l) // 2, pivot_fn)
    else:
    return 0.5 * (quickselect(l, len(l) / 2 - 1, pivot_fn) +
    quickselect(l, len(l) / 2, pivot_fn))
    50 comments हो चुके हैं और लगता है किसी ने इसे नहीं देखा, इससे औसत Python code quality को लेकर मेरा पुराना bias और मजबूत हो गया

    • अच्छी पकड़। Python 2 में सिर्फ एक operator था, लेकिन Python 3 में दोनों अलग हैं
      मुझे लगता है floating-point से array indexing करने पर exception आएगा
    • code smell वाली बात से सहमत हूँ। हालांकि यह algorithm पर लेख है, इसलिए code quality से judge करना पूरी तरह fair नहीं लगता
      pseudocode के बजाय pseudocode जैसा दिखने वाली असली programming language चुनी गई है, और explanation के लिए शायद यह ठीक से चलने वाला code है

  • मूल लेख पढ़ने में वाकई मजेदार था, लेकिन “अगर हर step में सबसे बड़ा element pivot के रूप में चुना जाए तो O(n) के बजाय O(n²) हो सकता है” वाला हिस्सा अटका
    अगर adversarial input की चिंता है, तो data को पहले O(n) में shuffle कर देने से ऐसा जबरन होने से रोका जा सकता है। अगर data इतना बड़ा है कि shuffle करना मुश्किल है, तो जब buckets shuffle करने लायक size के हो जाएँ, तब एक बार मिला दें
    shuffle करने के बाद probability इस बात की गारंटी देती है कि worst case practically नहीं होगा। अगर कोई कहे कि “technically” possible है, तो मैं कहूँगा कि “technically” attacker 256-bit private key के सभी bits भी सही guess कर सकता है
    हमारी दुनिया probability पर बनी है। हर private key इस mathematical impossibility से सुरक्षित है कि कोई उसे सही-सही guess नहीं कर पाएगा
    मेरी पढ़ाई के हिसाब से shuffle के बाद quickselect practical रूप से O(n) है

    • pivot को पहले से ही अपने random numbers से randomly चुना जा रहा है, इसलिए shuffle और क्यों मदद करेगा, यह समझ नहीं आता
      फिर भी अगर random numbers पर भरोसा किया जा सकता है, तो O(n) से ज्यादा runtime आने की probability बहुत कम है
    • “अगर adversarial input की चिंता है, तो data को पहले O(n) में shuffle करना इसकी guarantee देता है” यह worst case से बचने की guarantee नहीं देता, बल्कि worst case को force करने की संभावना को हटाता है

  • Floyd-Rivest भी वह काम कर देता है। अगर मुझे सही याद है तो थोड़ा ज्यादा efficient है
    लेकिन मैं इसके काम करने का तरीका आखिर तक समझ नहीं पाया
    https://en.m.wikipedia.org/wiki/Floyd%E2%80%93Rivest_algorithm

  • nवें element को चुनते समय अगर n बहुत छोटा या बहुत बड़ा है, तो median-of-medians शायद best न हो
    इसके बजाय [1] जैसा biased pivot इस्तेमाल कर सकते हैं, या वह तरीका जिसे मैं “j-th of k-th” कहता हूँ। Floyd-Rivest भी speed बढ़ा सकता है
    मेरा एक hobby project है जो अच्छी तरह implemented quickselect की तुलना में 1.2~2.0 गुना throughput देता है: https://github.com/koskinev/turboselect
    तेज general-purpose in-place selection algorithms पर कोई material हो तो मुझे interest है
    [1] https://doi.org/10.4230/LIPIcs.SEA.2017.24

  • पूरे data को memory में store किए बिना भी arbitrary quantiles के approximate values निकालने के लिए streaming algorithm इस्तेमाल किया जा सकता है

    • अगर approximation accept कर सकते हैं, तो यह शानदार तरीका है। लेकिन जल्दी ही असहज सवाल आने लगते हैं
      क्या approximate calculation allow कर सकते हैं? error bound तय करने के लिए data के बारे में कौन-सी assumptions चाहिए? और कैसे verify करेंगे कि वे assumptions लगातार valid हैं?
      व्यक्तिगत रूप से, जब तक streaming median approximation पर विचार करना ही पड़े ऐसी स्थिति न आ जाए, मैं मूल लेख वाले quickselect algorithm की तरफ झुकूँगा
    • streaming quantile algorithm useful होता, ऐसी situations निश्चित रूप से रही हैं। कोई reference material है?