Εισαγωγή στην μέτρηση

Η μέτρηση Ταξινόμηση είναι ένας αλγόριθμος ταξινόμησης που δεν βασίζεται σε σύγκριση που υπερέχει όταν ταξινομεί ακέραιους πάνω από ένα μικρό, γνωστό εύρος. Σε αντίθεση με τα είδη που βασίζονται στη σύγκριση, όπως Quicksort ή Mergesort, τα οποία βασίζονται σε συγκρίσεις στοιχείων κατά ζεύγη, η μέτρηση Ταξινόμηση καθορίζει την ταξινομημένη σειρά μετρώντας τη συχνότητα κάθε διακριτής τιμής. Αυτή η προσέγγιση αποδίδει γραμμική χρονική πολυπλοκότητα κάτω από ευνοϊκές συνθήκες, καθιστώντας την μια επιλογή μετάβαση σε πολλές εφαρμογές που είναι κρίσιμης απόδοσης όπου ο τομέας εισόδου είναι περιορισμένος.

Ο αλγόριθμος περιγράφηκε για πρώτη φορά από τον Harold H. Seward το 1954 και παραμένει μια βασική τεχνική στην επιστήμη των υπολογιστών. Η απλότητα και η αποτελεσματικότητά του το καθιστούν ιδανικό για εργασίες όπως η διαλογή των φοιτητικών ηλικιών, των βαθμών, ή οποιουδήποτε ακέραιου δεδομένων με μια μέτρια εξάπλωση. Με τη μόχλευση βοηθητική αποθήκευση ανάλογη με το εύρος τιμών, η μέτρηση Ταξινόμηση αποφεύγει το O(n log n) χαμηλότερο όριο της διαλογής σύγκρισης, επιτυγχάνοντας O(n + k) χρόνο όπου k είναι το εύρος των τιμών εισόδου.

Πώς λειτουργεί η Μέτρηση

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

  1. Μετρώντας: Δημιουργήστε μια σειρά αριθμών μεγέθους k (το εύρος των τιμών εισόδου), μονογραφήθηκε στο μηδέν. Επαναλάβετε μέσω της διάταξης εισόδου και αυξήστε τον αριθμό για κάθε τιμή.
  2. Υπολογιστικά προθέματα: Μεταμορφώστε τη συστοιχία καταμέτρησης σε μια συστοιχία άθροισμα προθέματος, όπου κάθε στοιχείο στο δείκτη i κατέχει τη σωρευτική καταμέτρηση στοιχείων μικρότερη ή ίση με i. Αυτό το βήμα καθορίζει τις θέσεις εκκίνησης για κάθε διακριτή τιμή στην ταξινομημένη έξοδο.
  3. Στοιχεία τοποθέτησης: Τράβηξε τη συστοιχία εισόδου από δεξιά προς αριστερά (για σταθερότητα), χρησιμοποίησε τη συστοιχία καταμέτρησης για να βρεις το σωστό δείκτη στη συστοιχία εξόδου, τοποθέτησε το στοιχείο εκεί και αποτύπωσε τον αριθμό. Η τελική έξοδος είναι ένα ταξινομημένο αντίγραφο της εισόδου.

Ο αλγόριθμος επιστρέφει μια νέα ταξινομημένη σειρά, αφήνοντας την αρχική αμετάβλητη. Μια παραλλαγή που ονομάζεται σε θέση Μετρώντας Ταξινόμηση υπάρχει αλλά σπάνια χρησιμοποιείται επειδή θέτει σε κίνδυνο είτε τη σταθερότητα είτε την απόδοση του χώρου.

Παράδειγμα βήμα ⁇ βήμα

