8

log(n)Java ので時間的に最も高いエントリを削除したい場合はTreeSet、次を使用しますtreeSet.pollFirst()- Scala のmutable.TreeSetクラスに相当するものは何ですか?

とにかく、私が本当に欲しいのは、ヒープのようなプライオリティ キュー データ構造でremoveMaxありadd、updatePriority対数時間で実行できます。Scalaコレクションライブラリを見て、混乱していmutable.PriorityQueueます-対数時間でdeque(つまりremoveMax)許可しますが、ログ時間で優先度を更新する方法がありません(アイテムをハックしてスキャンして削除し、線形時間で再追加する必要があります) . 同様に、対数時間で優先度を更新できますが (ハッキリと削除して再追加することにより)、 (つまり) 操作mutable.TreeSetはありません。どのコレクション コンテナを使用すればよいですか? 外部依存関係について私に言及しないでください。removeMaxpollFirst

4

2 に答える 2

3

headでおよびlastメソッドを使用できimmutable.TreeSetますO(log n)。にも同じメソッドが存在しますがmutable.TreeSet、効率と償却時間を向上させるためにオーバーライドされていません (Scala 2.10)。headメソッドは対数になりますが、そうするときに反復子をインスタンス化する場合があります。メソッドは実際にそれlastを走査し、線形の複雑さを持ちます。幸いなことに、カスタムを使用して最小または最大を制御でき、 を呼び出すことOrderingで既存のものから簡単に取得できます。OrderingOrdering.reverse

その要素を削除する必要がある場合は、単純に-=. 独自の暗黙的な値クラスを作成pollFirstして、ツリー セットのメソッドをピギーバックできます。

implicit class MyExtensions[T](ts: mutable.TreeSet[T]) extends AnyVal {
  def pollFirst(): T = {
    val elem = ts.head
    ts -= elem
    elem
  }
}
于 2013-04-04T12:26:02.227 に答える
1

答えではなく、単なる提案です:) scalaからJavaライブラリにアクセスできることを覚えておいてください(JVMにコンパイルする場合:)したがって、JavaのTreeSetが機能する場合は、それを使用してください:)

要件を明確にすることもできます。updatePriority メソッドのパラメーターは何ですか? 誰の優先度を更新しようとしていますか?

于 2013-04-04T12:55:16.867 に答える