Introducere în Sortare găleată pentru numere cu punct plutitor

Sort găleată este un algoritm de sortare pe bază de distribuție care partiționează datele de intrare într-un număr finit de

Ideea de bază este simplă: în loc să compare fiecare pereche de elemente (ca în comparaţie cu tipul de hyppipsort sau fuzion), găleată de sortare distribuie mai întâi elementele de-a lungul găleţilor bazate pe valorile lor. Fiecare găleată se grupează natural împreună o gamă îngustă de valori. După aceea, un simplu algoritm de sortare

Acest articol oferă o privire aprofundată asupra implementării sortimentului de găleată pentru numerele de puncte plutitoare din Python, acoperind mecanica, complexitatea, punctele forte, capcanele și aplicațiile din lumea reală.

Cum se sortează găleata

Sort găleată presupune că intrarea este distribuită uniform într-un interval cunoscut, de obicei . Algoritmul se realizează în trei faze:

  1. Inițializare: Creați o serie de găleți goale n, unde nn este numărul de elemente.
  2. Distribuție[: Pentru fiecare element , calculează indicele său de găleată (valorile care presupun sunt în ] și introduce elementul în găleată.
  3. Sortare și concatenare: Sortare individuală a fiecărei găleți (folosind orice tip intern stabil sau eficient), apoi concatenați gălețile pentru a produce matricea sortate final.

Ideea cheie este că, deoarece datele sunt distribuite uniform, fiecare găleată primește aproximativ n / n = 1 element în medie. Aceasta menține costul sortării găleților individuale extrem de scăzute

Manipularea cazurilor de margine

Atunci când un număr de punct plutitor este exact egal cu 1.0, indicele calculat ar fi , care este în afara limitelor. Un fix comun este de a fixa indexul la pentru astfel de valori. În practică, dacă datele dumneavoastră este strict , acest caz margine nu are loc, dar este înțelept să se păzească împotriva ei.

Implementarea Bucket Sortare în Python

Mai jos este o implementare curată, gata de producție a unui fel de găleată pentru numerele de puncte plutitoare din intervalul .

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

Funcția folosește Python . Pentru fiecare găleată este foarte rapidă. Pentru utilizare, puteți înlocui cu un fel de inserție pentru partea inferioară a capului pe găleți mici.

Galetă Sortare pentru distanțe de arbitraj

Dacă datele dumneavoastră cu punct variabil se întinde pe o altă gamă decât , puteți normaliza valorile înainte de distribuție. Următoarea variație cartografiază orice interval până la :

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

Această versiune este mai generală, dar necesită cunoașterea sau calcularea intervalului. Funcționează bine atunci când distribuția datelor este aproximativ uniformă în cadrul acestui interval.

Analiza complexității

Înțelegerea costului computațional al sortului de găleți este esențială pentru a decide când să-l folosească.

Complexitatea temporală

  • Best case[ (date distribuite neuniform): [O(n + k], unde [k este numărul de găleți (de obicei ]n. Distribuția este O(n] și sortarea fiecărei găleți durează constant în medie, astfel încât în ansamblu O(n].
  • Caz peroxi[: O(n + n2/k)] dacă se utilizează sortat de inserție pentru găleți. Cu k = n, aceasta devine ]O(n).
  • Cel mai rău caz: O(n2)] atunci când toate elementele cad în aceeași găleată. Acest lucru se întâmplă atunci când datele nu sunt distribuite uniform sau când intervalul este foarte mic în raport cu numărul de elemente.

Complexitatea spaţială

Galeta necesită un spațiu suplimentar pentru găleți și conținutul lor. Cu k = n, acesta este ]O(n). Spațiul utilizat este comparabil cu cel al fuzionării și mai mare decât cel al sorților în loc precum fivesort.

Avantaje şi cazuri de utilizare

Galeta strălucește în scenarii specifice în care ipotezele sale dețin:

  • Date distribuite uniform cu puncte plutitoare
  • Seturi de date mari
  • Sortare externă
  • Calculator paralel și GPU

O putere notabilă este că tipul de găleată este stable (dacă tipul per-bucket este stabil), ceea ce înseamnă că ordinea relativă a elementelor egale este păstrată.

Limitări şi consideraţii

În ciuda eleganţei sale, găleata are mai multe limitări care pot face nepotrivit pentru sortarea generală:

  • Sensitivitatea la distribuția de intrare: Dacă datele sunt zgâriate (de exemplu, multe valori grupate împreună), majoritatea elementelor cad în câteva găleți, crescând costul de sortare la O(n2).
  • Cere cunoștințe anterioare ale intervalului: Fără a cunoaște valorile minime și maxime, nu poți crea efectiv găleți. Versiunea scalată de mai sus atenuează acest lucru, dar calculând gama adaugă o trecere suplimentară.
  • Memoria aeriană: Crearea nlistele Python pot consuma memorie semnificativă, în special pentru array-uri foarte mari. Listele sau array-urile conectate de array-uri pot reduce cheltuielile generale, dar lista de liste Python este simplă.
  • Deasupra sortării per-bucket: Sortarea multor găleți mici cu Python

Când nu se utilizează sortarea găleții

Evitați sortarea găleții atunci când datele nu sunt distribuite uniform, când intervalul este foarte mare în raport cu numărul de elemente, sau când memoria este extrem de constrânsă. În aceste cazuri, un tip de comparație ca quicksort sau heapsort este o alegere mai sigură.

Comparație cu alte alge de sortare

Galeata de tip găleată ocupă o nișă unică printre algoritmii de sortare. Iată cum se compară cu alternative comune:

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

Pentru numerele de puncte plutitoare, găleata de sortare adesea depăşeşte formele de tip radix (care necesită manipularea biţilor de flotoare) şi poate fi mai rapidă decât O [n log n]] comparaţie de tip atunci când datele sunt uniforme.

