Mon algorithme préféré : recherche de la médiane en temps linéaire (2018)

Trouver la médiane en O(n log n)

• La méthode la plus simple consiste à trier la liste puis à choisir la médiane
• La complexité temporelle d’un tri par comparaison est de O(n log n)
• Exemple de code :

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

Trouver la médiane en O(n) en moyenne

• On peut trouver la médiane en temps linéaire en moyenne en utilisant l’algorithme de "quickselect"

• Algorithme récursif développé par Tony Hoare

• Procédure :

  1. Choisir un index aléatoire dans la liste et le définir comme pivot
  2. Diviser la liste en deux groupes autour du pivot :
     • les éléments inférieurs ou égaux au pivot
     • les éléments supérieurs au pivot
  3. Explorer récursivement le groupe qui contient la médiane

• Exemple de code :

  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)  
  

Preuve du O(n) en moyenne

• Si le pivot coupe la liste à peu près en deux, chaque appel récursif travaille sur la moitié des données de l’étape précédente
• Preuve mathématique :

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

O(n) déterministe

• Garantit un temps linéaire même dans le pire des cas

• Sélectionne le pivot avec l’algorithme de "median-of-medians"

• Procédure :

  1. Diviser la liste en groupes de 5
  2. Trier chaque groupe et choisir sa médiane
  3. Choisir comme pivot la médiane des médianes

• Exemple de code :

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

Résumé

• L’algorithme quickselect peut trouver la médiane en temps linéaire s’il choisit un pivot approprié
• L’algorithme median-of-medians est une méthode de sélection du pivot qui garantit un temps linéaire même dans le pire des cas
• En pratique, un choix de pivot aléatoire est généralement suffisamment efficace

Le résumé de GN⁺

• Cet article explique différents algorithmes pour trouver la médiane, en particulier les méthodes qui la trouvent en temps linéaire
• L’algorithme quickselect est rapide en moyenne, mais on peut utiliser l’algorithme median-of-medians pour se prémunir contre le pire des cas
• Dans les applications réelles, un choix de pivot aléatoire est le plus souvent suffisamment efficace
• Un algorithme similaire est introselect, utilisé dans la bibliothèque standard C++

[GN⁺]

Commentaires Hacker News

• Il y a 4 ans, il avait rédigé un long article comparant différents algorithmes de médiane
• Il y a 10 à 15 ans, il avait utilisé MapReduce pour trouver la médiane dans des entrées de logs contenant des milliards de valeurs
  • En connaissant la précision et la plage des données, il était possible d’utiliser un tri par buckets
  • En représentant les temps en millisecondes entières et en générant un histogramme, il était possible de trouver facilement la médiane
• En 2017, un article a été publié rendant l’approche median-of-medians compétitive face à d’autres algorithmes de sélection
  • Andrei Alexandrescu a donné une conférence sur cet algorithme en 2016
• La liste des auteurs de l’algorithme median-of-medians est particulièrement prestigieuse
  • Manuel Blum, Robert Floyd, Ron Rivest, Bob Tarjan, Vaughan Pratt, etc.
• L’algorithme de Floyd-Rivest est lui aussi efficace, mais difficile à comprendre
• Les algorithmes de streaming permettent de calculer une approximation sans stocker l’ensemble des données en mémoire
• Il existe une méthode consistant à modifier le quicksort pour sélectionner la médiane
• Il a reçu en entretien une question demandant de trouver la médiane dans une liste contenant des milliers de milliards de nombres
  • Il a utilisé une approche consistant à fixer des bornes supérieure et inférieure pour trouver la médiane, mais ce n’était pas optimal
  • Il existait une méthode plus efficace utilisant un tas de priorité
  • Il a ensuite commencé un abonnement à LeetCode
• Il a partagé un exemple simple implémenté en Go
• Le tri radix peut s’appliquer à différents types de données, pas seulement aux entiers, mais aussi aux chaînes de caractères, etc.