检索列表大小时发生 ConcurrentModificationException
ConcurrentModificationException Occuring When Retrieving List Size
对于我的数据结构中的一个项目class，我的任务是创建一个 3 维范围树，其中每个维度都是一个 BST。我看了this question，但这是一个Android问题，我们的问题原因似乎不同，唯一的答案没有被接受。
代码墙即将推出。对不起。
类 参与人数：
Point3D<T>：包含点坐标的通用 class。 T extends Comparable<T>，Point3D 也对其进行扩展RangeTree<T>：通用 class 包含整个树的根以及构建和搜索树的方法
比这 2 个多 class，但它们似乎与我收到 ConcurrentModificationException (link to CME) 的原因无关。
这是我 运行 我的 driver:
时得到的
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 是我在 build3DTree.
中调用 sortAscending 的行
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>> 并将它们合并到一个按升序排序的列表中，然后 returns 它。即，它采用第一个参数并将其修改为合并列表和 returns 它。代码：
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 出现了。我不知道为什么会这样。我已经 hand-traced 我的代码通过数据集（在下面发布）完成了每个步骤，但我看不到 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 没有 return 您可以修改的列表副本。您需要制作这些列表的可变副本。不完全确定为什么只在 size() 中进行并发检查，但可以查看 ConcurrentModificationException thrown by sublist 进行讨论
编辑：检查仅发生在 size() 中的可能原因：您可以进行不扰乱子列表结构的更改，例如与 Collections.swap 的交换操作。他们必须只检查 size() 以允许执行这些 "structure-preserving" 操作而不会立即崩溃，因此您对 add() 的调用可能被单独留下。
编辑 2：解决此问题的一种方法可能是始终按原样传递原始列表，并使用索引为递归定义子列表范围
我会将这个问题归类为过度可变性，您开始处理一个列表，然后创建该列表的视图，将元素添加到其中一个视图，然后合并，所有这些都在递归中进行。这是错误的秘诀。
我认为可以调试并解决您的问题，但无法解决主要问题，即具有副作用的递归函数。
我会更改排序和合并以使用不可变参数，不要更改输入列表，创建新列表。
对于我的数据结构中的一个项目class，我的任务是创建一个 3 维范围树，其中每个维度都是一个 BST。我看了this question，但这是一个Android问题，我们的问题原因似乎不同，唯一的答案没有被接受。
代码墙即将推出。对不起。
类 参与人数：
Point3D<T>：包含点坐标的通用 class。T extends Comparable<T>，Point3D也对其进行扩展RangeTree<T>：通用 class 包含整个树的根以及构建和搜索树的方法
比这 2 个多 class，但它们似乎与我收到 ConcurrentModificationException (link to CME) 的原因无关。 这是我 运行 我的 driver:
时得到的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 是我在 build3DTree.
sortAscending 的行
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>> 并将它们合并到一个按升序排序的列表中，然后 returns 它。即，它采用第一个参数并将其修改为合并列表和 returns 它。代码：
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 出现了。我不知道为什么会这样。我已经 hand-traced 我的代码通过数据集（在下面发布）完成了每个步骤，但我看不到 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 没有 return 您可以修改的列表副本。您需要制作这些列表的可变副本。不完全确定为什么只在 size() 中进行并发检查，但可以查看 ConcurrentModificationException thrown by sublist 进行讨论
编辑：检查仅发生在 size() 中的可能原因：您可以进行不扰乱子列表结构的更改，例如与 Collections.swap 的交换操作。他们必须只检查 size() 以允许执行这些 "structure-preserving" 操作而不会立即崩溃，因此您对 add() 的调用可能被单独留下。
编辑 2：解决此问题的一种方法可能是始终按原样传递原始列表，并使用索引为递归定义子列表范围
我会将这个问题归类为过度可变性，您开始处理一个列表，然后创建该列表的视图，将元素添加到其中一个视图，然后合并，所有这些都在递归中进行。这是错误的秘诀。
我认为可以调试并解决您的问题，但无法解决主要问题，即具有副作用的递归函数。
我会更改排序和合并以使用不可变参数，不要更改输入列表，创建新列表。