Java: 递归函数中出现意外的运行时错误

Question

我正在尝试编写自己的 MergeSort 版本并编写了以下内容 class:

import java.util.List;
import java.util.LinkedList;
import java.lang.Comparable;

public class Sort<E extends Comparable<E>> {
  private List<E> list;

  public void setList(List<E> inList) {list = inList;}
  public List<E> getList() {return list;}

  public List<E> mergeSortRec(List<E> inList) {
    if (inList == null) return null;
    if (inList.size() < 2) return inList;
    int mdpt = inList.size()/2;
    List<E> left = inList.subList(0,mdpt);
    List<E> right = inList.subList(mdpt,inList.size());
    left = mergeSortRec(left);
    right = mergeSortRec(right);
    List<E> out = new LinkedList<E>();
    while (left.size()>0 && right.size()>0) {
      if (left.get(0).compareTo(right.get(0)) < 0) {
        out.add(left.remove(0));
      } else {
        out.add(right.remove(0));
      }
    }
    if (left.size()==0) {
      while (right.size()>0) {
        out.add(right.remove(0));
      }
    } else {
      while (left.size()>0) {
        out.add(left.remove(0));
      }
    }
    return out;
  }
  public void mergeSort() {list = mergeSortRec(list);}
}

不过下面主要class,

import java.util.LinkedList;

public class Main {
  public static void main(String[] args) {
    System.out.println("Input list:");
    LinkedList<Integer> lst = new LinkedList<Integer>();
    lst.add(3);
    lst.add(1);
    lst.add(5);
    Sort<Integer> s = new Sort<Integer>();
    s.setList(lst);
    s.mergeSort();
  }
}

导致以下错误，

Exception in thread "main" java.util.ConcurrentModificationException
    at java.util.SubList.checkForComodification(AbstractList.java:769)
    at java.util.SubList.size(AbstractList.java:645)
    at Sort.mergeSortRec(Sort.java:69)
    at Sort.mergeSortRec(Sort.java:59)
    at Sort.mergeSort(Sort.java:79)
    at Main.main(Main.java:12)

插入打印行后，我发现问题来自 if (left.size()==0) { 中对 left.size() 的调用，我相信它发生在递归调用的 "zeroth level" 中，即也就是说，当 inList 是整个原始列表，并且 left 是 3 并且 right 是 1,5 时，它就会发生。我不明白为什么对 left 的方法调用会导致错误。我只是模模糊糊地理解了怎么会出现并发问题，但我对此几乎没有经验，我认为 left 是函数的 return 值这一事实可以避免这种情况因此不应被多个变量引用——如果这与问题有关。

Answer 1

这里的问题是由于从正在迭代的列表中删除了一个项目：

 while (left.size()>0 && right.size()>0) { // iteration on left/right lists
      if (left.get(0).compareTo(right.get(0)) < 0) {
        out.add(left.remove(0)); // modification of the left list
      } else {
        out.add(right.remove(0)); // modification of the right list
      }
 }

在 while 迭代期间删除项目违反了列表对象的约定并导致您的异常 - ConcurrentModificationException。

有多种方法可以处理这个问题 -

使用将要修改的列表的副本，同时迭代原始列表。在这种情况下，您可以使用大小计数器而不是调用列表大小方法。
使用 Iterator 和迭代器的专用 remove() 方法。
使用 Java 8 可以使用 Collection.removeIf 方法。

参考文献：

How to avoid ConcurrentModificationException / How to remove an item from an ArrayList while iterating over it
Iterating through a Collection, avoiding ConcurrentModificationException when removing in loop
Java 8 – Collection.removeIf method tutorial with examples

Java: 递归函数中出现意外的运行时错误

Java: Unexpected runtime error in a recursive function

java

recursion

concurrentmodification