为什么在这个排序算法的实现中向量比数组慢得多？

Question

MergeSort 的实现使用 vectors 从参数 toBeSorted 复制数据。通过更改它，分配一个常规数组并复制每个值 "by hand"，程序执行得更快（底部有详细信息）。

我预计会有一些开销，但差异之大让我感到惊讶。我认为构建向量几乎不会比使用 new.

分配数组慢

代码（我删除了实际合并以最小化示例）：

#include <iostream>
#include <vector>
#include <time.h>

using namespace std;

#define USE_VECTORS

void Merge(vector<int>& toBeSorted, int left, int middle, int right) {
  int rightPartSize = (-1) * (middle - right);
  int leftPartSize = (middle - left) + 1;

#ifdef USE_VECTORS

  vector<int> leftPart{toBeSorted.begin() + left,
                            toBeSorted.begin() + left + leftPartSize};

  vector<int> rightPart{toBeSorted.begin() + middle + 1,
                            toBeSorted.end()};
#else

  int* leftPart = new int[leftPartSize];
  for (int i = 0; i < leftPartSize; i++) {
    leftPart[i] = (toBeSorted[left + i]);
  }

  int* rightPart = new int[rightPartSize];
  for (int i = 0; i < rightPartSize; i++) {
    rightPart[i] = (toBeSorted[middle + i + 1]);
  }

  delete[] leftPart;
  delete[] rightPart;
#endif
}

void MergeSort(vector<int>& toBeSorted, int left, int right) {
  if (left < right) {
    int middle = (left + right) / 2;
    MergeSort(toBeSorted, left, middle);
    MergeSort(toBeSorted, middle + 1, right);
    Merge(toBeSorted, left, middle, right);
  }
}

int main() {

  const int SIZE = 100000;
  std::vector<int> x(SIZE, 0);

  clock_t t_start = clock();
  MergeSort(x, 0, int(x.size()) - 1);
  clock_t t_end = clock();

  double elapsedTime = (t_end - t_start) / (double)CLOCKS_PER_SEC;
  cout << "Time: " << elapsedTime << endl;

  return 0;
}

运行它在 rextester，我得到的时间大约是 1.2 秒。
取消注释 #define USE_VECTORS 以查看数组版本的时间。为此，我看到了 ~0.009 秒。

Answer 1

计算 rightPartSize 的代码与您创建 rightPart 向量的方式不一致。您可以通过添加以下语句轻松检查它：

if( static_cast<size_t>( rightPartSize ) != rightPart.size() ) 
      cout << rightPartSize << " != " << rightPart.size() << endl;

rightPart 创建后：

因此向量完成的工作量明显大于动态数组。

为什么在这个排序算法的实现中向量比数组慢得多？

Why are vectors significantly slower than arrays in this implementation of a sorting algorithm?

c++

optimization

performance

benchmarking