Ταξινόμηση#

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

Η σελίδα αναφοράς για την sort ορίζει τον τελεστή, το συμβόλαιο του συγκριτή και τους μηχανισμούς των $a/$b. Αυτό το κεφάλαιο υποθέτει ότι τα γνωρίζετε και εστιάζει στην ταχύτητα.

Ο συγκριτής είναι το κόστος#

Η ίδια η sort είναι μια σταθερή ταξινόμηση με συγχώνευση - γρήγορη, και όχι κάτι που μπορείτε να βελτιώσετε από την Perl. Αυτό που ελέγχετε είναι το πόση εργασία συμβαίνει μέσα σε κάθε σύγκριση. Δύο γεγονότα καθορίζουν τον προϋπολογισμό:

  • Ο συγκριτής τρέχει O(n log n) φορές. Για μια λίστα 100.000 στοιχείων αυτό είναι αρκετά πάνω από ένα εκατομμύριο κλήσεις.

  • Στο pperl, το μπλοκ του συγκριτή είναι ένα callback, και τα callbacks τρέχουν στον διερμηνευτή. Το JIT μεταγλωττίζει βρόχους, όχι σώματα συγκριτών sort (δείτε Μεταγλώττιση JIT), οπότε δεν μπορείτε να βασιστείτε στο JIT για να σώσει έναν ακριβό συγκριτή με τον τρόπο που σώζει έναν αριθμητικό βρόχο. Το κόστος του συγκριτή πληρώνεται πλήρως, σε κάθε κλήση.

Αυτό το δεύτερο γεγονός είναι ο ειδικός για το pperl λόγος που οι παρακάτω μετασχηματισμοί έχουν εδώ τόση σημασία όση και στην upstream Perl - αναμφισβήτητα περισσότερη, επειδή οι επιταχύνσεις του JIT αλλού κάνουν μια αμετασχημάτιστη ταξινόμηση να ξεχωρίζει πιο έντονα σε ένα προφίλ.

Η διάγνωση είναι πάντα η ίδια: αν η Μέτρηση δείχνει χρόνο συγκεντρωμένο σε έναν συγκριτή, το κλειδί επαναϋπολογίζεται σε κάθε σύγκριση. Υπολογίστε το αντ” αυτού μία φορά.

Ο μετασχηματισμός Schwartzian#

Όταν το κλειδί ταξινόμησης είναι ακριβό να εξαχθεί από κάθε στοιχείο - μια εξαγωγή υποσυμβολοσειράς, μια αναζήτηση πεδίου, ένα μήκος, ένας υπολογισμός - η αφελής ταξινόμηση το επαναϋπολογίζει σε κάθε σύγκριση:

# Slow: the key (-M $_) is computed twice per comparison, O(n log n) times.
my @sorted = sort { -M $a <=> -M $b } @files;

Ο μετασχηματισμός Schwartzian υπολογίζει κάθε κλειδί ακριβώς μία φορά, ταξινομεί βάσει του προϋπολογισμένου κλειδιού, μετά το απορρίπτει - μια map, μια sort, μια map:

my @sorted =
    map  { $_->[1] }                      # 3. strip the key, keep the element
    sort { $a->[0] <=> $b->[0] }          # 2. sort on the precomputed key
    map  { [ -M $_, $_ ] }                # 1. compute the key once per element
    @files;

Διαβάστε το από κάτω προς τα πάνω: η κατώτερη map χτίζει ένα ζεύγος [key, element] για κάθε στοιχείο (n υπολογισμοί κλειδιού), η sort συγκρίνει μόνο το φθηνό προϋπολογισμένο $_->[0] (κανένας υπολογισμός κλειδιού στον συγκριτή), και η ανώτερη map πετά το κλειδί. Το ακριβό κλειδί υπολογίζεται n φορές αντί για O(n log n) φορές.

Χρησιμοποιήστε τον όποτε το κλειδί κοστίζει περισσότερο για να εξαχθεί απ” ό,τι μια αριθμητική ή συμβολοσειρική σύγκριση. Για μια λίστα 100.000 στοιχείων ταξινομημένη βάσει ενός κλειδιού που χρειάζεται ένα μικροδευτερόλεπτο για να υπολογιστεί, η αφελής μορφή δαπανά δευτερόλεπτα μόνο στον υπολογισμό κλειδιού· ο μετασχηματισμός δαπανά ένα δέκατο του δευτερολέπτου.

Τα κομμάτια είναι η map και η sort - η σελίδα αναφοράς της sort δείχνει τον ίδιο μετασχηματισμό ως λυμένο παράδειγμα.

Ο μετασχηματισμός Guttman-Rosler#

Ο μετασχηματισμός Schwartzian ταξινομεί arrayrefs, που κοστίζει μια κατανομή arrayref και μια αποαναφορά ανά σύγκριση. Όταν το κλειδί μπορεί να κωδικοποιηθεί ως ένα πρόθεμα συμβολοσειράς σταθερού πλάτους, ο μετασχηματισμός Guttman-Rosler (GRT) πάει παραπέρα: πακετάρει το κλειδί και το στοιχείο σε μία μόνο συμβολοσειρά, ταξινομεί αυτές τις συμβολοσειρές με την προεπιλεγμένη συμβολοσειρική sort (καθόλου μπλοκ συγκριτή), μετά αφαιρεί το πρόθεμα.

