1

私がやろうとしているのは、TreeMapのアイテムのキーの順序を調整できるようにすることです。

  • 変化しない「静的」データでオブジェクトを見つけることができるかもしれません
  • オブジェクトの位置（マップが平坦化されている場合）は、オブジェクトの「優先度」を尊重する必要があります

次のテストケースは、numEntries = 6の場合はうまく機能しますが、7より大きい値の場合は機能しません。そこで何が問題になっているのかはよくわかりませんが、更新やコピーを行った後、ツリーが乱れるのではないかと思います。誰かがアドバイスしてくれませんか？それは私のせいですか、それともScala 2.9のTreeMapに何らかのバグがありますか？

ループの場合は更新

for (i <- 1 to (numEntries - 1)) {

交換された

for (i <- (numEntries - 1) to 1 by -1) {

すべてが正しく機能します。これがTreeMapのバグのように見えますか？

  import org.scalatest.FlatSpec
  import collection.immutable.TreeMap
  import org.junit.runner.RunWith
  import org.scalatest.junit.JUnitRunner

  @RunWith(classOf[JUnitRunner])
  class TreeMapTest extends FlatSpec {

    //val numEntries = 6;
    val numEntries = 10;

    sealed case class Entry(first: Option[Int], last: Int) extends Ordered[Entry] {

      def compare(that: TreeMapTest.this.type#Entry) = {
        if (first.isEmpty || that.first.isEmpty) {
          last compare that.last
        } else {
          (first.get compare that.first.get) match {
            case 0 => last compare that.last
            case x => x
          }
        }
      }

      def increase() = copy(first = Some(this.first.getOrElse(0) + 1))

    }

    type Container = TreeMap[Entry, Entry]

    "TreeMap" should "allow updates" in {
      var dataMap: Container = new Container() ++ (for (i <- 1 to numEntries) yield Entry(Some(0), i) -> Entry(Some(0), i))
      for (i <- 1 to (numEntries - 1)) {
        val key = new Entry(None, i)
        dataMap.get(new Entry(None, i)) match {
          case Some(e) =>
            val newEntry = e.increase()
            dataMap = (dataMap - key) + (newEntry -> newEntry)
          case None => fail("Can not find entry " + key)
        }
      }
    }

  }
4

1 に答える 1

7

基本的な操作にバグがある可能性は非常に低いと思いますTreeMap。Scala2.9.0以前はたくさんありましたが、今では強力なテストスイートRedBlackのバッキングがあります。これはバッキングストアです。

多くの場合、問題はあなたが完全な注文を持っていないことで発生します。次の3つの要素があるとします。

val a = Entry(Some(0), 3)
val b = Entry(Some(1), 0)
val c = Entry(None, 1)

次に、次のことが当てはまります。

scala> a < b
res39: Boolean = true

scala> b < c
res40: Boolean = true

scala> c < a
res41: Boolean = true

つまり、サイクルがあります。つまり、注文は全注文ではありません。TreeSet全順序付けを要求します（実際、特性はOrdered全順序付けを要求します-半順序には特定の特性があります）。

さらに2つのノードを作成して、それが問題を引き起こす可能性がある理由を示しましょう。

val d = Entry(Some(0), 1)
val e = Entry(Some(2), 4)

したがって、d <a<b<eです。考えられるツリーの1つは次のとおりです。

      b
     / \ 
    a   e
   /
  d

cここで、このツリーを検索しようとすると、最初にと比較cして、それが。よりも大きいbことがわかります。つまり、を含む正しいブランチのみを確認し、を見つけることはできません。cbed

于 2012-08-28T14:45:57.333 に答える