Πιο αποτελεσματικό αλγόριθμο ταξινόμησης για πολλά όμοια κλειδιά;

ψήφοι
8

Ποιο είναι το πιο αποτελεσματικό αλγόριθμο για την ομαδοποίηση πανομοιότυπα στοιχεία μαζί σε μια σειρά, δίνεται το ακόλουθο κείμενο:

  1. Σχεδόν όλα τα στοιχεία επαναλαμβάνονται αρκετές φορές.
  2. Τα στοιχεία δεν είναι απαραίτητα ακέραιοι ή οτιδήποτε άλλο που είναι εξίσου απλή. Η σειρά των πλήκτρων δεν είναι ακόμη καλά καθορισμένο, πόσο μάλλον μικρή. Στην πραγματικότητα, τα κλειδιά μπορεί να είναι αυθαίρετη Δομές. Αυτό αποκλείει τις πιο απλές μορφές της καταμέτρησης του είδους.
  3. Νοιαζόμαστε για δύο ασυμπτωτικές και μη ασυμπτωτικές ιδιότητες και η μπορεί να είναι μικρή μερικές φορές. Ωστόσο, όταν η είναι μικρό, η απόδοση εξακολουθεί να είναι σημαντική, διότι αυτή η λειτουργία μπορεί να κληθεί αρκετά εκατομμύρια φορές σε ένα βρόχο σε εκατομμύρια μικρά σύνολα δεδομένων. Αυτό αποκλείει οποιαδήποτε ακριβά συνάρτηση κατακερματισμού ή χρησιμοποιώντας μια σύνθετη δομή δεδομένων που χρειάζεται για να εκτελέσει πολλά εκχωρήσεις μνήμης.
  4. Τα δεδομένα μπορούν να ταξινομηθούν σε αυθαίρετη σειρά για όσο διάστημα είναι όλα πανομοιότυπα αντικείμενα ομαδοποιούνται.

Αν αυτή είναι η σύγχυση, εδώ είναι ένα παράδειγμα, υποθέτοντας μια τέτοια λειτουργία ονομάζεται groupIdentical:

uint[] foo = [1,2,3,2,1,5,4,5];
uint[] bar = groupIdentical(foo);
// One possibile correct value for bar:
// bar == [2,2,1,1,3,4,5,5].
// Another possible correct answer:
// bar == [1,1,2,2,5,5,4,3].

Ωστόσο, ως υπενθύμιση, δεν μπορούμε να υποθέσουμε ότι τα δεδομένα αποτελείται ως ακέραιοι.

Επεξεργασία: Σας ευχαριστώ για τις απαντήσεις. κύριο πρόβλημά μου με τον κατακερματισμό ήταν ότι οι πίνακες κατακερματισμού εκτελούν κατανομές μνήμης για συχνά. Αυτό που κατέληξε να κάνει ήταν να γράφει τη δική μου πίνακα κατακερματισμού που χρησιμοποιεί ένα κατανεμητή περιοχή που είχα γύρω για να πάρει γύρω από αυτό το πρόβλημα. Δουλεύει καλά.

Δημοσιεύθηκε 09/12/2008 στις 22:00
πηγή χρήστη
Σε άλλες γλώσσες...                            


9 απαντήσεις

ψήφοι
10

Νομίζω ότι θα μπορούσε να hash μόνο τα αντικείμενα, δεδομένου ότι το πραγματικό προκειμένου να μην έχει σημασία, μόνο ομαδοποίηση. Πανομοιότυπα αντικείμενα θα καταλήξουν συγκεντρώνονται στο ίδιο κουβά. Αυτό προϋποθέτει ότι κάθε είδος που σας ενδιαφέρει έχει τη δική του λειτουργία hash του, ή μπορείτε να ορίσετε τη δική σας και υπερφόρτωση του (λαμβάνοντας κάθε τύπου ως παράμετρος σε διαφορετικό ορισμό της συνάρτησης hashCode).

