对于我的数据结构类中的一个项目,我的任务是创建一个 3 维范围树,其中每个维度都是 BST。我读过this question ,但这是一个Android问题,而且我们的问题原因似乎不同,唯一的答案是不被接受。
代码墙即将推出。抱歉。
涉及类:
-
Point3D<T>
:包含点坐标的通用类。T extends Comparable<T>
,和Point3D
也扩展了它 -
RangeTree<T>
:包含整个树的根以及构建和搜索树的方法的通用类
还有比这两个更多的类,但它们似乎与我收到 ConcurrentModificationException ( link to CME ) 的原因无关。 这是我运行驱动程序时得到的结果:
Read in 10 points //Number of points read in driver, this is okay
5//first median, 10 / 2
2//second median 5 / 2
first[0.082 0.791 0.832 , 0.366 0.136 0.009 ]//correct
second[0.138 0.968 0.391 , 0.414 0.785 0.883 , 0.546 0.044 0.133 ]//correct
merged[0.082 0.791 0.832 , 0.366 0.136 0.009 ]//not correct
first[0.082 0.791 0.832 , 0.366 0.136 0.009 ]//printed again. why?
2//secondHalf being sorted
first[0.415 0.64 0.099 , 0.513 0.612 0.466 ]//correct
second[0.091 0.719 0.772 , 0.199 0.999 0.086 , 0.896 0.835 0.86 ]//correct
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.ArrayList$SubList.checkForComodification(ArrayList.java:1231)
at java.util.ArrayList$SubList.size(ArrayList.java:1040)
at RangeTree.mergeList(RangeTree.java:189)
at RangeTree.sortAscending(RangeTree.java:175)
at RangeTree.sortAscending(RangeTree.java:173)
at RangeTree.build3DTree(RangeTree.java:126)
at RangeTree.build(RangeTree.java:11)
at Main.main(Main.java:35)
何时 RangeTree.build
被称为(Main.java:35),它需要 List<Point3D<T>>
并将其传递给 RangeTree.build3DTree
(RangeTree.java:11) 它还需要剩余 # 个维度来构建,以及一个指示是否 List
的参数。已经排序了。该方法中的 RangeTree.java:126 是我调用 sortAscending
的行在build3DTree
.
sortAscending
(它是递归的)通过比较某个维度上的点(从 x
开始)来完成听起来的样子。 (x = 0, y = 1, z = 2),如果它们相等,它会检查下一个维度等。基于上述,它显然工作得很好,除了那个奇怪的故障,其中 Line 172
以某种方式打印两次。下面是sortAscending
代码(所有打印行纯粹用于调试):
private List<Point3D<T>> sortAscending(List<Point3D<T>> pointArr){
if(pointArr.size() <= 3){//minimum sublist size is 3
int median = findMedian(pointArr);
Point3D<T> medianElement = pointArr.get(median);//retrieves coordinate to sort on
int compareLeft = medianElement.compareTo(pointArr.get(median - 1));
if(compareLeft < 0){//determine if median is less than element to its left. There will always be an element to the left
pointArr.add(0, pointArr.remove(median));
medianElement = pointArr.get(median);
}
try{//check median against element to its right. May not be valid if sublist is size 2
int compareRight = medianElement.compareTo(pointArr.get(median + 1));
if(compareRight > 0){
Point3D<T> rightEnd = pointArr.get(median + 1);
Point3D<T> leftEnd = pointArr.get(median - 1);
if(rightEnd.compareTo(leftEnd) < 0)
pointArr.add(0, pointArr.remove(median + 1));
else
pointArr.add(median, pointArr.remove(median + 1));
}
} catch (IndexOutOfBoundsException e){
}
return pointArr;
}
int median = findMedian(pointArr);//returns pointArr.size() / 2
System.out.println(median);//for debugging
List<Point3D<T>> firstHalf = sortAscending(pointArr.subList(0, median));
System.out.println("first" + firstHalf); //prints twice, once when it should, and again after Line 176 prints
List<Point3D<T>> secondHalf = sortAscending(pointArr.subList(median, pointArr.size()));//Line 173
System.out.println("second" + secondHalf);//debugging
List<Point3D<T>> merged = mergeList(firstHalf, secondHalf);//Line 175
System.out.println("merged" + merged);//debugging
return merged;//mergeList(firstHalf, secondHalf);
}
所以,CME的最终来源似乎在 mergeList
,并且直到调用后半部分数据才中断。 mergeList
(迭代)需要两个 List<Point3D<T>>
并将它们合并成一个按升序排序的列表,然后返回。也就是说,它采用第一个参数并将其修改为合并列表并返回它。代码:
private List<Point3D<T>> mergeList(List<Point3D<T>> firstList, List<Point3D<T>> secList){
int sListSize = secList.size();
int fListSize = firstList.size();//Line 188
Point3D<T> firstListElement = firstList.get(fListSize - 1);
Point3D<T> secListElement = secList.get(0);
if(secListElement.compareTo(firstListElement) >= 0){//check to see if secList can be appended to end of firstList e.g. firstList = {1, 2} secList = {3, 4, 5}
firstList.addAll(secList);
return firstList;
}
secListElement = secList.get(secList.size() - 1);
firstListElement = firstList.get(0);
if(secListElement.compareTo(firstListElement) <= 0){//check to see if firstList can be appended to the end of secList e.g. secList = {1, 2} firstList = {3,4,5}
secList.addAll(firstList);
return secList;
}
for(int a = 0; a < secList.size(); a++){//take an element from secList and insert it into firstList
secListElement = secList.get(a);
int minIdx, maxIdx, median = findMedian(firstList);
int mComp = secListElement.compareTo(firstList.get(median));//compare to the median of firstList to choose side to start from
if(mComp < 0){
minIdx = 0;
maxIdx = median;
}
else if(mComp > 0){
minIdx = median;
maxIdx = firstList.size();
}
else{//if mComp is 0, insert it at median index
firstList.add(median, secList.get(a));
continue;
}
for(; minIdx < maxIdx; minIdx++){
firstListElement = firstList.get(minIdx);
int compare = secListElement.compareTo(firstListElement);
if(compare <= 0){
firstList.add(minIdx, secList.get(a));
break;
}
}
}
return firstList;
}
由于某种原因,当我尝试访问 firstList
的大小时,CME 就会出现。 。我不知道为什么会发生这种情况。我已经使用数据集(下面发布)手动跟踪了我的代码,完成了每个步骤,但我看不到 CME 来自哪里。数据:
10
0.366 0.136 0.009
0.082 0.791 0.832//beautiful 3D points
0.138 0.968 0.391
0.414 0.785 0.883
0.546 0.044 0.133
0.513 0.612 0.466
0.415 0.640 0.099
0.199 0.999 0.086
0.896 0.835 0.860
0.091 0.719 0.772
0.25 0.75 0.25 0.75 0.25 0.75//range queries. Code fails before we get to this
0.75 0.25 0.8 0.1 0.9 0.1
0.95 1.75 0.1 0.01 0.1 0.2
exit//no more queries
最佳答案
问题在于函数 List#subList
不会返回允许您修改的列表的副本。您需要制作这些列表的可变副本。不完全确定为什么并发检查只在 size()
中进行但看看ConcurrentModificationException thrown by sublist进行讨论
编辑:检查仅发生在size()
中的可能原因:您可以进行不会扰乱子列表结构的更改,例如与 Collections.swap
进行交换操作。他们只能将支票存入 size()
允许执行这些“结构保留”操作而不会立即崩溃,因此您可以调用 add()
可能已经被单独留下了。
编辑 2:解决此问题的一种方法可能是始终按原样传递原始列表,并使用索引来定义递归的子列表范围
关于java - 检索列表大小时发生 ConcurrentModificationException,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43063346/