Sevdiğim Algoritma: Doğrusal Zamanda Medyan Bulma (2018)

O(n log n) ile medyan bulma

• Bir listeyi sıraladıktan sonra medyanı seçmek en basit yöntemdir
• Karşılaştırma tabanlı sıralamanın zaman karmaşıklığı O(n log n)'dir
• Kod örneği:

  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])  
  

Ortalama O(n) ile medyan bulma

• Medyan, "quickselect" algoritması kullanılarak ortalama olarak doğrusal zamanda bulunabilir

• Tony Hoare tarafından geliştirilen özyinelemeli bir algoritmadır

• Süreç:

  1. Listeden rastgele bir indeks seçilip pivot olarak belirlenir
  2. Liste, pivot temel alınarak iki gruba ayrılır:
     • pivottan küçük veya pivota eşit öğeler
     • pivottan büyük öğeler
  3. Medyanı içeren grup özyinelemeli olarak aranır

• Kod örneği:

  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)  
  

Ortalama O(n) kanıtı

• Pivot listenin yaklaşık yarıya bölünmesini sağladığında, her özyinelemeli çağrı bir önceki adımın verisinin yarısı üzerinde çalışır
• Matematiksel kanıt:

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

Deterministik O(n)

• En kötü durumda bile doğrusal zamanı garanti eder

• Pivot seçmek için "median-of-medians" algoritması kullanılır

• Süreç:

  1. Liste 5'li gruplara ayrılır
  2. Her grup sıralanır ve medyan seçilir
  3. Medyanların medyanı pivot olarak seçilir

• Kod örneği:

  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)]  
  

Özet

• quickselect algoritması, uygun bir pivot seçildiğinde medyanı doğrusal zamanda bulabilir
• median-of-medians algoritması, en kötü durumda bile doğrusal zamanı garanti eden bir pivot seçme yöntemidir
• Pratikte rastgele pivot seçimi yeterince etkilidir

GN⁺ özeti

• Bu yazı, medyan bulmaya yönelik çeşitli algoritmaları açıklar ve özellikle medyanı doğrusal zamanda bulma yöntemini ele alır
• quickselect algoritması ortalamada hızlıdır, ancak en kötü durum için median-of-medians algoritması kullanılabilir
• Gerçek uygulamalarda rastgele pivot seçimi çoğu zaman yeterince etkilidir
• Benzer işleve sahip bir algoritma olan introselect de vardır; bu algoritma C++ standart kütüphanesinde kullanılır

[GN⁺]

Hacker News görüşleri

• 4 yıl önce çeşitli medyan algoritmalarını karşılaştıran uzun bir yazı yazmıştı
• 10-15 yıl önce, milyarlarca değere sahip log kayıtlarında medyanı bulmak için MapReduce kullanmıştı
  • Verinin hassasiyetini ve aralığını biliyorsanız bucket sort kullanabiliyordunuz
  • Zamanlamaları tam sayı milisaniye olarak ifade edip bir histogram oluşturarak medyanı kolayca bulabiliyordunuz
• 2017'de, median-of-medians yaklaşımını diğer seçim algoritmalarıyla rekabetçi hale getiren bir makale yayımlandı
  • Andrei Alexandrescu bu algoritma hakkında 2016'da bir konuşma yapmıştı
• Median-of-medians algoritmasının yazar listesi oldukça ünlü
  • Manuel Blum, Robert Floyd, Ron Rivest, Bob Tarjan, Vaughan Pratt gibi isimler
• Floyd-Rivest algoritması da verimli, ancak anlaşılması zor
• Streaming algoritmaları kullanılırsa tüm veriyi bellekte tutmadan yaklaşık değer hesaplanabilir
• Quicksort'u değiştirerek medyan seçmenin bir yolu var
• Mülakat sorusu olarak, trilyonlarca sayı içeren bir listede medyanı bulma problemiyle karşılaşmıştı
  • Üst ve alt sınırlar koyarak medyanı bulma yöntemini kullanmıştı, ancak bu en iyi yöntem değildi
  • Priority heap kullanan daha verimli bir yöntem vardı
  • Sonrasında LeetCode aboneliği başlatmıştı
• Go ile yazılmış basit bir örnek paylaşmıştı
• Radix sort, tam sayılar dışında string gibi çeşitli veri türlerinde de kullanılabilir