Mein Lieblingsalgorithmus: Lineare Medianbestimmung (2018)

Median in O(n log n) finden

• Die einfachste Methode ist, die Liste zu sortieren und dann den Median auszuwählen
• Vergleichsbasiertes Sortieren hat eine Zeitkomplexität von O(n log n)
• Codebeispiel:

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

Median in durchschnittlich O(n) finden

• Mit dem Algorithmus "quickselect" lässt sich der Median im Durchschnitt in linearer Zeit finden

• Ein rekursiver Algorithmus, entwickelt von Tony Hoare

• Ablauf:

  1. Wähle einen beliebigen Index aus der Liste und setze ihn als Pivot
  2. Teile die Liste anhand des Pivot in zwei Gruppen:
     • Elemente, die kleiner oder gleich dem Pivot sind
     • Elemente, die größer als der Pivot sind
  3. Durchsuche rekursiv die Gruppe, die den Median enthält

• Codebeispiel:

  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)  
  

Beweis für durchschnittlich O(n)

• Wenn der Pivot die Liste ungefähr halbiert, arbeitet jeder rekursive Aufruf auf der Hälfte der Daten des vorherigen Schritts
• Mathematischer Beweis:

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

Deterministisches O(n)

• Garantiert lineare Zeit auch im Worst Case

• Verwendet den Algorithmus "median-of-medians" zur Auswahl des Pivot

• Ablauf:

  1. Teile die Liste in Gruppen zu je 5 Elementen
  2. Sortiere jede Gruppe und wähle den Median
  3. Wähle den Median der Mediane als Pivot

• Codebeispiel:

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

Zusammenfassung

• Der quickselect-Algorithmus kann bei geeigneter Pivot-Wahl den Median in linearer Zeit finden
• Der median-of-medians-Algorithmus ist eine Methode zur Pivot-Auswahl, die auch im Worst Case lineare Zeit garantiert
• In der Praxis ist die zufällige Pivot-Wahl meist ausreichend effektiv

Zusammenfassung von GN⁺

• Dieser Artikel erklärt verschiedene Algorithmen zur Bestimmung des Medians und behandelt insbesondere Methoden, den Median in linearer Zeit zu finden
• Der quickselect-Algorithmus ist im Durchschnitt schnell, aber für den Worst Case kann der median-of-medians-Algorithmus verwendet werden
• In praktischen Anwendungen ist die zufällige Pivot-Wahl in den meisten Fällen ausreichend effektiv
• Ein Algorithmus mit ähnlicher Funktion ist introselect, der in der C++-Standardbibliothek verwendet wird

[GN⁺]

Hacker-News-Kommentare

• Vor 4 Jahren wurde ein langer Artikel geschrieben, der verschiedene Median-Algorithmen verglich
• Vor 10–15 Jahren wurde MapReduce verwendet, um den Median in Log-Einträgen mit Milliarden von Werten zu finden
  • Wenn man die Genauigkeit und den Wertebereich der Daten kennt, hätte man Bucket Sort verwenden können
  • Die Zeitwerte konnten als ganze Millisekunden dargestellt und ein Histogramm erstellt werden, um den Median leicht zu finden
• 2017 wurde eine Arbeit veröffentlicht, die den Median-of-Medians-Ansatz im Vergleich zu anderen Auswahlalgorithmen konkurrenzfähig machte
  • Andrei Alexandrescu hielt 2016 einen Vortrag über diesen Algorithmus
• Die Autorenliste des Median-of-Medians-Algorithmus ist sehr prominent
  • Manuel Blum, Robert Floyd, Ron Rivest, Bob Tarjan, Vaughan Pratt usw.
• Der Floyd-Rivest-Algorithmus ist ebenfalls effizient, aber schwer zu verstehen
• Mit Streaming-Algorithmen lassen sich Näherungswerte berechnen, ohne die gesamten Daten im Speicher zu halten
• Es gibt eine Methode, den Median auszuwählen, indem man Quicksort modifiziert
• Als Interviewfrage bekam jemand das Problem, den Median in einer Liste mit Billionen von Zahlen zu finden
  • Es wurde ein Ansatz mit oberer und unterer Schranke verwendet, um den Median zu finden, aber das war nicht die optimale Methode
  • Es gab eine effizientere Methode mit einem Priority Heap
  • Danach wurde ein LeetCode-Abonnement begonnen
• Ein einfaches in Go implementiertes Beispiel wurde geteilt
• Radix Sort kann außer für ganze Zahlen auch für verschiedene Datentypen wie Strings verwendet werden