scala treeset無法刪除元素

我正在使用scala.collection.mutable.TreeSet，並遇到一個問題，在調用-=時無法刪除元素。scala treeset無法刪除元素

我的代碼：

val discovered = new TreeSet[Position]()(Ordering by { position => estimation(position) }) 
//Position is defined as: type Position = (Int, Int) 

discovered += start 
var x = 0 
while(!discovered.isEmpty){ 
    val current = discovered.head 
    println(discovered) 
    discovered -= current 
    println(discovered) 
    x += 1 
    println(s"$x $current") 

    [...] //Code to process current and discover new positions 
}

以下示例顯示了，即（18.46）不會被刪除。直到那一刻，清除工作完美。我還有其他的測試用例，這些測試用例可以完美地工作，而其他情況下，只要達到大約100次迭代，這個問題就不會發生。我已經得到了與TreeSet的不變實現相同的結果。輸出

部分：

TreeSet((22,42), (18,46), (21,44), (24,46), (22,47), (21,43), (21,47), (23,47), (24,47)) 
TreeSet((18,46), (21,44), (24,46), (22,47), (21,43), (21,47), (23,47), (24,47)) 
14 (22,42) 
TreeSet((18,46), (21,44), (22,41), (24,46), (22,47), (21,43), (21,47), (23,47), (24,47)) 
TreeSet((18,46), (21,44), (22,41), (24,46), (22,47), (21,43), (21,47), (23,47), (24,47)) 
15 (18,46) 
TreeSet((18,46), (21,44), (22,41), (24,46), (22,47), (21,43), (21,47), (23,47), (24,47), (17,46)) 
TreeSet((18,46), (21,44), (22,41), (24,46), (22,47), (21,43), (21,47), (23,47), (24,47), (17,46)) 
16 (18,46)

來源

2016-04-24 TheJP

如何定義估計（位置）？也許排序不健壯？ – Suma

'val estimation = new HashMap [Position，Float] .withDefaultValue（Float.PositiveInfinity）' 當估計值發生變化時，總是更新'discovered'： 'estimate（somePosition）= newScore; if（alreadyDiscovered）{discovered - = somePosition} discover + = somePosition' – TheJP

這是一個可變的散列表嗎？是否有任何值填充它？ – Suma

-1

感謝大家的回答！排序與問題有關，所以發現錯誤很有幫助。

說明：

我實現了很多我的代碼基礎完全功能。對於這種算法，由於幾個原因是不可能的。另外：如果有一個PriorityQueue，它有一個updateElement（）函數，我會用它代替TreeSet來獲得更好的性能，並避免我遇到的問題。

我的解決辦法：

象曰：我要實現它可變的，大多是勢在必行。這個問題在代碼

estimation(somePosition) = newScore 
if(alreadyDiscovered){ discovered -= somePosition } 
discovered += somePosition

卸下somePosition從discovered正在利用的排序，這是在該行改變上述的那些行。所以當RB樹嘗試刪除元素時，它不會再找到它。 下面的代碼正在爲所有測試用例

if(alreadyDiscovered){ discovered -= somePosition } 
estimation(somePosition) = newScore 
discovered += somePosition

如果有更好的數據結構比TreeSet的香草斯卡拉這個任務我很願意切換到。

來源

2016-04-24 22:11:21 TheJP

請勿將評論發佈爲答案。改爲編輯原始答案。或者，如果它不再相關，則將其刪除。爲了回答yoyr問題，「vanilla scala」中有很多結構，不可能告訴他們哪個比TreeSet「更好」，因爲質量取決於具體目的。無論如何，你的問題並不是TreeSet是一個「錯誤的數據結構」，而是你的實現很糟糕。不，你不需要這樣實施，你只需選擇這樣做。 – Dima

這不是一個評論，但答案：所以這個話題是爲我完成的。我不會刪除它，因爲它可以幫助別人。正如我所說：我不認爲TreeSet是一個不好的數據結構，但它不是一個完美的適合我想要完成的任務。它仍然非常適合，但更新的pqueue（其他框架中存在的）會更好。我做了很多研究，而香草Scala不包含這樣的集合。我覺得說我的實現不好，不知道代碼庫或上下文（如問題陳述）有點粗魯。 – TheJP

這不是粗魯。任何依賴於排序不穩定的有序集合的實現都是不好的，無論代碼庫（可能整個代碼庫不好，我不知道）或問題陳述。任何問題都可以用一種好的方式或以不好的方式解決，這是無關緊要的。一個好的實現不是選擇一個好的數據結構（儘管我們也很重要），因爲它是設計一個適當的，正確的和有效的算法，並以一種可靠而可靠的方式實現它。 – Dima

的問題是，你的排序並不穩定，兩個給定元素之間的關係可以在代碼運行時更改，使樹無效的內容（你沒想到每次更新散列圖時都會重新排列樹的元素，是嗎？）。

我認爲，你應該考慮拋棄你完全擁有的東西，並從一開始就重新考慮你的方法。這可能有助於嘗試以函數形式實現它，避免使用變量和可變結構，除了使代碼更清晰更清晰外，還可以幫助您避免像這樣的錯誤。

來源

2016-04-24 21:43:44 Dima

scala treeset無法刪除元素

回答

相關問題