Scalaで優先度キューのk番目の最小要素を取得するにはどうすればよいですか?
以下を試してみましたが、間違っているようです!
import collection.mutable
object Main {
def main(args: Array[String]): Unit = {
val asc = Ordering.by((_: (Double, Vector[Double]))._1).reverse
val pq = mutable.PriorityQueue.empty[(Double, Vector[Double])](asc)
pq.enqueue(12.4 -> Vector(22.0, 3.4))
pq.enqueue(1.2 -> Vector(2.3, 3.2))
pq.enqueue(9.1 -> Vector(12.0, 3.2))
pq.enqueue(32.4 -> Vector(22.0, 13.4))
pq.enqueue(13.2 -> Vector(32.3, 23.2))
pq.enqueue(93.1 -> Vector(12.0, 43.2))
val k = 3
val kthMinimum = pq.take(k).last
println(kthMinimum)
}
}
問題は、PriorityQueue
プロパティと継承されたコレクションメソッドtake
などの非互換性です。Scalaコレクションの奇妙な実装問題の別の例。
Javaにも同じ問題がありますPriorityQueue
。
import java.util.PriorityQueue
val pQueue = new PriorityQueue[Integer]
pQueue.add(10)
pQueue.add(20)
pQueue.add(4)
pQueue.add(15)
pQueue.add(9)
val iter = pQueue.iterator()
iter.next() // 4
iter.next() // 9
iter.next() // 10
iter.next() // 20
iter.next() // 15
したがって、PriorityQueue
データを基礎となるものArrayBuffer
(正確ではなく、特別な継承クラス)に保持します。この「配列」はヒープ化されたままです。そして、継承されたtake
APIは、このヒープ化された配列のようなデータ構造の上で機能します。そしてk
、最小ヒープ配列の最初の要素は確かにminimum k
要素と同じではありません。
さて、定義AがPriorityQueue
サポートすることになっているenqueue
とdequeue
。最高の優先度(最初の)要素を維持するだけで、キュー内のk番目の要素を確実に提供することはできません。
これはJavaとScalaの両方の実装で問題になると私は言いますが、これを正しく実装することは不可能です。なぜこれらの誤解を招くメソッドがまだPriorityQueue
実装に存在しているのか疑問に思います。それらを削除することはできませんか?
要件に適した最も厳密なAPIを使用することを強くお勧めします。言い換えれば、キューAPIに固執し、継承されたAPIメソッドを使用しないでください(これは奇妙なことをする可能性があります)。
ただし、それを行うための良い方法はありません(これは、に明示的に必要なものではないためPriorityQueue
)。
これdequeueing k times
は、時間計算量がのループで簡単に実現できk * log(n)
ます。
val kThMinimum = {
val pqc = pq.clone()
(1 until k).foreach(i => pqc.dequeue())
pqc.dequeue()
}
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加