my @sorted =
    map  { substr($_, 8) }                          # 3. strip the 8-char key prefix
    sort                                            # 2. plain string sort, no comparator
    map  { pack('N', $_->{priority}) . $_->{name} } # 1. fixed-width key + payload
    @records;

Το όφελος έχει δύο μέρη. Πρώτον, το κλειδί προϋπολογίζεται μία φορά, όπως στον Schwartzian. Δεύτερον - και αυτό είναι το διακριτό πλεονέκτημα του GRT - η sort δεν έχει μπλοκ συγκριτή, οπότε δεν υπάρχει καθόλου callback ανά σύγκριση. Η προεπιλεγμένη συμβολοσειρική sort συγκρίνει τις πακεταρισμένες συμβολοσειρές απευθείας, πράγμα που αποφεύγει εντελώς το κόστος του callback. Η αφαίρεση του callback του συγκριτή έχει μεγαλύτερη σημασία στο pperl ακριβώς επειδή εκείνο το callback θα έτρεχε στον διερμηνευτή.

Το κόστος του GRT είναι ότι το κλειδί πρέπει να είναι κωδικοποιήσιμο ώστε μια συμβολοσειρική σύγκριση κατά byte να παράγει τη σειρά που θέλετε:

  • Οι ακέραιοι πρέπει να πακετάρονται big-endian (pack 'N' / pack 'Q>') ώστε η σειρά των byte να ταιριάζει με την αριθμητική σειρά, και να μετατοπίζονται ώστε να είναι μη αρνητικοί (η συμβολοσειρική σύγκριση δεν έχει bit προσήμου).

  • Οι αριθμοί κινητής υποδιαστολής και οι προσημασμένοι αριθμοί χρειάζονται κωδικοποίηση με μεροληψία (bias) για να ταξινομηθούν σωστά ως byte - αρκετά λεπτεπίλεπτο ώστε ο Schwartzian να είναι συνήθως η καλύτερη επιλογή εκτός αν η ταξινόμηση είναι πραγματικά θερμή.

  • Κάθε κλειδί πρέπει να έχει το ίδιο πλάτος, αλλιώς το payload ενός κοντού κλειδιού διαρρέει μέσα στη σύγκριση.

Καταφύγετε στον GRT όταν η ταξινόμηση είναι θερμή, το κλειδί είναι μη προσημασμένος ακέραιος ή συμβολοσειρά, και ο Schwartzian εξακολουθεί να εμφανίζεται στο προφίλ. Για οτιδήποτε άλλο, ο Schwartzian είναι απλούστερος και σχεδόν πάντα αρκετά γρήγορος.

Φθηνότεροι συγκριτές χωρίς μετασχηματισμό#

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

  • Συγκρίνετε αριθμούς με <=>, συμβολοσειρές με cmp. Η χρήση της cmp σε αριθμούς μετατρέπει και τις δύο πλευρές σε συμβολοσειρά σε κάθε σύγκριση· η χρήση της <=> σε συμβολοσειρές είναι παγίδα μετατροπής σε αριθμό. Ταιριάξτε τον τελεστή με τα δεδομένα.

  • Διατάξτε τους αποκλεισμούς ισοβαθμίας από τον φθηνότερο πρώτα. Ένας πολυκλειδικός συγκριτής με || σταματά στο πρώτο μη μηδενικό αποτέλεσμα. Βάλτε το διακριτικό, φθηνό κλειδί πρώτο ώστε οι περισσότερες συγκρίσεις να μη φτάνουν ποτέ στο ακριβό:

    sort { $a->{rank} <=> $b->{rank}        # cheap, decides most pairs
    || $a->{name} cmp $b->{name} }      # only when ranks tie
       @rows;

  • Ταξινομήστε μία φορά, αντιστρέψτε ξεχωριστά. Για να ταξινομήσετε φθίνουσα, η αύξουσα ταξινόμηση και η κλήση της reverse είναι συχνά σαφέστερη και όχι πιο αργή από την αντιστροφή του συγκριτή, και κρατά τον συγκριτή στη φθηνότερη μορφή του.

Σειρά αποφάσεων#

  1. Προφιλάρετε. Αν η Μέτρηση δεν τοποθετεί τον χρόνο στην ταξινόμηση, αφήστε την ήσυχη.

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

  3. Αν η ταξινόμηση είναι ακόμη θερμή και το κλειδί είναι μη προσημασμένος ακέραιος ή συμβολοσειρά, εξετάστε τον μετασχηματισμό Guttman-Rosler για να εγκαταλείψετε εντελώς το callback του συγκριτή.

  4. Ξαναμετρήστε μετά από κάθε αλλαγή.

Δείτε επίσης#

  • sort - η αναφορά του τελεστή: συμβόλαιο συγκριτή, $a/$b, σταθερότητα.

  • map - το μετασχηματιστικό μισό τόσο της μορφής Schwartzian όσο και της Guttman-Rosler.

  • reverse - φθίνουσες ταξινομήσεις χωρίς αντιστροφή του συγκριτή.

  • Μέτρηση - επιβεβαιώστε ότι ο συγκριτής είναι το κόστος προτού τον μετασχηματίσετε.

  • Μεταγλώττιση JIT - γιατί ένα μπλοκ συγκριτή sort δεν μεταγλωττίζεται με JIT, οπότε το κόστος του πληρώνεται πλήρως.