Scala TreeSet vs Java TreeSet - Umfrage? - Hervorragende Bibliothek

Wenn ich den höchsten Eintrag in log(n) Zeit in Javas TreeSet entfernen möchte, verwende ich treeSet.pollFirst() - was ist das Äquivalent für Scalas mutable.TreeSet Klasse?Scala TreeSet vs Java TreeSet - Umfrage?

Wie auch immer, was ich wirklich will, ist eine Heap-ähnliche Datenstruktur der Prioritätswarteschlange, die mich removeMax, add und updatePriority in logarithmischer Zeit lässt. Ich schaute auf die Scala Sammlungen Bibliothek und ich bin verwirrt - während mutable.PriorityQueue lässt mich deque (dh removeMax) in logarithmischer Zeit - es bietet keine Möglichkeit, die Priorität in Log-Zeit zu aktualisieren (ich würde hacky scannen und entfernen Element und neu hinzufügen in lineare Zeit). In ähnlicher Weise würde mutable.TreeSet die Priorität in logarithmischer Zeit aktualisieren (durch hackiges Löschen und erneutes Hinzufügen), aber es hat keine removeMax (d. H. pollFirst) Operation. Welchen Sammelbehälter soll ich verwenden? Bitte verweisen Sie mich nicht auf externe Abhängigkeiten.

Quelle

2013-04-04 pathikrit

Wie denken Sie, 'updatePriority' würde mit' TreeSet' von Java funktionieren? – sharakan

Einfach (vorausgesetzt, Sie haben einen externen Vergleicher durch Überschreiben des TreeSet mit einer anonymen Klasse definiert). Sie löschen und fügen den Knoten einfach hinzu. Schau dir mein Beispiel an. Schau dir Zeile 19 und Zeile 33-36 hier an: https://github.com/pathikrit/scalgos/blob/master/temp/SandBox/AStar.java – pathikrit

Richtig, macht Sinn. Sie sollten den Knoten jedoch entfernen, bevor Sie ihn aktualisieren. – sharakan

Sie können die head und last Methoden in immutable.TreeSet verwenden, die O(log n) sind. Die gleichen Methoden existieren in mutable.TreeSet, wurden aber nicht überschrieben, um eine bessere Effizienz und amortisierte Zeit (in Scala 2.10) zu bieten. Die head Methode wird logarithmisch sein, kann aber dabei einen Iterator instanziieren. Das last-Verfahren wird es tatsächlich durchlaufen, wobei es eine lineare Komplexität aufweist. Die gute Nachricht ist, dass Sie mit einer benutzerdefinierten Ordering steuern können, was am kleinsten oder am größten ist - und es leicht von einem vorhandenen Ordering erhalten, indem Sie Ordering.reverse aufrufen.

Wenn Sie dieses Element entfernen müssen, verwenden Sie einfach -=. Sie können Ihre eigene implizite Wertklasse erstellen, um die Methode pollFirst im Baumsatz zu übernehmen.

implicit class MyExtensions[T](ts: mutable.TreeSet[T]) extends AnyVal { 
    def pollFirst(): T = { 
    val elem = ts.head 
    ts -= elem 
    elem 
    } 
}

Quelle

2013-04-04 12:26:02 axel22

Der Kopf und der Leisten sind gleichbedeutend mit 'peekFirst' und' peekLast' - was ich will ist ** 'poll' ** – pathikrit

Nachdem ein Element in einem' TreeSet' identifiziert wurde, ist es einfach es mit '- =' zu entfernen. – axel22

Ah, ok, aber das ist wesentlich hässlicher als das einfache 'pollLast' – pathikrit

keine Antwort, nur :) ein Vorschlag nicht vergessen, dass Sie Java-Bibliotheken von scala zugreifen können (gut, wenn Sie auf die JVM kompilieren :) also wenn Java TreeSet für Sie arbeitet, es verwenden :)

Sie können auch Ihre Anforderungen klären; Was wären die Parameter Ihrer updatePriority-Methode? Wessen Priorität versuchst du zu aktualisieren?

Quelle

2013-04-04 12:55:16 okaram

Scala TreeSet vs Java TreeSet - Umfrage?

Antwort

Verwandte Themen