为什么我的 Java 合并排序比我的 C++ 实现更快？

Question

我在 Java 和 C++ 中实现了合并排序，并尝试尽可能相似地实现它们。两种算法都有效，我对它们进行了多次测试。问题是我的 Java-实现比我的 C++-实现快很多，我想知道为什么。我不敢相信 Java 会更快，所以我想我在其中一个实现中犯了一个错误。为了测量运行时间，我创建了一个 class "Person"，它有两个字符串属性（名字、姓氏）。在 C++ 中，我使用了 std::vector<Person*>，在 Java 中，我使用了 ArrayList<Person>。此外，我在 C++ 中重载了 operator< 来比较两个人（比较姓氏，如果相等则比较名字）。在 Java 中，我实现了接口 Comparable<Person> 来比较两个人。

你能在我的代码中找到一个错误或者 Java 会更快或者 C++ 会更慢的原因吗？如有任何帮助，我们将不胜感激。

我的Java代码：

public void mergeSort(List<T> list) {
    if (list.size() <= 1) {
        return;
    }

    int subLength = (int) (list.size() / 2);
    List<T> first = new ArrayList<T>(list.subList(0, subLength));
    List<T> second = new ArrayList<T>(list.subList(subLength, list.size()));


    mergeSort(first);
    mergeSort(second);

    merge(first, second, list);
    return;
}

private void merge(List<T> first, List<T> second, List<T> result) {
    int firstPos = 0, secondPos = 0, resultPos = 0;

    while (firstPos < first.size() && secondPos < second.size()) {
        if (first.get(firstPos).compareTo(second.get(secondPos)) < 0) {
            result.set(resultPos, first.get(firstPos));
            firstPos++;
        } else {
            result.set(resultPos, second.get(secondPos));
            secondPos++;
        }
        resultPos++;
    }

    for (int i = firstPos; i < first.size(); i++) {
        result.set(resultPos, first.get(i));
        resultPos++;
    }
    for (int i = secondPos; i < second.size(); i++) {
        result.set(resultPos, second.get(i));
        resultPos++; 
    }
}

我的 C++ 代码：

注意：我使用了两个模板方法来使合并排序可用于 Person 和 Person*。

template<typename T>
    T * ptr(T & obj) { return &obj; } 

    template<typename T>
    T * ptr(T * obj) { return obj; }


void mergeSort(std::vector<T> &list) {
        if (list.size() <= 1) {
            return;
        }

        int subLength = (int)(list.size() / 2);
        std::vector<T> first(list.begin(), list.begin() + subLength);
        std::vector<T> second(list.begin() + subLength, list.end());

        mergeSort(first);
        mergeSort(second);

        merge(first, second, list);

    }
void merge(const std::vector<T> &first, const std::vector<T> &second, std::vector<T> &result) {
        int firstPos = 0, secondPos = 0, resultPos = 0;
        while (firstPos < first.size() && secondPos < second.size()) {
            if (*ptr(first[firstPos]) < *ptr(second[secondPos])) {
                result[resultPos] = first[firstPos];
                firstPos++;
            }
            else {
                result[resultPos] = second[secondPos];
                secondPos++;
            }
            resultPos++;
        }

        for (int i = firstPos; i < first.size(); i++) {
            result[resultPos] = first[i];
            resultPos++;
        }
        for (int i = secondPos; i < second.size(); i++) {
            result[resultPos] = second[i];
            resultPos++;
        }
    }

编辑 1 和 2：

我的安装配置：

我用了一百万、一千万和两千万人来测试这些实现。我与多少人一起测试并不重要，Java 总是更快。

然后我通过以下方式对其进行测试：我创建人员并初始化我的 MergeSort-class。然后我开始测量并调用我的 mergeSort 方法。分类完成后，我停止测量。（删除发生在时间测量之后）。对于 Java 中的时间测量，我使用 System.nanoTime()，在 C++ 中我使用 chrono::high_resolution_clock::time_point

当然，我在 "Release"-模式下编译了 C++（优化：O2，首选更快的代码）。

我的测试电脑：

英特尔 i5 2500
8GB DDR3 内存
Windows 10 学历

编辑3：

有一件事我忘了说。我以通用方式实现了该算法，以便使用简单的数据类型和对象。当我在 Java 中使用 std::vector<int> 和 ArrayList<Integer> 时，我的 C++ 实现要快得多。我的第一次尝试是使用 std::vector<Person> 但它更慢。所以我的猜测是它制作了深拷贝而不是浅拷贝，这就是我切换到 Person* 的原因，因为我认为当复制发生时，只会复制指针。

Answer 1

TL;DR - Java 版本减少了数组复制。

ArrayList 的 ArrayList constructor (see line 167) 在传递 Collection 时使用 Collection.toArray() 并根据需要选择 Arrays.copyOf。 ~~在 ArrayList 的情况下，无需复制 - toArray() return 对底层数组的引用~~.

另请注意，if (elementData.getClass() != Object[].class) 将导致数组不再被复制。

ArrayList 对象上的 Java List.subList 不复制任何底层数组，它只是 return 一个 ArrayList 支持的原始数组但仅限于所需的元素。

因此 - 在许多情况下，整个机制使用实际上仅引用原始数组的子列表 - 不需要复制。

对 C++ 不太熟悉，但我怀疑有很多数组复制和分配正在进行，而 Java 不需要这样做。

已添加 - 正如@ThomasKläger 正确指出的那样，ArrayList.toArray 实际上是 return 数组的防御性副本 - 所以我在上面错了。

Answer 2

我看到的第 1^st 件事之一是在你的陈述中：

Deleting is happening after the time measurement

你说的是删除 Person 对象，你显然不是在说容器，例如 C++ 正在创建和清理的 first 和 second堆栈：

std::vector<T> first(list.begin(), list.begin() + subLength);
std::vector<T> second(list.begin() + subLength, list.end());

而 Java 正在堆上创建它们并且直到它到达它才清理它们（所以在你停止计时之后）：

List<T> first = new ArrayList<T>(list.subList(0, subLength));
List<T> second = new ArrayList<T>(list.subList(subLength, list.size()));

因此，您将 C++ 与容器清理一起计时，而 Java 没有。

在这里我不得不问，自己写归并排序有什么意义？最好的 Java 和 C++ 代码会使用该语言已经提供的排序算法。如果您正在寻找时间，至少要对优化算法进行计时。

此外，我不会在时间比较上投入大量精力。 C++ 会更快，通常也需要更多的编写工作。如果速度对您来说足够重要，以至于您可能需要使用 C++ 来解决时间问题。如果开发时间为王，那么您将希望使用 Java.

为什么我的 Java 合并排序比我的 C++ 实现更快？

Why is my Java Merge-Sort faster than my C++ implementation?

c++

java

mergesort

runtime