Was ist in Java (1.5 oder höher) die beste Methode, ein (beliebiges) Element aus einem Set zu holen?

8

Im folgenden Code musste ich ein Element, ein beliebiges Element, aus toSearch holen. Ich war nicht in der Lage, eine nützliche Methode in der Set-Schnittstellendefinition zu finden, um nur ein einzelnes (zufälliges, aber nicht unbedingt zufälliges) Element der Menge zurückzugeben. Also habe ich die Methode toArray () [0] verwendet (im folgenden Code vorhanden).

%Vor%

Die andere Technik, die ich gesehen habe, ist, " (Coordinate) toSearch.toArray () [0] " mit " toSearch.iterator (). next () ". Welche Methode, toArray () oder iterator (), wird am ehesten am schnellsten mit dem geringsten GC-Effekt (Garbage Collection) ausgeführt?

Meine Intuition (nach dem Verfassen dieser Frage) ist, dass die zweite Technik, die den Iterator verwendet, sowohl schneller in der Ausführung als auch weniger Aufwand für den GC ist. Da die Implementierung des übergebenen Sets nicht bekannt ist (unter der Annahme, dass HashSet oder LinkedHashSet am wahrscheinlichsten ist), wie hoch ist der Aufwand in jeder der toArray () - oder iterator () -Methoden? Alle Einsichten dazu würden sehr geschätzt werden.

Fragen (von oben wiederholt):

  1. Welche Technik, toArray () oder iterator (), führt am ehesten zur schnellsten Ausführung mit dem geringsten GC (Garbage Collection) -Aufschlag?
    2.   
  2. Da ich nicht weiß, wie das übergebene Set implementiert wird (unter der Annahme, dass HashSet oder LinkedHashSet am wahrscheinlichsten ist), wie viel Overhead in jeder der toArray () - und iterator () -Methoden anfällt?
chaotic3quilibrium 04.12.2010, 23:52
quelle

5 Antworten

9

toSearch.iterator().next() ist schneller und weniger speicherintensiv, da keine Daten kopiert werden müssen, während toArray den Inhalt des Satzes dem Array zuordnet und kopiert. Dies ist unabhängig von der tatsächlichen Implementierung: toArray will immer Daten kopieren.

    
Cameron Skinner 04.12.2010, 23:57
quelle
1

Nach dem, was ich sehen kann, machen Sie Erste Suche in der Breite

Unten ist das Beispiel, wie es ohne toArray implementiert werden könnte:

%Vor%

Implementierungshinweise:

  

Und jetzt mache ich mir Sorgen, dass die Implementierung der contains () -Methode auf LinkedList bis zu einem vollständigen Scan der Inhalte vor der Rückgabe der Antwort durchgeführt werden kann.

Sie haben Recht mit dem vollständigen Scan (auch lineare Suche genannt). Dennoch, in Ihrem Fall ist es möglich, zusätzliche Set für die Verfolgung bereits besuchter Eckpunkte (BTW, eigentlich ist es Ihr Ergebnis!), Das würde Problem mit enthält Methode in O (1) Zeit zu lösen.

Prost

    
Petro Semeniuk 05.12.2010 00:11
quelle
1

So würde ich das umsetzen:

%Vor%

Anmerkungen:

  1. Wenn Sie darüber nachdenken, muss die Datenstruktur toSearch keine eindeutigen Elemente enthalten.
  2. Die Verwendung einer LinkedList für toSearch bedeutet, dass es eine einfache Methode gibt, um ein Element zu erhalten und es auf einmal zu entfernen.
  3. Wir können die Tatsache verwenden, dass Set.add(...) eine boolean zurückgibt, damit die Anzahl der Nachschlagevorgänge in result festgelegt wird ... im Vergleich zur Verwendung von Set.contains() .
  4. Es wäre besser, HashSet anstelle von LinkedHashSet für die Ergebnisse zu verwenden ... es sei denn, Sie müssen die Reihenfolge kennen, in der die Koordinaten durch die Füllung hinzugefügt wurden.
  5. Die Verwendung von == zum Vergleich von Value Instanzen ist möglicherweise ein bisschen schwierig.
Stephen C 05.12.2010 13:28
quelle
0

Nach Petros Antwort kopierte ich die Methode und führte sie nach seinen Vorschlägen neu ein. Es sieht so aus:

%Vor%

