Introduction au seau Tri pour les numéros flottants

Le tri de seau est un algorithme de tri basé sur la distribution qui divise les données d'entrée en un nombre fini de -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

L'idée centrale est simple : au lieu de comparer chaque paire d'éléments (comme en comparaison comme Quicksort ou fusionsort), le seau trie d'abord les éléments à travers des seaux en fonction de leurs valeurs. Chaque seaux regroupe naturellement une gamme étroite de valeurs. Ensuite, un simple algorithme de tri — souvent le trier par insertion ou même un appel récursif au trier des seaux — termine le travail.

Cet article offre un regard approfondi sur la mise en œuvre du tri de seau pour les nombres de points flottants en Python, couvrant ses mécanismes, complexité, forces, pièges et applications du monde réel.

Comment fonctionne le tri des seauts

Le tri de seau suppose que l'entrée est uniformément répartie dans une plage connue, généralement . L'algorithme se déroule en trois phases :

  1. Initialisation[: Créer un tableau de n seaux vides, où n est le nombre d'éléments.
  2. Distribution: Pour chaque élément , calculer son indice de godet (en supposant que les valeurs sont dans ) et placer l'élément dans ce godet.
  3. Sortir et concaténation[ : Trier chaque seau individuellement (en utilisant tout tri interne stable ou efficace), puis concaténer les seau afin de produire le tableau final trié.

La principale conclusion est que, parce que les données sont uniformément distribuées, chaque seau reçoit en moyenne un élément n / n = 1, ce qui maintient le coût de tri des seau individuels extrêmement bas — souvent le temps constant par seau.

Traitement des cas de bord

Quand un nombre de point flottant est exactement égal à 1,0, l'indice calculé serait , qui est hors limites. Une correction courante est de serrer l'index à pour de telles valeurs. Dans la pratique, si vos données sont strictement , ce cas de bord ne se produit pas, mais il est sage de se garder contre elle.

Mise en œuvre du seau Tri en Python

Ci-dessous est une mise en œuvre propre et prête à la production de seau tri pour les nombres de points flottants dans la gamme .

def bucket_sort(arr):
 """Sort an array of floats uniformly distributed in [0, 1)."""
 n = len(arr)
 if n <= 1:
 return arr

 # Create empty buckets
 buckets = [[] for _ in range(n)]

 # Distribute elements into buckets
 for num in arr:
 index = int(num * n)
 # Guard against floating-point index = n (e.g., when num == 1.0)
 if index == n:
 index = n - 1
 buckets[index].append(num)

 # Sort each bucket and concatenate
 sorted_arr = []
 for bucket in buckets:
 sorted_arr.extend(sorted(bucket)) # Python's Timsort is efficient

 return sorted_arr

La fonction utilise Python , intégré pour trier chaque seau. Pour les seaux qui sont petits (généralement 0–2 éléments), c'est très rapide. Pour l'utilisation de la production, vous pouvez remplacer par un tri d'insertion pour des frais généraux encore plus bas sur les seaux minuscules.

Tri seau pour les gammes arbitraires

Si vos données en point flottant s'étendent sur une plage autre que , vous pouvez normaliser les valeurs avant distribution. La variation suivante cartographie toute plage à :

def bucket_sort_scaled(arr, min_val=None, max_val=None):
 if not arr:
 return arr
 if min_val is None:
 min_val = min(arr)
 if max_val is None:
 max_val = max(arr)

 # Guard against identical values
 if max_val == min_val:
 return arr

 n = len(arr)
 buckets = [[] for _ in range(n)]

 for num in arr:
 # Normalize to [0, 1)
 normalized = (num - min_val) / (max_val - min_val)
 index = int(normalized * n)
 if index == n:
 index = n - 1
 buckets[index].append(num)

 sorted_arr = []
 for bucket in buckets:
 sorted_arr.extend(sorted(bucket))
 return sorted_arr

Cette version est plus générale mais nécessite de connaître ou de calculer la plage. Elle fonctionne bien lorsque la distribution des données est approximativement uniforme dans cette plage.

Analyse de complexité

Il est essentiel de comprendre le coût de calcul du tri des seau pour décider quand l'utiliser.

Complexité temporelle

  • (données réparties uniformément): O(n + k), où k est le nombre de seaux (généralement n. La distribution est O(n), et le tri de chaque seaux prend en moyenne un temps constant, donc globalement O(n).
  • Caisse moyenne: O(n + n2/k) si l'on utilise le tri d'insertion pour les seaux. Avec k = n, cela devient O(n).
  • Cachet le plus défavorable[: O(n2) lorsque tous les éléments tombent dans le même seau. Cela se produit lorsque les données ne sont pas uniformément distribuées ou lorsque la plage est très petite par rapport au nombre d'éléments.

Complexité spatiale

Le seau de tri nécessite O(n + k) un espace supplémentaire pour les seaux et leur contenu. Avec k = n, il s'agit O(n). L'espace utilisé est comparable à celui de fusion tri et supérieur à celui des types en place comme le swicksort.

Avantages et cas d'utilisation

Le seau se présente dans des scénarios spécifiques où ses hypothèses sont fondées :

  • Données en points flottants réparties uniformément — p.ex. lectures de capteurs, sorties de simulation Monte Carlo ou probabilités normalisées.
  • Les grandes séries de données[ — la O(n) moyenne-case rend attrayant pour le tri de millions de flotteurs où les comparaisons seraient moins efficaces.
  • Tri externe[ — lorsque les données résident sur disque, les seaux peuvent être traités indépendamment et écrits dans des fichiers séparés, puis concaténés.
  • Parallèle et calcul GPU[ — chaque seau peut être trié indépendamment, permettant un parallélisme massif.

Une force notable est que le seau de tri est stable (si le type par boulon est stable), ce qui signifie que l'ordre relatif des éléments égaux est préservé.

Limites et considérations

Malgré son élégance, le seau trié a plusieurs limites qui peuvent le rendre impropre au tri général :

  • Sensibilité à la distribution des entrées: Si les données sont biaisées (p. ex., de nombreuses valeurs regroupées), la plupart des éléments tombent dans quelques seaux, augmentant le coût de tri à O(n2).
  • Il faut connaître la plage : Sans connaître les valeurs minimales et maximales, vous ne pouvez pas créer de seaux. La version à échelles ci-dessus l'atténue, mais le calcul de la plage ajoute un passage supplémentaire.
  • Mémoires : Création n Les listes de Python peuvent consommer une mémoire importante, surtout pour les très grands tableaux. Les listes de Python sont liées ou les tableaux de tableaux peuvent réduire les frais généraux, mais la liste de Python="s est simple.
  • Le tri par rondelle: Trier de nombreux petits seaux avec des Python] produit des appels de fonction qui peuvent s'additionner. Pour des seaux extrêmement petits, un genre d'insertion explicite pourrait être plus rapide.

Quand ne pas utiliser le seau Tri

Évitez le triage par seau lorsque les données ne sont pas uniformément distribuées, lorsque la plage est très grande par rapport au nombre d'éléments, ou lorsque la mémoire est extrêmement limitée. Dans ces cas, un tri à base de comparaison comme quicksort[ ou heapsort est un choix plus sûr.

Comparaison avec d'autres algorithmes de tri

Le seau occupe une niche unique parmi les algorithmes de tri. Voici comment il se compare aux alternatives communes:

Algorithm Average Time Space Stable Best For
Bucket Sort (with k = n) O(n) O(n) Yes (if per-bucket sort is stable) Uniform floats in known range
Quicksort O(n log n) O(log n) No (typical) General-purpose, in-place
Mergesort O(n log n) O(n) Yes Stable sorting, linked lists
Counting Sort O(n + k) O(k) Yes Integer data with limited range
Radix Sort O(n × w) O(n + 2^w) Yes (LSD) Integers or strings of fixed length

Pour les nombres flottants, le tri du seau surpasse souvent le tri du radix (qui nécessite une manipulation bit des flotteurs) et peut être plus rapide que O(n log n) les tris comparatifs lorsque les données sont uniformes.

Conseils pratiques et optimisations pour le Python

Choisir le nombre de seauts

Le nombre de seaux égal au nombre d'éléments (k = n) est une règle standard du pouce. Moins de seaux augmentent la taille moyenne des seaux et dégradent les performances; plus de seaux gaspillent la mémoire sans améliorer la vitesse.

Utilisation de l'insertion Tri pour les petits seauts

Si vous voulez un contrôle à grain fin, remplacez par un tri d'insertion personnalisé pour les seaux plus petits que, par exemple, 20 éléments:

def insertion_sort(arr):
 for i in range(1, len(arr)):
 key = arr[i]
 j = i - 1
 while j >= 0 and arr[j] > key:
 arr[j + 1] = arr[j]
 j -= 1
 arr[j + 1] = key

def bucket_sort_insertion(arr):
 n = len(arr)
 if n <= 1:
 return arr
 buckets = [[] for _ in range(n)]
 for num in arr:
 index = int(num * n)
 if index == n:
 index = n - 1
 buckets[index].append(num)
 sorted_arr = []
 for bucket in buckets:
 insertion_sort(bucket)
 sorted_arr.extend(bucket)
 return sorted_arr

Cela peut réduire les frais généraux parce que Python , a un comportement de fonction-appel en tête et à usage général qui est surkill pour les listes de 0 ou 1 élément.

Manipulation Distributions non uniformes

Si vous savez que la distribution des données n'est pas uniforme mais que vous voulez toujours utiliser le seau de tri, vous pouvez adapter les limites du seau. Par exemple, si les données suivent une distribution normale, vous pouvez créer des seaux de largeur inégale pour équilibrer la charge.

Ressources extérieures

Pour plus de précisions, il convient d'examiner les références suivantes faisant autorité :

Conclusion

Le seau est un algorithme élégant et efficace pour le tri des nombres flottants, surtout lorsque les données sont uniformément distribuées et que la gamme est connue. Sa complexité linéaire moyenne en fait un outil précieux dans la boîte à outils data savants ou ingénieurs. Cependant, sa sensibilité à la distribution d'entrées et aux exigences supplémentaires en mémoire signifie qu'il ne doit pas être utilisé aveuglément. En comprenant quand et comment appliquer le seau tri, et en le mettant en œuvre avec soin dans Python avec la manipulation appropriée des cas de bord, vous pouvez obtenir des gains de performance importants sur les types de comparaison à usage général.

Que vous triiez des millions de mesures de capteurs ou que vous normalisiez la sortie à partir d'une simulation stochastique, le seau tri offre une solution rapide, stable et parallélisante, tant que vos données sont en accord avec les règles.