Εφαρμογή του κάδου Ταξινόμηση για τους αριθμούς των σημείων που επιπλέουν σε Python

Εισαγωγή στο καλάθι Ταξινόμηση για αριθμούς κινητής-σημείων

Το είδος του κάδου είναι ένας αλγόριθμος ταξινόμησης που βασίζεται στην κατανομή και καταμερίζει τα δεδομένα εισόδου σε έναν πεπερασμένο αριθμό “κουβάδων” και στη συνέχεια ταξινομεί τα περιεχόμενα κάθε κουβά ξεχωριστά. Όταν εφαρμόζεται σε αριθμούς κινητής υποδιαστολής που κατανέμονται ομοιόμορφα σε ένα γνωστό διάστημα — συνήθως [ ⁇ είδος κουβά μπορεί να επιτύχει γραμμική πολυπλοκότητα του μέσου χρόνου περίπτωση, καθιστώντας το ισχυρό υποψήφιο για εργασίες διαλογής υψηλών επιδόσεων.

Η βασική ιδέα είναι απλή: αντί να συγκρίνουμε κάθε ζεύγος στοιχείων (όπως σε σύγκριση είδη όπως quicksort ή mattesort), ο κουβάς ταξινομεί πρώτα τα στοιχεία σε κουβάδες με βάση τις τιμές τους. Κάθε κουβάς φυσικά συγκεντρώνει ένα στενό φάσμα τιμών. Μετά από αυτό, ένας απλός αλγόριθμος ταξινόμησης — συχνά εισαγωγή είδος ή ακόμη και μια αναδρομική κλήση για να ταξινομήσετε κουβά — τελειώνει το έργο. Τέλος, οι κουβάδες είναι συμπυκνωμένοι προκειμένου να παραχθεί η ταξινομημένη σειρά.

Αυτό το άρθρο παρέχει μια εις βάθος ματιά στην εφαρμογή του είδους κουβά για πλωτό-σημείο αριθμούς σε Python, που καλύπτουν τη μηχανική του, πολυπλοκότητα, τις δυνάμεις, παγίδες, και εφαρμογές πραγματικό-κόσμο.

Πώς λειτουργεί το σχήμα του κουβά

Το είδος του κάδου υποθέτει ότι η είσοδος κατανέμεται ομοιόμορφα σε ένα γνωστό εύρος, τυπικά . Ο αλγόριθμος προχωρά σε τρεις φάσεις:

1. Εγκαινίαση: Δημιουργία μιας σειράς από n άδειους κουβάδες, όπου n] είναι ο αριθμός στοιχείων.
2. Διανομή: Για κάθε στοιχείο , υπολογίστε τον δείκτη του κουβά (οι τιμές υπολογισμού είναι []) και τοποθετήστε το στοιχείο στον εν λόγω κάδο.
3. Κωδισμός και Κατεύθυνση[: Ταξινόμηση κάθε κουβά ξεχωριστά (χρησιμοποιώντας οποιοδήποτε σταθερό ή αποτελεσματικό εσωτερικό είδος), στη συνέχεια συμπυκνώνουν τους κουβάδες προκειμένου να παραχθεί η τελική ταξινομημένη σειρά.

Η βασική αντίληψη είναι ότι επειδή τα δεδομένα είναι ομοιόμορφα κατανεμημένα, κάθε κουβάς λαμβάνει περίπου [[LFT:0]]n / n = 1[LPT:1] στοιχείο κατά μέσο όρο. Αυτό διατηρεί το κόστος της διαλογής μεμονωμένων κουβάδων εξαιρετικά χαμηλό — συχνά σταθερό χρόνο ανά κουβά.

Χειρισμός υποθέσεων άκρων

Όταν ένας αριθμός κινητής υποδιαστολής ισούται ακριβώς με 1,0, ο υπολογισμένος δείκτης θα ήταν [[LFT:5]], ο οποίος είναι εκτός ορίων. Μια κοινή ρύθμιση είναι να σφίγγει το δείκτη σε [[LFT:6] για τέτοιες τιμές. Στην πράξη, αν τα δεδομένα σας είναι αυστηρά [[LFT:7]], αυτή η περίπτωση άκρη δεν συμβαίνει, αλλά είναι σοφό να φυλάγεστε από αυτό.

Εφαρμογή του κάδου Ταξινόμηση σε Python

Παρακάτω είναι μια καθαρή, έτοιμη για παραγωγή εφαρμογή του είδους κουβά για τους αριθμούς κινητής υποδιαστολής στην περιοχή .

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

Η συνάρτηση χρησιμοποιεί το ενσωματωμένο της Python για να ταξινομήσει κάθε κουβά. Για κουβάδες που είναι μικρά (συνήθως 0 ⁇ 2 στοιχεία), αυτό είναι πολύ γρήγορο. Για χρήση στην παραγωγή, μπορείτε να αντικαταστήσετε [ με το είδος εισαγωγής για ακόμη χαμηλότερα πάνω σε μικροσκοπικούς κουβάδες.

Ταξινόμηση του κάδου για εύρος αρθρώσεων

Εάν τα δεδομένα κινητής υποδιαστολής καλύπτουν μια περιοχή διαφορετική από , μπορείτε να ομαλοποιήσετε τις τιμές πριν από τη διανομή. Οι ακόλουθοι χάρτες παραλλαγής οποιαδήποτε κυμαίνονται σε :

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

Αυτή η έκδοση είναι πιο γενική, αλλά απαιτεί τη γνώση ή την υπολογιστική του εύρους. Λειτουργεί καλά όταν η κατανομή δεδομένων είναι περίπου ομοιόμορφη μέσα σε αυτό το εύρος.

Ανάλυση πολυπλοκότητας

Η κατανόηση του υπολογιστικού κόστους του είδους κουβά είναι απαραίτητη για να αποφασίσει πότε θα το χρησιμοποιήσει.

Πολύπλοκη χρονική στιγμή

• Καλύτερη περίπτωση (ομοιόμορφα κατανεμημένα δεδομένα): O(n + k), όπου k] είναι ο αριθμός των κουβάδων (συνήθως n).Η διανομή είναι O(n), και η διαλογή κάθε κουβάς απαιτεί σταθερό χρόνο κατά μέσο όρο, οπότε συνολικά O(n).
• Κάθισμα μέσου όρου: O(n + n2/k) αν χρησιμοποιηθεί είδος εισαγωγής για κουβάδες. Με k = n, αυτό γίνεται [O(n)].
• Κίνδυνος: O(n2) όταν όλα τα στοιχεία πέφτουν στον ίδιο κουβά. Αυτό συμβαίνει όταν τα δεδομένα δεν κατανέμονται ομοιόμορφα ή όταν το εύρος είναι πολύ μικρό σε σχέση με τον αριθμό των στοιχείων.

Πολυπλοκότητα χώρου

Το είδος του κάδου απαιτεί O(n + k) επιπλέον χώρο για τους κουβάδες και το περιεχόμενό τους. Με k = n, αυτός είναι O(n)]. Ο χώρος που χρησιμοποιείται είναι συγκρίσιμος με αυτόν του είδους συγχώνευσης και υψηλότερος από αυτόν του είδους του τόπου όπως η γρήγορη ταξινόμηση.

Πλεονεκτήματα και περιπτώσεις χρήσης

Το είδος του κάδου λάμπει σε συγκεκριμένα σενάρια όπου οι υποθέσεις του έχουν:

• Ομόλογα κατανεμημένα δεδομένα πλωτών σημείων — π.χ., ενδείξεις αισθητήρων, έξοδοι προσομοίωσης Μόντε Κάρλο, ή ομαλοποιημένες πιθανότητες.
• Μεγάλα σύνολα δεδομένων — το O(n) μέση απόδοση καθιστά ελκυστική τη διαλογή εκατομμυρίων πλωτήρων όπου τα είδη σύγκρισης θα ήταν λιγότερο αποδοτικά.
• Εξωτερική διαλογή — όταν τα δεδομένα κατοικούν στο δίσκο, οι κουβάδες μπορούν να επεξεργαστούν ανεξάρτητα και να γραφτούν σε ξεχωριστά αρχεία, κατόπιν να συμπυκνωθούν.
• Παραλλήλιος και υπολογιστικός GPU — κάθε κουβάς μπορεί να ταξινομηθεί ανεξάρτητα, επιτρέποντας μαζικό παραλληλισμό.

Μια αξιοσημείωτη δύναμη είναι ότι το είδος κουβά είναι σταθερό (αν το είδος ανά μπούκετ είναι σταθερό), δηλαδή διατηρείται η σχετική σειρά ίσων στοιχείων.

Περιορισμοί και Προτάσεις

Παρά την κομψότητά του, το είδος κουβά έχει αρκετούς περιορισμούς που μπορούν να το καταστήσουν ακατάλληλο για διαλογή γενικής χρήσης:

• Ευαισθησία στη διανομή εισροών[: Αν τα δεδομένα είναι πελεκημένα (π.χ., πολλές τιμές συσπειρωμένες μεταξύ τους), τα περισσότερα στοιχεία πέφτουν σε μερικούς κουβάδες, αυξάνοντας το κόστος διαλογής σε O(n2).
• Απαιτεί προηγούμενη γνώση του εύρους: Χωρίς να γνωρίζετε τις ελάχιστες και μέγιστες τιμές, δεν μπορείτε να δημιουργήσετε αποτελεσματικά κουβάδες. Η κλιμακωτή έκδοση παραπάνω μετριάζει αυτό, αλλά ο υπολογισμός του εύρους προσθέτει ένα επιπλέον πέρασμα.
• Απάντηση μνήμης: Δημιουργία n Οι λίστες Python μπορούν να καταναλώσουν σημαντική μνήμη, ειδικά για πολύ μεγάλες συστοιχίες. Οι συνδεδεμένες λίστες ή συστοιχίες των συρτακτών μπορούν να μειώσουν τα γενικά, αλλά η λίστα των καταλόγων Python είναι απλή.
• Υπεράνω διαλογής ανά μπουκιού[[LFT:1]]: Η ταξινόμηση πολλών μικροσκοπικών κουβάδων με τις κλήσεις λειτουργίας της Python [[LFT:16]] παράγει κλήσεις που μπορούν να προστεθούν. Για εξαιρετικά μικρούς κουβάδες, ένα συγκεκριμένο είδος εισαγωγής μπορεί να είναι πιο γρήγορο.

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