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无法删除元素

回答

相关问题