Scala :: TreeMap更新後不均衡？

什麼是我想要做的是能夠調整TreeMap中的項目的鍵順序，因此Scala :: TreeMap更新後不均衡？

我可能能夠通過一些「靜態」數據，以找對象，不改變
的對象的位置（如果該映射爲弄平）應該尊重它的「優先級」

以下測試情況下可以很好地用於numEntries = 6，但大於7的值不起作用我並沒有真正理解那裏出了什麼問題，但我懷疑這棵樹不合格在一些更新/副本之後。那麼請問有人請指教 - 是我的錯，還是Scala 2.9中的TreeMap有某種錯誤？

UPDATE如果循環

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

    }

來源

2012-08-28 jdevelop

優先'1，直到numEntries'超過'1到（numEntries - 1）'。 –

我覺得非常不可能有一個在TreeMap基本操作中的錯誤 - 有大量的Scala 2.9.0之前，但現在有一個強大的測試套件支持RedBlack，它的後備存儲。

更可能的問題是您沒有全部訂單。說你有三個要素：

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要求總訂購 - 部分訂單有一個特定的特徵）。

讓我們創建兩個節點，以說明爲什麼可能會導致問題：

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

所以，d <一個< b <即一個可能的樹是：

 b 
    /\ 
    a e 
/
    d

現在，如果你嘗試查找c在這棵樹，你會先用b比較c，發現c比b更大。這意味着您只能看到包含e的正確分支，而您永遠也找不到d。

來源

2012-08-28 14:45:57

那麼，爲什麼如果我按相反順序迭代，它會正常工作呢？另外請注意，我沒有在地圖中包含「None」的項目，它僅在我知道「有效載荷」的情況下使用，但不知道項目的當前「訂單」。所以當我在地圖中插入某些東西時，它會定義嚴格而一致的排序。 – jdevelop

算法倒退時，算法只選擇「正確」比較是純粹的運氣。正如Daniel指出的那樣，你的「比較」功能被打破了，但這並不意味着它在「幸運」的情況下不能產生正確的結果。 – Landei

好吧，明白了。謝謝！ – jdevelop

Scala :: TreeMap更新後不均衡？

回答

相關問題