Beim Wechsel von "Setzen" in "Warteschlange" wurden meine Effizienzfragen auf die neue bedingte Prüfung verschoben, die ich hinzufügen musste: " if (! toSearch.contains (coordinateAdjacent)) ". Mit der Set-Schnittstelle verhinderte ich, dass Duplikate hinzugefügt wurden. Unter Verwendung der Warteschlangenschnittstelle muss ich überprüfen, dass ich kein Duplikat hinzufüge.

Und jetzt mache ich mir Sorgen, dass die Implementierung der contains () -Methode auf LinkedList bis zu einem vollständigen Scan der Inhalte vor der Rückgabe der Antwort durchgeführt werden kann. Also, vergleichen Sie diese Methode mit der, die ich ursprünglich gepostet habe, die wahrscheinlich effizienter sein wird (bevor ich eine Menge Zeit damit verbringe, die empirischen Tests zu machen)?

    
chaotic3quilibrium 05.12.2010 01:10
quelle
0

Okay, unten ist meine letzte Implementierung mit Feedback (hauptsächlich von Stephen, Cameron und Petro), die das vollständige Eliminieren des toArray () [] - vs-interator (). next () Konflikts beinhaltet. Und ich habe Kommentare eingestreut, um genauer zu unterscheiden, was passiert und warum. Und um besser zu verdeutlichen, warum ich konkret Petro's ursprünglichen Ratschlag "Benutze ein Tracking-Set" umgesetzt habe (unterstützt von Cameron). Und gleich nach dem Codeausschnitt werde ich es mit den anderen vorgeschlagenen Lösungen gegenüberstellen.

%Vor%

Ich habe die Methode auf mehrere wichtige Arten aktualisiert:

  1. Ein weniger Methodenparameter: Ich entfernte einen Parameter, da er von der Suche ableitbar war, und eliminierte ein mögliches logisches Problem, bei dem die Startkoordinate auf einen Ort zeigt, der den Wert! Enthält.
  2. Drei Sammlungen verfolgen die Suche; Bereich (Set), aktiviert (Set) und Kandidaten (Warteschlange). Die Code-Kommentare verdeutlichen die spezifische Verwendung von jedem. Verwendetes LinkedHashSet für zuverlässige Reproduzierbarkeit während der Verfolgung von Fehlern und Leistungsproblemen (http://stackoverflow.com/questions/2704597/iteration-order-of-hashset). Sobald es stabil ist, werde ich wahrscheinlich zu einer schnelleren HashSet-Implementierung zurückkehren.
  3. Der Test "Prüfen, ob bereits evaluiert" wurde vor dem Test "Ist-Wert" neu angeordnet, um nur jede Koordinate genau einmal zu besuchen. Dadurch wird vermieden, benachbarte Koordinaten mehr als einmal zu bearbeiten. Auch Stephens schlaue doppelte Verwendung der Set add () -Methode wurde mit einbezogen. Dies wird sehr wichtig, da das zu überflutende Gebiet labyrinthartiger wird (Schlangen- / Spinnen-).
  4. Halte das "==" für den Prüfwert, der einen Referenzvergleich erzwingt. Value ist als Java 1.5 Enum definiert und ich wollte nicht von HotSpot abhängig sein, um den Aufruf der .equals () Methode zu inline zu schreiben und auf einen Referenzvergleich zu reduzieren. Wenn Value sich jemals von einem Enum verändern sollte, könnte diese Wahl wiederkehren, um mich zu beißen. Tyvm an Stephen, dass er darauf hingewiesen hat.

Die Lösungen von Petro und Stephan besuchen die Koordinaten, die den Wert enthalten, nur einmal, müssen aber die Koordinaten, die den! -Wert mehr als einmal enthalten, erneut aufrufen, was zu mehreren doppelten Fetches / Wertüberprüfungen für Bereiche führen kann, die aus langen labyrinthartigen Tunneln bestehen. Während "lange labyrinthartige Tunnel" als pathologischer Fall angesehen werden können, ist es typischer für die spezielle Domäne, für die ich diese Methode brauche. Und meine "zweite" versuchte Lösung (die hatte die schlechte Leistung LinkedList enthält () Anruf) war fraglich als eine echte Antwort (Stephen zu diesem Thema).

Vielen Dank für Ihr Feedback.

Als nächstes gibt es viele empirische Tests mit einzelnen Variationen / Änderungen über Hunderte von Millionen von Aufrufen. Ich werde diese Antwort irgendwann dieses Wochenende mit Details aktualisieren.

    
chaotic3quilibrium 07.12.2010 04:54
quelle

Tags und Links

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Wie werden sowohl binäre als auch kontinuierliche Features im k-Nearest-Neighbor-Algorithmus verwendet?