मेरा पसंदीदा एल्गोरिद्म: Linear Time Median Finding (2018)

O(n log n) में median खोजना

• सूची को sort करने के बाद median चुनने का सबसे सरल तरीका
• comparison-based sorting की time complexity O(n log n) होती है
• कोड उदाहरण:

  def nlogn_median(l):  
      l = sorted(l)  
      if len(l) % 2 == 1:  
          return l[len(l) // 2]  
      else:  
          return 0.5 * (l[len(l) // 2 - 1] + l[len(l) // 2])  
  

औसतन O(n) में median खोजना

• "quickselect" एल्गोरिद्म का उपयोग करके औसतन linear time में median पाया जा सकता है

• Tony Hoare द्वारा विकसित recursive एल्गोरिद्म

• प्रक्रिया:

  1. सूची से एक random index चुनकर उसे pivot के रूप में सेट करें
  2. pivot के आधार पर सूची को दो समूहों में बाँटें:
     • pivot से छोटे या उसके बराबर elements
     • pivot से बड़े elements
  3. उस समूह में recursively खोजें जिसमें median शामिल है

• कोड उदाहरण:

  import random  
  
  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))  
  
  def quickselect(l, k, pivot_fn):  
      if len(l) == 1:  
          assert k == 0  
          return l[0]  
  
      pivot = pivot_fn(l)  
      lows = [el for el in l if el < pivot]  
      highs = [el for el in l if el > pivot]  
      pivots = [el for el in l if el == pivot]  
  
      if k < len(lows):  
          return quickselect(lows, k, pivot_fn)  
      elif k < len(lows) + len(pivots):  
          return pivots[0]  
      else:  
          return quickselect(highs, k - len(lows) - len(pivots), pivot_fn)  
  

औसत O(n) का प्रमाण

• यदि pivot सूची को लगभग आधे में बाँटता है, तो हर recursive call पिछले चरण के लगभग आधे डेटा पर काम करती है
• गणितीय प्रमाण:

  C = n + n/2 + n/4 + n/8 + ... = 2n = O(n)  
  

deterministic O(n)

• worst case में भी linear time की गारंटी

• pivot चुनने के लिए "median-of-medians" एल्गोरिद्म का उपयोग

• प्रक्रिया:

  1. सूची को 5-5 के समूहों में बाँटें
  2. हर समूह को sort करें और उसका median चुनें
  3. medians के median को pivot के रूप में चुनें

• कोड उदाहरण:

  def pick_pivot(l):  
      assert len(l) > 0  
  
      if len(l) < 5:  
          return nlogn_median(l)  
  
      chunks = chunked(l, 5)  
      full_chunks = [chunk for chunk in chunks if len(chunk) == 5]  
      sorted_groups = [sorted(chunk) for chunk in full_chunks]  
      medians = [chunk[2] for chunk in sorted_groups]  
      median_of_medians = quickselect_median(medians, pick_pivot)  
      return median_of_medians  
  
  def chunked(l, chunk_size):  
      return [l[i:i + chunk_size] for i in range(0, len(l), chunk_size)]  
  

सारांश

• quickselect एल्गोरिद्म उचित pivot चुनने पर linear time में median खोज सकता है
• median-of-medians एल्गोरिद्म pivot चुनने की ऐसी विधि है जो worst case में भी linear time की गारंटी देती है
• व्यवहार में random pivot selection काफी प्रभावी होता है

GN⁺ का सार

• यह लेख median खोजने के विभिन्न एल्गोरिद्म समझाता है, खासकर linear time में median खोजने की विधि पर केंद्रित है
• quickselect एल्गोरिद्म औसतन तेज है, लेकिन worst case से निपटने के लिए median-of-medians एल्गोरिद्म का उपयोग किया जा सकता है
• वास्तविक अनुप्रयोगों में random pivot selection अधिकांश मामलों में पर्याप्त रूप से प्रभावी होता है
• समान कार्यक्षमता वाला एक और एल्गोरिद्म introselect है, जिसका उपयोग C++ standard library में किया जाता है

[GN⁺]

Hacker News राय

• 4 साल पहले विभिन्न median algorithms की तुलना करते हुए एक लंबा लेख लिखा था
• 10-15 साल पहले, अरबों values वाले log entries में median खोजने के लिए MapReduce का उपयोग किया था
  • अगर data की precision और range पता हो, तो bucket sort का उपयोग किया जा सकता था
  • timing को integer milliseconds में व्यक्त करके histogram बनाया जा सकता था और median आसानी से निकाला जा सकता था
• 2017 में एक paper प्रकाशित हुआ था जिसने median-of-medians approach को अन्य selection algorithms के मुकाबले प्रतिस्पर्धी बनाया
  • Andrei Alexandrescu ने 2016 में इस algorithm पर एक talk दी थी
• median-of-medians algorithm के authors की सूची बहुत प्रसिद्ध है
  • Manuel Blum, Robert Floyd, Ron Rivest, Bob Tarjan, Vaughan Pratt आदि
• Floyd-Rivest algorithm भी efficient है, लेकिन समझना कठिन है
• streaming algorithms का उपयोग करने पर पूरे data को memory में रखे बिना भी approximation निकाला जा सकता है
• quicksort को modify करके median select करने का एक तरीका है
• interview question के रूप में खरबों numbers वाली list में median खोजने की समस्या मिली थी
  • upper bound और lower bound सेट करके median खोजने का तरीका इस्तेमाल किया, लेकिन वह सबसे अच्छा तरीका नहीं था
  • priority heap का उपयोग करने वाला एक अधिक efficient तरीका मौजूद था
  • उसके बाद LeetCode subscription शुरू किया
• Go में implement किया गया एक सरल example साझा किया था
• Radix sort का उपयोग integers के अलावा strings जैसे विभिन्न data types पर भी किया जा सकता है