Είναι δυνατόν να βρούμε ένα τυχαίο στοιχείο σε ένα σετ σε συνεχή χρόνο;

ψήφοι
3

Έτσι, έτρεξα σε ένα πρόβλημα για την οικοδόμηση ενός συνόλου με λειτουργία getRandomElement (). Εύκολο αρκετά με την πρώτη ματιά. Αλλά το πιο πολύ το σκέφτομαι αυτό, το λιγότερο νομίζω ότι είναι δυνατόν να γίνει αυτό σε O (1) χρόνο πολυπλοκότητα. Δεν υπήρχε δεδομένη την απαίτηση για συνεχή φορά, αλλά όλοι ένα σετ σημαντικές λειτουργίες είναι σε συνεχή χρόνο, έτσι αισθάνομαι σαν να υπονοείται ότι αυτό θα πρέπει να γίνει σε σταθερό χρόνο.

Ο στόχος ενός συνόλου είναι η συνάρτηση κατακερματισμού για τη μείωση των συγκρούσεων. Το πρόβλημα γίνεται τώρα ότι αν απλά δημιουργήσετε τυχαίους ακέραιους αριθμούς και να προσπαθήσουμε να επιλέξετε το δείκτη χρησιμοποιώντας αυτό το τυχαίο ακέραιο αριθμό, που πιθανότατα θα τρέχει σε ένα «άδειο» υποδοχή στο σετ σας .... οπότε θα πρέπει να δημιουργήσει ένα νέο τυχαίο αριθμό και δοκιμάστε ξανά. Ουσιαστικά η καλύτερη συνάρτηση κατακερματισμού σας, το χειρότερο getRandomElement σας θα εκτελέσει χρήση αυτής της προσέγγισης.

Έτσι λοιπόν σκέφτηκα ... εντάξει, γιατί να μην αποθηκεύετε τους δείκτες μετά από κάθε εισαγωγή; Στη συνέχεια, δημιουργούν έναν τυχαίο αριθμό και να επιλέξετε ένα ευρετήριο από αυτή τη συλλογή των δεικτών. Σκέφτηκα ότι αυτό ήταν μια καλή ιδέα, αλλά στη συνέχεια έρχεται το πρόβλημα της αφαίρεσης στοιχείων. Θα πρέπει επίσης να αφαιρέσετε το αντίστοιχο δείκτη από τη λίστα δείκτη μας, καθώς και την κατάργηση του ίδιου του στοιχείου από το σύνολο μας. Πώς μπορούμε να βρούμε το σωστό δείκτη για να αφαιρέσετε πιο γρήγορα από ό, τι γραμμικό χρόνο ???

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

Δημοσιεύθηκε 20/10/2018 στις 12:35
πηγή χρήστη
Σε άλλες γλώσσες...                            


1 απαντήσεις

ψήφοι
5

Ναι, είναι δυνατό να οικοδομήσουμε μια δομή δεδομένων set-όπως που υποστηρίζει O (1) λειτουργία getRandomElement. Έχετε δίκιο σχετικά με την αποθήκευση στοιχείων σε μια σειρά. Το πρόβλημα της αφαίρεσης των στοιχείων δεν είναι πάρα πολύ δύσκολο.

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

Κατά την εκτέλεση getRandomElement(), απλά επαναλάβετε μέχρι να χτυπήσει ένα πραγματικό στοιχείο. Ο μέσος αριθμός των επαναλήψεων δεν είναι τίποτα περισσότερο από 2, γιατί η σειρά είναι πάντα τουλάχιστον μισογεμάτο, έτσι έχετε ακόμα Ξ σας (1) μέσος χρόνος για getRandomElement().

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

Απαντήθηκε 20/10/2018 στις 13:18
πηγή χρήστη

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