Για να αποφύγετε συγκρούσεις σε όλους τους τύπους δεδομένων (τόσο χορδές δεν καταλήγουν στον ίδιο κουβά όπως διπλασιάζεται, για παράδειγμα), τότε θα πρέπει να κωδικοποιήσει τον τύπο δεδομένων στο hash. Έτσι, για παράδειγμα, αν έχετε ένα hash 32-bit, ίσως τα πρώτα 5 bits μπορεί να κωδικοποιήσει το είδος των δεδομένων, ώστε να μπορείτε να έχετε 32 διαφορετικά είδη στο ίδιο χάρτη κατακερματισμού.

EDIT: Επιτρέψτε μου να προσθέσω ότι ο λόγος που είμαι προτείνοντας έναν χάρτη προσαρμοσμένο hash είναι επειδή δεν ξέρω από αυτή που εκθέτει αρκετά από την εσωτερική εφαρμογή του για να πάρει τις τιμές από κάθε κάδο. Μπορεί να υπάρχει μια τέτοια εφαρμογή που δεν ξέρω από. Υπάρχουν πολλά πράγματα που δεν ξέρω. :)

Απαντήθηκε 09/12/2008 στις 22:04
πηγή χρήστη

ψήφοι
4

Η μαγική λέξη που ψάχνετε εδώ είναι πολλαπλό σύνολοτσάντα ). Δεν είναι πραγματικά ένα είδος καθόλου, αφού δεν νοιάζονται για το σκοπό εφ 'όσον έχετε όλα τα στοιχεία με την ίδια πλήκτρα ομαδοποιούνται. Υπάρχουν πολλές κονσέρβες εφαρμογές διαθέσιμες, ανάλογα με τη γλώσσα που χρησιμοποιείτε, αλλά σε γενικές γραμμές η κατακερματίζεται έκδοση παραπάνω είναι ασυμπτωτικά βέλτιστος, πιστεύω ότι: insert()είναι σταθερά χρόνου, δεδομένου ότι μπορείτε να υπολογίσετε ένα hash σε O (1) και να προσθέσετε συγκρούονται ένθετα σε μια λίστα σε O (1) χρόνο? μπορείτε να ανακτήσετε ένα στοιχείο από τους κάδους σε O (1) χρόνο, απλά αρπάξτε το πρώτο στον κάλαθο των αχρήστων? και μπορείτε κατά συνέπεια να συλλέγουν όλα αυτά σε O (n) χρόνο, δεδομένου ότι θα ανακτήσετε n στοιχεία με O (1) για κάθε στοιχείο.

Απαντήθηκε 09/12/2008 στις 23:17
πηγή χρήστη

ψήφοι
3

Ένα καλπάζοντας συγχωνευτική, όπως ενσωματωμένο είδος (βλ πύθωνα του timsort ), έχει καλή αναμενόμενη απόδοση όταν υπάρχουν μεγάλες πίστες της ήδη ταξινομηθεί δεδομένα (όπως, στο παράδειγμά σας, πανομοιότυπα αντικείμενα) - θα παραλείψετε O (log ( N)) λειτουργούν ανά συγχώνευση. Μπορείτε, επίσης, να διανείμει συγχωνευτική σε πολλές CPU και δίσκων, αν το σύνολο δεδομένων σας είναι εξαιρετικά μεγάλο (αυτό ονομάζεται «εξωτερική» είδος). Ωστόσο, θα είναι χειρότερη περίπτωση O (* log (N)).

Τα μόνο τα είδη που είναι ταχύτερη από ό, τι * log (N) μετρώντας τα είδη, που εκμεταλλεύονται κάποια κοινή ιδιότητα των πλήκτρων. Για να χρησιμοποιήσετε ένα γραμμικό χρόνο είδος (πίνακας κατακερματισμού ή ρίζας / κουβά είδος), θα πρέπει να hash το struct να παράγει κάποιο είδος αριθμητικό πλήκτρο.

Radix είδος θα κάνει πολλαπλά περάσματα μέσα από τα πλήκτρα, έτσι ώστε με την αναμενόμενη ώρα της θα είναι μεγαλύτερη από ό, τι ένα hashtable προσέγγιση? και, δεδομένου ότι δεν νοιάζονται για λεξικογραφική σειρά, η λύση πίνακα κατακερματισμού ακούγεται καλύτερα για σας, αν μπορείτε να αντέξετε οικονομικά για τον κατακερματισμό των κλειδιών.

