Ich habe ungefähr 420.000 Elemente, die ich einfach in einem Set oder einer Liste speichern muss. Die Einschränkungen sind jedoch, dass ich in der Lage sein muss, ein zufälliges Element auszuwählen und dass es schnell sein muss.
Anfangs habe ich eine ArrayList und eine LinkedList verwendet, aber mit so vielen Elementen war es sehr langsam. Als ich es profilierte, sah ich, dass die equals() -Methode in dem Objekt, das ich speicherte, ungefähr 21 Millionen Male in einer sehr kurzen Zeitperiode aufgerufen wurde.
Als nächstes habe ich ein HashSet versucht. Was ich an Leistung erlange, verliere ich an Funktionalität: Ich kann kein zufälliges Element auswählen. HashSet wird von einer HashMap unterstützt, die von einem Array von HashMap.Entry -Objekten unterstützt wird. Als ich jedoch versuchte, sie zu entlarven, wurde ich durch die verrückte private und paket-private Sichtbarkeit des gesamten Java Collections Framework behindert (sogar das Kopieren und Einfügen der Klasse funktionierte nicht, die JCF ist sehr "Verwenden Sie, was wir haben oder rollen Sie Ihre eigenen ").
Wie wählt man am besten ein Element aus, das in einem HashSet oder HashMap gespeichert ist? Aufgrund der Größe der Sammlung würde ich lieber keine Schleifen verwenden.
WICHTIG BEARBEITEN: Ich habe ein wirklich wichtiges Detail vergessen: genau wie ich die Collection verwende. Ich bevölkere die gesamte Sammlung am Bett des Tisches. Während des Programms wähle ich und entferne ein zufälliges Element, dann wähle und entferne ein paar mehr bekannte Elemente und wiederhole es dann. Das ständige Nachschlagen und Ändern ist die Ursache für die Langsamkeit
Es gibt keinen Grund, warum ein ArrayList oder ein LinkedList equals() aufrufen müsste ... obwohl Sie nicht wollen, dass Sie hier einen LinkedList haben, wie Sie einen schnellen Direktzugriff wünschen nach Index.
Ein ArrayList sollte ideal sein - erstellen Sie es mit einer geeigneten Kapazität, fügen Sie alle Elemente hinzu, und dann können Sie einfach immer eine Zufallszahl im entsprechenden Bereich auswählen und get(index) aufrufen, um den entsprechenden Wert zu erhalten .
HashMap und HashSet sind dafür einfach nicht geeignet.
Wenn ALL Sie eine große Sammlung von Werten erhalten und eine zufällige auswählen müssen, dann ist ArrayList (buchstäblich) perfekt für Ihre Bedürfnisse. Sie werden nicht wesentlich schneller (es sei denn, Sie gingen direkt zum primitiven Array, wo Sie Vorteile der Abstraktion verlieren.)
Wenn Ihnen das zu langsam ist, liegt das daran, dass Sie auch andere Operationen verwenden. Wenn Sie Ihre Frage mit ALLEN Operationen aktualisieren, die die Sammlung bearbeiten muss, erhalten Sie eine bessere Antwort.
Wenn Sie contains() nicht aufrufen (was equals() viele Male aufruft), können Sie ArrayList.get(randomNumber) verwenden und das ist O (1)
Sie können es nicht mit einem HashMap tun - es speichert die Objekte intern in einem Array, wobei der Index = hashcode für das Objekt ist. Selbst wenn Sie diese Tabelle hätten, müssten Sie raten, welche Buckets Objekte enthalten. Also ein HashMap ist keine Option für den wahlfreien Zugriff.
Vorausgesetzt, dass equals() -Aufrufe darauf zurückzuführen sind, dass Duplikate mit contains() aussortiert wurden, möchten Sie möglicherweise sowohl eine HashSet (für eine schnelle Suche nach bereits vorhandenen) als auch eine ArrayList (für schneller wahlfreier Zugriff). Oder, wenn Operationen nicht verschachteln, erstellen Sie zuerst eine HashSet , dann extrahieren Sie ihre Daten mit toArray() oder transformieren Sie sie in ArrayList mit dem Konstruktor der letzteren.
Wenn Ihre Probleme auf remove() Aufruf auf ArrayList zurückzuführen sind, verwenden Sie sie nicht und stattdessen:
set() ) das entfernte Element durch das letzte; Das wird natürlich die Reihenfolge der Elemente vermasseln, aber anscheinend brauchen Sie es nicht, nach der Beschreibung zu urteilen. Oder haben Sie ein anderes wichtiges Detail ausgelassen?
Tags und Links java collections hashmap hashset