Ist es möglich, ein zufälliges Element in einem Satz in Konstante Zeit zu finden?

stimmen
3

Also lief ich auf ein Problem für den Aufbau eines Satzes mit einem getRandomElement () Funktion. Leicht genug auf den ersten Blick. Aber je mehr ich darüber nachdenken, desto weniger ich denke, es ist möglich, dies in O zu tun (1) Zeitkomplexität. Es war für eine konstante Zeit nicht gegeben Anforderung, aber alle eines Sets Hauptfunktionalität in konstanter Zeit, so dass ich das Gefühl, dass es impliziert, dass dies auch in konstanter Zeit durchgeführt werden sollte.

Das Ziel eines Satzes ist für die Hashfunktion Kollisionen zu reduzieren. Das Problem wird jetzt, wenn Sie einfach Zufallszahl erzeugen und versuchen, den Index mit dieser Zufallszahl zu wählen, werden Sie höchstwahrscheinlich läuft in einen „leeren“ Slot in Ihrem Set .... in dem Fall, dass Sie eine neue Zufallszahl erzeugen müssen und versuche es noch mal. Im Wesentlichen Ihrer Hashing-Funktion, desto besser werden die schlechtesten Ihre getRandomElement mit diesem Ansatz durchzuführen.

Also dachte ich ... okay, warum nicht speichern die Indizes nach jedem Einfügen? Dann eine Zufallszahl erzeugen und einen Index aus dieser Sammlung von Indizes auswählen. Ich dachte, das war eine gute Idee, aber dann kommt das Problem Elemente zu entfernen. Wir würden auch den entsprechenden Index aus unserem Index Liste entfernen müssen, sowie das Entfernen des Elements selbst aus unserem Set. Wie können wir die richtige Index schneller als die lineare Zeit zu entfernen finden ???

Wie auch immer, aus einem Satz ein zufälliges Element immer fühlt sich an wie es in besser als linearer Zeit durchgeführt werden kann. Btw, ich bin Umgang mit Kollisionen durch Verkettung. Ich will keine Zeit verschwenden, zu tun, was mathematisch unmöglich ist, aber ich bin auch kein Mathematiker und ich will nicht auf etwas verzichten, das tatsächlich möglich ist.

Veröffentlicht am 20/10/2018 um 12:35
quelle vom benutzer
In anderen Sprachen...                            


1 antworten

stimmen
5

Ja, es ist möglich, eine Reihe artige Datenstruktur aufzubauen, die O (1) getRandomElement Betrieb unterstützt. Sie sind direkt über Elemente in einem Array gespeichert werden. Das Problem Elemente zu entfernen, ist nicht allzu schwierig.

Das Geheimnis ist, um das Array zu komprimieren, sobald die Anzahl der Löcher zu groß ist (sagen wir, mehr als die Hälfte der Größe des Arrays). Auf diese Weise der fortgeführten Anschaffungslöschzeit ist immer noch O (1).

Bei der Durchführung getRandomElement(), wiederholen Sie , bis Sie ein aktuelles Element getroffen. Die durchschnittliche Anzahl der Wiederholungen ist nicht mehr als 2, da das Array immer mindestens halb voll ist, so dass Sie immer noch für O (1) durchschnittliche Zeit haben getRandomElement().

Edit: vielleicht eine einfachere Methode Elemente zu löschen wäre das letzte Element, um den frei gewordenen Platz zu bewegen.

Beantwortet am 20/10/2018 um 13:18
quelle vom benutzer

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