Εξετάστε τη διαλογή της διάταξης [4, 2, 2, 8, 3, 1,] όπου οι τιμές κυμαίνονται από 0 έως 8.

  1. Κόμμα: Μεγέθη συστοιχίας 9 (0 ⁇ 18) → [0,1,2,1,0,0,0]. (Δείκτης 1 εμφανίζεται μία φορά, δείκτης 2 δύο φορές, δείκτης 3 δύο φορές, δείκτης 4 μία φορά, δείκτης 8 μία φορά.)
  2. Προκαθορισμένα ποσά: Μετασχηματισμός σε σωρευτικό → [0,1,3,5,6,6,6,6,7]. Τώρα κάθε τιμή μας λέει τη θέση εκκίνησης για τον αριθμό αυτό σε ταξινομημένη έξοδο.
  3. Έξοδος:[ Τράβερς αρχική συστοιχία από το τέλος: το πρώτο στοιχείο που διαβάζεται είναι 1 → θέση = αριθμός[1] - 1 = 0 → έξοδος[0]=1, αριθμός decrement[1] έως 0. Επόμενος είναι 3 → θέση = αριθμός[3] - 1 = 4 → έξοδος[4]=3, αριθμός[3]=4. Συνεχίστε μέχρι όλα τα στοιχεία να τοποθετηθούν. Τελική έξοδος: [1,2,2,3,3,4,8].

Αυτό το παράδειγμα δείχνει πώς η Μέτρηση Ταξινόμηση αποφεύγει εντελώς συγκρίσεις, βασιζόμενος αποκλειστικά σε αριθμητικές πράξεις.

Υπολογιστική πολυπλοκότητα

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

  • Καλύτερη, Μέση και Χειρότερη περίπτωση: O(n + k), όπου n είναι ο αριθμός στοιχείων και k είναι το εύρος τιμών εισόδου. Όταν το k είναι μικρό σε σχέση με το n, ο αλγόριθμος τρέχει σε γραμμικό χρόνο.
  • Συγκριτική σύγκριση σε είδη: Quicksort και Mergesort έχουν O(n log n) μέση πολυπλοκότητα. Για n = 106 και k = 1000, η μέτρηση Ταξινόμηση ( ⁇ 1.001.000 πράξεις) είναι περίπου 13 φορές ταχύτερη από μια τυπική ταξινόμηση O(n log n).

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

  • Πρωτότυπο: O(k) για τη συστοιχία καταμέτρησης, συν O(n) για τη συστοιχία εξόδου. Αυτή η μνήμη μπορεί να είναι απαγορευτική αν το k είναι μεγάλο (π.χ., διαλογή 32-bit ακέραιων όπου k = 232).
  • Σταθερή παραλλαγή: Απαιτεί βοηθητική διάταξη εξόδου μεγέθους n· ενσωματωμένες παραλλαγές θυσιάζουν σταθερότητα ή χρησιμοποιούν πολύπλοκο χειρισμό δείκτη.

Πότε να χρησιμοποιήσετε το είδος μέτρησης

Η μέτρηση Ταξινόμηση είναι πιο αποτελεσματική υπό τις ακόλουθες συνθήκες:

  • Η είσοδος αποτελείται από ακέραιους (ή δεδομένα που μπορούν να χαρτογραφηθούν σε ένα μικρό ακέραιο εύρος, όπως χαρακτήρες ή διακριτές κατηγορίες).
  • Το εύρος k δεν είναι σημαντικά μεγαλύτερο από το n. Ένας κοινός κανόνας του αντίχειρα είναι k ≤ O(n).
  • Η μνήμη δεν περιορίζεται σοβαρά, επειδή η σειρά καταμέτρησης και η ενδιάμεση μνήμη εξόδου απαιτούν επιπλέον χώρο.
  • Απαιτείται σταθερότητα (π.χ. διαλογή με πολλαπλά πλήκτρα). Η τυπική εφαρμογή είναι σταθερή όταν τα στοιχεία τοποθετούνται από τα δεξιά προς τα αριστερά.

Οι εξαιρετικές περιπτώσεις χρήσης περιλαμβάνουν τις βαθμολογίες ταξινόμησης (0 ⁇ 100), τις ηλικίες (0 ⁇ 20), τις κατηγορίες προϊόντων (μέχρι μερικές εκατοντάδες SKU), ή ως υπορουτίνα σε Radix Sort.

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

Παρά την ταχύτητά του, η Μέτρηση Ταξινόμηση έχει μειονεκτήματα που περιορίζουν τη δυνατότητα εφαρμογής του:

  • Ακέραιος μόνο: Δεν μπορεί να ταξινομήσει απευθείας αριθμούς κινητής υποδιαστολής ή συμβολοσειρές εκτός αν μετατραπούν σε ένα συνεχές ακέραιο σύνολο.
  • Εγγυημένο εύρος: Αν k νάνοι n ⁇ για παράδειγμα, διαλογή 100 αριθμών με τιμές μεταξύ 1 και 107 ⁇ η σειρά καταμέτρησης καταναλώνει τεράστια μνήμη ενώ διαλογή μόνο μερικά στοιχεία.
  • Μη-προσαρμοζόμενο: Η μέτρηση Κατάταξη απαιτεί πάντα σάρωση ολόκληρης της εισόδου και κατασκευή της διάταξης καταμέτρησης, ακόμα και αν τα δεδομένα έχουν ήδη ταξινομηθεί ή σχεδόν ταξινομηθεί.
  • Αιτιολογημένες τιμές: Τυποποιημένη μέτρηση Ταξινόμηση υποθέτει μη αρνητικούς ακέραιους. Για να χειριστείτε αρνητικά, μπορείτε να μετατοπίσετε τις τιμές αφαιρώντας το ελάχιστο (κάνοντας το εύρος 0 στο μέγιστο ⁇ min).

Αυτοί οι περιορισμοί σημαίνουν Μέτρηση Ταξινόμηση είναι ένα εξειδικευμένο εργαλείο, όχι μια καθολική αντικατάσταση για αλγόριθμους γενικής χρήσης.

Σύγκριση με τους σχετικούς αλγόριθμους ταξινόμησης

Ταξινόμηση μέτρησης εναντίον Radix

Radix Ταξινόμηση επεκτείνει την ιδέα με τη διαλογή ψηφίων από λιγότερο σημαντικά σε πιο σημαντικά, χρησιμοποιώντας ένα σταθερό είδος (συχνά Ταξινόμηση αρίθμησης) σε κάθε ψηφίο. Ενώ η αρίθμηση Ταξινόμηση λειτουργεί σε ένα πέρασμα πάνω από το πλήρες εύρος k, Radix Ταξινόμηση εκτελεί πολλαπλές περάσματα πάνω από ένα μικρότερο εύρος ψηφίων (π.χ., βάση 256), μειώνοντας τη χρήση μνήμης για μεγάλο k. Για παράδειγμα, ταξινόμηση 32-bit ακέραιοι με μέτρηση Ταξινόμηση θα απαιτούσε μια σειρά καταμέτρησης 232 καταχωρήσεων, ενώ το Radix Ταξινόμηση με 8-bit ψηφία απαιτεί 256 καταχωρήσεις ανά πέρασμα και μόνο τέσσερις περάσματα.

Είδος μέτρησης εναντίον του κουβά

Ταξινόμηση του κάδου Διανέμει στοιχεία σε έναν αριθμό κουβά και ταξινομεί κάθε κουβά ξεχωριστά (συχνά με το είδος εισαγωγής).Η μέτρηση Ταξινόμηση μπορεί να θεωρηθεί ως μια ειδική περίπτωση του κουβά Ταξινόμηση όπου κάθε κουβά αντιστοιχεί σε μια μόνο ξεχωριστή τιμή.

Εφαρμογή ενός Σταθερού Καταλόγου

Η σταθερότητα είναι σημαντική όταν ταξινομείται με ένα κλειδί ενώ διατηρείται η σχετική σειρά ίσων στοιχείων από ένα άλλο κλειδί. Ο τυπικός αλγόριθμος μέτρησης Ταξινόμησης είναι εγγενώς σταθερός όταν ο βρόχος τοποθέτησης εξόδου διασχίζει την είσοδο από τα δεξιά προς τα αριστερά. Εδώ είναι ένα περιγράμματα κειμένου της σταθερής παραλλαγής:

  1. Υπολογίστε την παράταξη καταμέτρησης όπως περιγράφεται.
  2. Μετατροπή σε προθέματα (θέσεις κάθε τιμής στην ταξινομημένη έξοδο).
  3. Επαναλάβετε τη διάταξη εισόδου με αντίστροφη σειρά. Για κάθε στοιχείο, τοποθετήστε το στη θέση που υποδεικνύεται από τον αριθμό του, και στη συνέχεια αποδείξτε ότι μετράτε.

Επειδή επεξεργαζόμαστε στοιχεία από το τέλος, η τελευταία εμφάνιση μιας δεδομένης τιμής πηγαίνει στο υψηλότερο δυνατό δείκτη, διατηρώντας σχετική σειρά. Αυτή η σταθερή έκδοση είναι απαραίτητη για το Radix Ταξινόμηση για να λειτουργήσει σωστά σε κάθε ψηφίο.

Πρακτικές εφαρμογές

  • Συστήματα διαβάθμισης εκπαίδευσης: Ταξινόμηση εκατοντάδων βαθμολογιών εξετάσεων (εύρος 0 ⁇ 100) σε χρόνο Ο(ν).
  • Βιοϊνπληροφορική: Ταξινόμηση ακέραιων αναγνώσεων αριθμών ή συχνοτήτων κ ⁇ μερ DNA όταν το μέγεθος του αλφαβήτου είναι μικρό (A, C, G, T).
  • Συντήρηση δείκτη βάσεων δεδομένων: Ταξινόμηση μοναδικών ακέραιων αναγνωριστικών σε εύρος αρκετά μικρών ώστε να χωρέσουν στη μνήμη.
  • Επεξεργασία εικόνας: Ταξινόμηση ιστογράμματος κάδους ή χρωματικές εντάσεις (0 ⁇ 255) όταν χτίζετε πίνακες αναζήτησης.
  • Η κοπή με δευτερεύον κλειδί: Χρησιμοποιείται μέσα στο Radix Sort, το οποίο είναι το άλογο εργασίας για αποτελεσματική διαλογή σε πολλές βιβλιοθήκες και γλώσσες (π.χ., το .NET runtime χρησιμοποιεί ένα προσαρμοστικό μείγμα αλγορίθμων συμπεριλαμβανομένης της μέτρησης Ταξινόμηση για μικρές σειρές).

Για περισσότερα σχετικά με τη θεωρία και τις παραλλαγές, συμβουλευτείτε τις έγκυρες αναφορές όπως [[LFT:0]]Wikipedia: Counting Sort[[LFT:1]] και [[LFT:2]GeeksforGeeks: Counting Sort[[LFT:3]]]. Πρακτικές συγκρίσεις με άλλους αλγόριθμους μπορούν να βρεθούν σε [[[LFT:4]]Briilliant’s Counting Sort article[[LFT:5]]].

Βελτιστοποίηση Μετρώντας Ταξινόμηση για Μεγάλες Ακτίνες

Όταν k είναι μεγάλο, αλλά n είναι επίσης μεγάλο, καθαρό είδος μέτρησης γίνεται μνήμη-εντατική.

  • Συμπυκνωμένη αραιότητα: Χρησιμοποιήστε έναν χάρτη hash αντί μιας παραπλήσιας συστοιχίας όταν το εύρος των χρησιμοποιούμενων τιμών είναι μεγάλο αλλά ο αριθμός των διακριτών τιμών είναι μικρός.
  • Υβριδικές προσεγγίσεις: Συνδυάστε την αρίθμηση Ταξινόμηση με άλλους αλγόριθμους. Για παράδειγμα, αν το εύρος υπερβαίνει το 106, χρησιμοποιήστε το Radix Ταξινόμηση με βάση που κρατά τα ψηφία εύρος μικρό.
  • Σε ⁇ θέση παραλλαγές: Μερικές βελτιστοποιήσεις μειώνουν τον επιπλέον χώρο στο O(k) χωρίς διάταξη εξόδου, αλλά γενικά θυσιάζουν σταθερότητα ή απαιτούν κύκλους για να εντοπίσουν θέσεις.

Συμπέρασμα

Η πολυπλοκότητα του χρόνου και η γραμμική απόδοση του O(n + k) το καθιστούν απαραίτητο σε σενάρια όπως η ταξινόμηση βαθμών, η διαλογή Radix και οι εφαρμογές με τα δεμένα ακέραια πλήκτρα. Ωστόσο, η εξάρτηση του αλγόριθμου από την ακέραια είσοδο και τη μνήμη του σε μεγάλα εύρος μας υπενθυμίζουν ότι κανένας ενιαίος τύπος δεν είναι βέλτιστος για όλες τις καταστάσεις. Κατανοώντας όταν η μέτρηση Ταξινόμηση υπερέχει ⁇ και όταν αποτυγχάνει ⁇ οι developers μπορούν να κατασκευάσουν ταχύτερα, πιο προβλέψιμα συστήματα. Για περαιτέρω ανάγνωση σε μη-συγκροτήματα που βασίζονται στην ταξινόμηση, δείτε TutorialsPoint: Counting Sort και Course: Counting Diction.