合并排序 java.lang.StackOverflowError

Question

我正在为学校做一个项目，在我尝试对我的 ArrayList.
执行合并排序之前，一切进展顺利它会运行但随后会出错。许多错误中的第一个错误是 Exception in thread "main" java.lang.WhosebugError。我查看了代码，但无法找出错误发生的原因。它确实给了我一个位置（line 74:first_half = mergeSort(first_half);），但我没有看到问题。

public static void main(String[] args) throws IOException {

    // URL url = new
    // URL("https://www.cs.uoregon.edu/Classes/15F/cis212/assignments/phonebook.txt");
    FileReader fileReader = new FileReader("TestSort.txt");
    BufferedReader bufferReader = new BufferedReader(fileReader);
    String entry = bufferReader.readLine();

    // Scanner s = new Scanner(url.openStream());

//      int count = 0;

    while (entry != null) {

        // String person = s.nextLine();
        String phoneNum = entry.substring(0, 7);
        String name = entry.substring(9);
        PhonebookEntry newentry = new PhonebookEntry(name, phoneNum);
        phoneBook.add(newentry);
        entry = bufferReader.readLine();
    }
    // ********************Selection
    // Sort*************************************
    ArrayList<PhonebookEntry> sortList = new ArrayList<PhonebookEntry>(phoneBook);

    for (int min = 0; min < sortList.size(); min++) {

        for (int i = min; i < sortList.size(); i++) {
            int res = sortList.get(min).getName().compareTo(sortList.get(i).getName());

            if (res > 0) {
                PhonebookEntry temp = sortList.get(i);
                sortList.set(i, sortList.get(min));
                sortList.set(min, temp);

            }

        }

    }
    for (PhonebookEntry sortentry : sortList) {
        System.out.println(sortentry);
    }


    System.out.println(mergeSort(mergeSortList));

}


// *****************************merge sort******************************************
static int mergecounter = 0;
static ArrayList<PhonebookEntry> mergeSortList = new ArrayList<PhonebookEntry>(appMain.phoneBook);

public static ArrayList<PhonebookEntry> mergeSort(ArrayList<PhonebookEntry> mergeSortLists) {
    if (mergeSortLists.size() == 1) {
        return mergeSortLists;
    }
    int firstHalf = mergeSortLists.size() % 2 == 0 ? mergeSortLists.size() / 2 : mergeSortLists.size() / 2 + 1;

    ArrayList<PhonebookEntry> first_half = new ArrayList<PhonebookEntry>(mergeSortLists.subList(0, firstHalf));
    ArrayList<PhonebookEntry> mergeSortHalf2 = new ArrayList<PhonebookEntry>(
    mergeSortLists.subList(first_half.size(), mergeSortLists.size()));

    System.out.println(++mergecounter);

    first_half = mergeSort(first_half);
    mergeSortHalf2 = mergeSort(mergeSortHalf2);
    return merge(first_half, mergeSortHalf2);
}

public static ArrayList<PhonebookEntry> merge(ArrayList<PhonebookEntry> first_half,
        ArrayList<PhonebookEntry> mergeSortHalf2) {
    ArrayList<PhonebookEntry> returnMerge = new ArrayList<PhonebookEntry>();

    while (first_half.size() > 0 && mergeSortHalf2.size() > 0) {
        if (first_half.get(0).getName().compareTo(mergeSortHalf2.get(0).getName()) > 0) {
            returnMerge.add(mergeSortHalf2.get(0));
            mergeSortHalf2.remove(0);
        }

        else {
            returnMerge.add(first_half.get(0));
            first_half.remove(first_half.get(0));
        }
    }

    while (first_half.size() > 0) {
        returnMerge.add(first_half.get(0));
        first_half.remove(first_half.get(0));

    }
    while (mergeSortHalf2.size() > 0) {
        returnMerge.add(mergeSortHalf2.get(0));
        mergeSortHalf2.remove(mergeSortHalf2.get(0));
    }
    return returnMerge;
}

}

Answer 1

我认为代码没有错误。
怎么这么确定？

我运行你在我的环境中编写代码并且执行时没有任何错误。

使用我在 https://www.cs.uoregon.edu/Classes/15F/cis212/assignments/phonebook.txt 找到的文本文件作为输入并为 PhonebookEntry

做了一个简单的实现

那为什么会出现这个错误呢？

首先尝试理解错误，我的意思是为什么 WhosebugError 会发生。因为有很多我不打算解释这个但是请阅读这两个线程的最佳答案，我相信您会知道为什么会这样。

Thread 1: What is a WhosebugError?
Thread 2: What actually causes a Stack Overflow error?

如果您阅读了这些内容，我希望您能理解摘要是 You Ran Out Of Memory。

那么为什么我没有得到那个错误：可能的原因是

在我的环境中，我将 jvm 配置为运行，具有更高的内存 1024m 到 1556m（作为 eclipse 参数）

现在让我们用解决方案分析你的案例：

输入：您的输入量很大 ( 50,000 )

要检查您的代码，请尝试缩短输入并进行测试。
你已经在一个单一的方法中对这个大输入执行了两个算法：当一个方法执行时，它的所有变量都保留在内存中，直到它完成执行。因此，当您调用合并排序时，所有以前的用户变量和其他变量都保留在内存中，这可能会导致这种情况

现在如果你使用分离的方法并从主方法调用它们，比如写一个选择排序的方法，它使用的所有变量都会超出范围在选择排序结束后可能是免费的（如果 GC 收集它们）。

所以写了两个独立的读取输入文件和选择排序的方法。还有 Please Please close() 那些 FileReader 和 BufferedReader.
摆脱那些静态方法。使它们成为 class 的非静态创建和对象，并从主方法

所以一切都是为了代码优化

而且你也可以增加 jvm 的内存并通过这样做 java -Xmx1556m -Xms1024m 在命令行中破坏应用程序时进行测试

顺便说一句，谢谢你提出这个问题，它让我思考了一些问题

合并排序 java.lang.StackOverflowError

Merge sort java.lang.StackOverflowError

java

stack-overflow

sorting

merge

arraylist