Scalaで優先度キューのk番目の最小要素を取得するにはどうすればよいですか?

xorz57

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)
  }
}
sarveshseri

問題は、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(正確ではなく、特別な継承クラス)に保持します。この「配列」はヒープ化されたままです。そして、継承されたtakeAPIは、このヒープ化された配列のようなデータ構造の上で機能します。そしてk、最小ヒープ配列の最初の要素は確かにminimum k要素と同じではありません

さて、定義AがPriorityQueueサポートすることになっているenqueuedequeue最高の優先度(最初の)要素を維持するだけで、キュー内の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]

編集
0

コメントを追加

0

関連記事

分類Dev

優先キューの特定の要素を削除するにはどうすればよいですか?

分類Dev

Pythonで優先度キューの優先度関数を変更するにはどうすればよいですか?

分類Dev

ActiveAdminで親メニューの優先度を設定するにはどうすればよいですか?

分類Dev

HttpRuntime.Cacheオブジェクトのキャッシュアイテムの優先度を取得するにはどうすればよいですか?

分類Dev

Scala優先キューに注文を適用するにはどうすればよいですか?

分類Dev

辞書のキーリストの2番目の項目の最小値を取得するにはどうすればよいですか?

分類Dev

jQueryの.eachループから1番目、2番目、3番目の要素の値を取得するにはどうすればよいですか?

分類Dev

FCMメッセージの優先度を指定するにはどうすればよいですか?

分類Dev

PHPで多次元配列のn番目の要素を取得するにはどうすればよいですか?

分類Dev

C#で特定の優先度を持つWebsphere MQメッセージのみを取得するにはどうすればよいですか?

分類Dev

Seqのn番目の要素を取得するにはどうすればよいですか?

分類Dev

Javaで指定された範囲を持つサブ配列のk番目の要素を取得するにはどうすればよいですか?

分類Dev

優先度の高いGCMを送信するにはどうすればよいですか?

分類Dev

優先度の低い割り込みを終了するにはどうすればよいですか?

分類Dev

Slurmジョブに最大の優先度を設定するにはどうすればよいですか?

分類Dev

Android:NFCプロトコルの優先度を変更するにはどうすればよいですか?

分類Dev

プロセスのIO優先度を表示するにはどうすればよいですか?

分類Dev

JavaScript / Htmlで再生および一時停止できるビデオ要素の優先度を切り替えるにはどうすればよいですか?

分類Dev

Caps Lockキーを3番目のShiftキーにするにはどうすればよいですか?

分類Dev

2番目の変数でグループ化された単語頻度カウントを取得するにはどうすればよいですか(Python)

分類Dev

k番目の最大/最小要素はどういう意味ですか?

分類Dev

キューから要素のチャンクを取得するにはどうすればよいですか?

分類Dev

キューから特定の要素を取得するにはどうすればよいですか?

分類Dev

C ++で4つの値を持つ優先キューを定義するにはどうすればよいですか?

分類Dev

内部結合内の2番目の最小値を選択するにはどうすればよいですか?

分類Dev

画像から最大強度と最小強度の値を取得するにはどうすればよいですか?

分類Dev

このJSONデータの2番目の要素から最初の値を取得するにはどうすればよいですか?

分類Dev

Qtアプリケーションのメインスレッドで実行される関数をできるだけ高い優先度でキューに入れるにはどうすればよいですか?

分類Dev

Swiftで、名前付きのバックグラウンド優先SERIALキューを作成するにはどうすればよいですか?

Related 関連記事

  1. 1

    優先キューの特定の要素を削除するにはどうすればよいですか?

  2. 2

    Pythonで優先度キューの優先度関数を変更するにはどうすればよいですか?

  3. 3

    ActiveAdminで親メニューの優先度を設定するにはどうすればよいですか?

  4. 4

    HttpRuntime.Cacheオブジェクトのキャッシュアイテムの優先度を取得するにはどうすればよいですか?

  5. 5

    Scala優先キューに注文を適用するにはどうすればよいですか?

  6. 6

    辞書のキーリストの2番目の項目の最小値を取得するにはどうすればよいですか?

  7. 7

    jQueryの.eachループから1番目、2番目、3番目の要素の値を取得するにはどうすればよいですか?

  8. 8

    FCMメッセージの優先度を指定するにはどうすればよいですか?

  9. 9

    PHPで多次元配列のn番目の要素を取得するにはどうすればよいですか?

  10. 10

    C#で特定の優先度を持つWebsphere MQメッセージのみを取得するにはどうすればよいですか?

  11. 11

    Seqのn番目の要素を取得するにはどうすればよいですか?

  12. 12

    Javaで指定された範囲を持つサブ配列のk番目の要素を取得するにはどうすればよいですか?

  13. 13

    優先度の高いGCMを送信するにはどうすればよいですか?

  14. 14

    優先度の低い割り込みを終了するにはどうすればよいですか?

  15. 15

    Slurmジョブに最大の優先度を設定するにはどうすればよいですか?

  16. 16

    Android:NFCプロトコルの優先度を変更するにはどうすればよいですか?

  17. 17

    プロセスのIO優先度を表示するにはどうすればよいですか?

  18. 18

    JavaScript / Htmlで再生および一時停止できるビデオ要素の優先度を切り替えるにはどうすればよいですか?

  19. 19

    Caps Lockキーを3番目のShiftキーにするにはどうすればよいですか?

  20. 20

    2番目の変数でグループ化された単語頻度カウントを取得するにはどうすればよいですか(Python)

  21. 21

    k番目の最大/最小要素はどういう意味ですか?

  22. 22

    キューから要素のチャンクを取得するにはどうすればよいですか?

  23. 23

    キューから特定の要素を取得するにはどうすればよいですか?

  24. 24

    C ++で4つの値を持つ優先キューを定義するにはどうすればよいですか?

  25. 25

    内部結合内の2番目の最小値を選択するにはどうすればよいですか?

  26. 26

    画像から最大強度と最小強度の値を取得するにはどうすればよいですか?

  27. 27

    このJSONデータの2番目の要素から最初の値を取得するにはどうすればよいですか?

  28. 28

    Qtアプリケーションのメインスレッドで実行される関数をできるだけ高い優先度でキューに入れるにはどうすればよいですか?

  29. 29

    Swiftで、名前付きのバックグラウンド優先SERIALキューを作成するにはどうすればよいですか?

ホットタグ

アーカイブ