java - 检索列表大小时发生 ConcurrentModificationException

标签 java list binary-search-tree concurrentmodification

对于我的数据结构类中的一个项目,我的任务是创建一个 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/

相关文章:

java - 在 Freemarker 中遍历两个序列

python - 通过切断循环来缩短元组列表?

java - 如何检查 BST 的结构是否对称

c - 无法理解二叉搜索树中插入的逻辑

algorithm - 查找构建二叉搜索树的时间复杂度

java - @拆解后, hibernate 100ms,测试全部通过

java - 504 生成 Excel 文件时网关超时

java - 如何按一定顺序打印 3 个不同字符串数组的元素?

java - 列出 codenameone 中的渲染器问题

java - Netbeans 无法在 mac 中读取 utf8 文件名