10

Java 1.6 では、NavigableMap (およびNavigableSet ) インターフェースが導入され、新しいインターフェースを実装するためにTreeMapが更新されました。とりわけ、NavigableMap は、「コレクション内のどの要素が X に最も近いか?」などの質問をするのに役立ちます (例と議論については、François Saradin によるこの優れたブログ投稿を参照してください)。

Scala 2.8 の TreeMap 実装で似たようなものを見つけたいと思っていましたが、残念ながらそうではないようです (少なくとも、明らかではありません)。Java の NavigableMap に似た別の Scala クラスまたは特性はありますか? そうでない場合、同様のことを達成するために使用できるいくつかの単純な Scala イディオムはありますか?

Java の TreeMap を使用できることはわかっていますが、Scala コレクション フレームワーク内にとどまりたいと思っています (簡単にするためだけに)。

4

2 に答える 2

2

不変コレクションでは、後方参照があると、コレクションを永続化できなくなります。そのため、代わりに、人々はジッパーを使用してそのような構造をナビゲートします. Anti-xmlには、XML を扱うときにジッパーを使用する良い例があります。

于 2011-08-29T19:37:29.273 に答える
1

このトピックに関するスレッドはこちら

それはあなたをそこに導くことができるSortedMap かもしれませんが、私がこれまでにテストしたことは、それが O(log(n)) であるべき検索方法であるかどうかわかりません:

def searchMap(m: SortedMap[Int,_], k: Int) = {
    val left  = m to(k) lastKey
    val right = m from(k) take(2) lastKey

    if (k - left < right - k)
        left
    else
        right
}

rangeImplの定義fromとto観点からすると、これは O(log(n)) のように見えますが、実際のタイミングに基づいて、n のすべての妥当な値に対して直線的に増加するように見えます。

よくわかりません。

于 2011-08-29T01:37:26.630 に答える