1

私は典型的な方法で使用してきた LinkedHashMap を持っています: 新しいキーと値のペアを最後に追加し、挿入順にアクセスします。ただし、マップの「先頭」にペアを追加する必要がある特別なケースがあります。これを行うための LinkedHashMap ソース内にいくつかの機能があると思いますが、プライベートなアクセシビリティがあります。

新しいマップを作成し、ペアを追加してから、すべての古いマッピングを追加するソリューションがあります。Java 構文:

newMap.put(newKey, newValue) 
newMap.putAll(this.map)
this.map = newMap

できます。しかし、ここでの問題は、メインのデータ構造 (this.map) を val ではなく var にする必要があることです。

誰もがより良い解決策を考えることができますか? Map コレクションによって提供される高速ルックアップ機能が絶対に必要であることに注意してください。プリペンディングのパフォーマンスはそれほど大したことではありません。

より一般的に言えば、Scala 開発者として、このような場合に var を回避するのにどれだけ苦労するでしょうか? LinkedHashMap の独自のバージョンを作成しますか? はっきり言って面倒くさい。

4

2 に答える 2

1

LinkedHashMapのコードを見ましたか? クラスにはフィールドfirstEntryがあり、をざっと見てみるだけで、新しいメソッドを追加するだけで必要な動作が得られるupdateLinkedEntriesサブクラスを作成するのは比較的簡単なはずです (テストされていません)。LinkedHashMapprependupdateLinkedEntriesPrepend

private def updateLinkedEntriesPrepend(e: Entry) {
    if (firstEntry == null) { firstEntry = e; lastEntry = e }
    else {
        val oldFirstEntry = firstEntry
        firstEntry = e
        firstEntry.later = oldFirstEntry
        oldFirstEntry.earlier = e
    }
}

これは、私がすぐにまとめたサンプル実装です (つまり、完全にテストされていません!):

class MyLinkedHashMap[A, B] extends LinkedHashMap[A,B] {

  def prepend(key: A, value: B): Option[B] = {
    val e = findEntry(key)
    if (e == null) {
      val e = new Entry(key, value)
      addEntry(e)
      updateLinkedEntriesPrepend(e)
      None
    } else {
      // The key already exists, so we might as well call LinkedHashMap#put
      put(key, value)
    }
  }

  private def updateLinkedEntriesPrepend(e: Entry) {
    if (firstEntry == null) { firstEntry = e; lastEntry = e }
    else {
      val oldFirstEntry = firstEntry
      firstEntry = e

      firstEntry.later = oldFirstEntry
      oldFirstEntry.earlier = firstEntry
    }
  }

}

このようにテストされました：

object Main {

 def main(args:Array[String]) {
    val x = new MyLinkedHashMap[String, Int]();

    x.prepend("foo", 5)
    x.prepend("bar", 6)
    x.prepend("olol", 12)

    x.foreach(x => println("x:" + x._1 + " y: " + x._2  ));
  }

}

これは、Scala 2.9.0 (ええ、更新する必要があります) では、

x:olol y: 12
x:bar y: 6
x:foo y: 5

簡単なベンチマークは、拡張された組み込みクラスと「マップ書き換え」アプローチの間のパフォーマンスの違いの桁違いを示しています（「ExternalMethod」でDebilskiの回答のコードを使用し、「BuiltIn」で私のコードを使用しました）：

 benchmark length        us linear runtime
ExternalMethod     10   1218.44 =
ExternalMethod    100   1250.28 =
ExternalMethod   1000  19453.59 =
ExternalMethod  10000 349297.25 ==============================
       BuiltIn     10      3.10 =
       BuiltIn    100      2.48 =
       BuiltIn   1000      2.38 =
       BuiltIn  10000      3.28 =

ベンチマーク コード:

  def timeExternalMethod(reps: Int) = {
    var r = reps
    while(r > 0) {
      for(i <- 1 to 100) prepend(map, (i, i))
      r -= 1
    }
  }

  def timeBuiltIn(reps: Int) = {
    var r = reps
    while(r > 0) {
      for(i <- 1 to 100) map.prepend(i, i)
      r -= 1
    }
  }

scala ベンチマーク テンプレートの使用。

于 2012-07-08T20:10:39.910 に答える
1

これは機能しますが、特に良いことでもありません:

import scala.collection.mutable.LinkedHashMap

def prepend[K,V](map: LinkedHashMap[K,V], kv: (K, V)) = {
  val copy = map.toMap
  map.clear
  map += kv
  map ++= copy
}

val map = LinkedHashMap('b -> 2)
prepend(map, 'a -> 1)
map == LinkedHashMap('a -> 1, 'b -> 2)
于 2012-07-08T20:12:20.807 に答える