Sfaturi practice Python și optimizări

Alegerea numărului de găleţi

Setarea numărului de găleți egal cu numărul de elemente [k = n[]]) este o regulă standard a degetului mare. Mai puține găleți cresc dimensiunea medie a găleții și degradează performanța; mai multe găleți își pierd memoria fără a îmbunătăți viteza.

Folosind Sortare inserție pentru Bucket mici

Dacă doriţi control fin, înlocuiţi cu un fel de inserţie personalizat pentru găleţi mai mici decât, să zicem, 20 de elemente:

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

Acest lucru poate reduce cheltuielile generale, deoarece Python

Manipularea distribuţiilor neuniforme

Dacă știți că distribuția datelor nu este uniformă, dar încă mai doresc să utilizeze sortul găleată, puteți adapta limitele găleată. De exemplu, dacă datele urmează o distribuție normală, puteți crea găleți de lățime inegală pentru a echilibra sarcina. Cu toate acestea, acest lucru necesită analiza prealabilă a datelor și este rareori făcut în practică.

Resurse externe

Pentru o citire ulterioară, să analizăm următoarele referinţe:

Concluzie

Sortul de găleată este un algoritm elegant, eficient pentru sortarea numerelor de puncte plutitoare . . Mai ales atunci când datele sunt distribuite uniform și gama este cunoscută. Complexitatea sa liniară medie de caz îl face un instrument valoros în om de știință de date . Cu toate acestea, sensibilitatea sa la distribuția de intrare și cerințele suplimentare de memorie înseamnă că nu ar trebui să fie utilizate orbește. Prin înțelegerea când și cum să se aplice sortat găleată, și prin punerea în aplicare cu atenție în Python cu manipularea adecvată la margine-caz, puteți obține câștiguri semnificative de performanță peste tipurile de comparație general-scop.

Fie că sunteți sortarea milioane de măsurători senzori sau normalizarea ieșire dintr-o simulare stocastică, găleată de tip oferă o soluție rapidă, stabilă, și paralelizabilă