Απαντήθηκε 09/12/2008 στις 22:10
πηγή χρήστη

ψήφοι
1

Νομίζω ότι κατακερματισμού σε κάδους θα ήταν η καλύτερη λύση, αν υποτεθεί ότι υπάρχει ένα κατακερματισμού που διατηρεί χειριστή = χαρτογράφησης (0.0 μπορεί να μην hash το ίδιο πράγμα -0.0, αλλά θα μπορούσαν να είναι «ίσο»). Υποθέτοντας ότι έχετε μόνο μια ίση και λιγότερο από ό, τι χειριστή, θα μπορούσε να εφαρμόσει μια στοιχειώδη αλγόριθμο γρήγορης ταξινόμησης του να πάρει το πρώτο στοιχείο ως άξονα, και τη θέση του κάτω από σε μια ομάδα, και μεγαλύτερη από ό, τι στην άλλη ομάδα, και στη συνέχεια, επαναλαμβάνοντας η διαδικασία σε κάθε ομάδα.

Απαντήθηκε 09/12/2008 στις 22:16
πηγή χρήστη

ψήφοι
1

3-way QuickSort αποδίδει πολύ καλά, όταν υπάρχει μεγάλος αριθμός διπλότυπων.

Απαντήθηκε 09/12/2008 στις 22:14
πηγή χρήστη

ψήφοι
0

Απλό αλγόριθμο με σκοπό την απόδοση των O (n (n-1) / 2) έχει ως εξής:

  1. Ας υποθέσουμε διάταξη εισαγωγής ονομάζονται ως μέγεθος εισόδου έχοντας ως n.
  2. Διαθέσει ένα μνήμη για συστοιχία επιστροφής με ίδιο μέγεθος ονομάζεται ως Αποτέλεσμα
  3. Διαθέστε μνήμη για Boolean σειρά με το ίδιο μέγεθος ονομάζεται ως Επισκέφτηκε και που όλα πήγαν στον ως ψευδή
  4. Ας υποθέσουμε ότι υπάρχει μια ίση λειτουργία που ονομάζεται ως Ίσο επιστρέψει true αν τα δύο αντικείμενα είναι ίσα άλλο λάθος.
  5. Ας υποθέσουμε δείκτης συστοιχία ξεκινά από 1 έως n
  6. Παρακαλώ δείτε τον κωδικό Ψευδο C παρακάτω:
function groupIdentical(Input) 
{
    k=1;
    for i=1 to n 
    {
        Visited[i]=false ;
    }

    for i=1 to n
    {
        if( !Visited(i) )
        {   
            Result[k++]=Input[i];
            for j= (i+1) to n
            {
                if( Equals(i,j) )
                {
                    Result[k++]=Input[j];
                    Visited[j]=true;
                }   
            }
        }
    }
    return Result;
}
Απαντήθηκε 10/12/2008 στις 08:16
πηγή χρήστη

ψήφοι
0

Ίσως ένα R + B ή AVL δέντρο; Στη συνέχεια και πάλι - θα εξακολουθεί να είναι τελικά O (NlogN). Θα μπορούσε κάλλιστα να χρησιμοποιήσει heapsort - δεν θα είναι χειρότερη και χωρίς επιπλέον χρήση μνήμης ...

Απαντήθηκε 09/12/2008 στις 22:36
πηγή χρήστη

ψήφοι
0

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

Απαντήθηκε 09/12/2008 στις 22:19
πηγή χρήστη

ψήφοι
0

Εάν γνωρίζετε το εύρος των πιθανών τιμών, και αυτό είναι μικρό, μπορείτε να κάνετε: (ψευδο-ish κώδικα)

uint[] bucket = new int[10];
foreach(uint val in foo) {
    ++bucket[val];
}

uint bar_i = 0;
uint[] bar = new int[foo.length];
foreach(int val = 0; val < 10; val++) {
    uint occurrences = bucket[val];
    for(int i=0; i < occurrences; i++) {
        bar[bar_i++] = val;
    }
}
Απαντήθηκε 09/12/2008 στις 22:16
πηγή χρήστη

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more