c++ - 用于快速插入和查找n维实 vector 的适当容器(提供了初始基准测试)

Question

1.问题描述

我正在尝试选择最合适的(有效)容器来存储由浮点数组成的独特的 n维 vector 。
解决整个问题，最重要的步骤(与问题有关)包括:

从外部程序获取一个新的 vector (在同一运行期间，所有 vector 都具有相同的维数)。

检查(ASAP)此容器中是否已存在新点:

如果存在-跳过很多昂贵的步骤，然后执行其他步骤；

如果不是-将插入容器(在容器中排序并不重要)，然后执行其他步骤。

预先，我不知道会有多少个 vector ，但是预先规定了最大 vector ，等于100000。此外，每次迭代我总是只得到一个新 vector 。因此，一开始，这些新 vector 中的大多数都是唯一的，并将被插入到容器中，但是以后很难预先进行预测。很大程度上取决于唯一 vector 和公差值的定义。

因此，我的目标是针对这种情况选择正确的容器。

2.选择合适的容器

我做了一些评论，并从 S. Meyers - Effective STL 中发现的内容第1项:小心选择容器

Is lookup speed a critical consideration? If so, you’ll want to look at hashed containers (see Item 25), sorted vectors (see Item 23), and the standard associative containers — probably in that order.

从惊人的David Moore流程图 Choosing a Container中可以看到，似乎S.Meyers，第1项中所有的所有三个建议选项都值得更广泛的研究。

2.1复杂度(基于 cppreference.com)

让我们从对所有三个考虑到的选项分开的查找和插入过程的理论复杂度开始进行简短的探讨:

对于 vector :

find_if()-线性O(n)

push_back()-常量，但是如果新的size()大于旧的capacity()

，则会导致重新分配

用于设置:

insert()-容器大小的对数，O(log(size()))。

对于无序集:

insert()-平均情况:O(1)，最差情况O(size())

3.对不同容器进行基准测试

在所有实验中，我都使用随机生成的3维 vector 对情况进行建模，这些 vector 填充了间隔[0,1)中的实际值。

编辑:

使用的编译器:Apple LLVM版本7.0.2(clang-700.1.81)

在 Release模式下编译，优化级别为-O3，并且没有任何优化级别。

3.1使用未排序的 vector
首先，为什么要排序 vector ？我的场景与 S. Meyers - Effective STL 项目23中描述的场景有很大不同:考虑用排序的 vector 替换关联容器。
因此，在这种情况下，使用排序 vector 不会带来任何好处。

其次，假设两个 vector x和y相等，如果 EuclideanDistance2(x,y) < tollerance^2。
考虑到这一点，我最初的(可能是牺牲品)使用vector的实现如下:

使用 vector容器实现的基准测试部分:

// create a vector of double arrays (vda)
std::vector<std::array<double, N>> vda;
const double tol = 1e-6;  // set default tolerance
// record start time
auto start = std::chrono::steady_clock::now();
// Generate and insert one hundred thousands new double arrays
for (size_t i = 0; i < 100000; ++i) {
  // Get a new random double array (da)
  std::array<double, N> da = getRandomArray();
  auto pos = std::find_if(vda.begin(), vda.end(),  // range
    [=, &da](const std::array<double, N> &darr) {  // search criterion
    return EuclideanDistance2(darr.begin(), darr.end(), da.begin()) < tol*tol;
    });

  if (pos == vda.end()) {
    vda.push_back(da);  // Insert array
  }
}
// record finish time
auto end = std::chrono::steady_clock::now();
std::chrono::duration<double> diff = end - start;
std::cout << "Time to generate and insert unique elements into vector: "
          << diff.count() << " s\n";
std::cout << "vector's size = " << vda.size() << std::endl;

这里生成随机的n维实 vector (N维数组):

// return an array of N uniformly distributed random numbers from 0 to 1
std::array<double, N> getRandomArray() {
  // Engines and distributions retain state, thus defined as static
  static std::default_random_engine e;                    // engine
  static std::uniform_real_distribution<double> d(0, 1);  // distribution
  std::array<double, N> ret;
  for (size_t i = 0; i < N; ++i) {
    ret[i] = d(e);
  }
  return ret;
}

并计算出欧几里德距离的平方:

// Return Squared Euclidean Distance
template <typename InputIt1, typename InputIt2>
double EuclideanDistance2(InputIt1 beg1, InputIt1 end1, InputIt2 beg2) {
  double val = 0.0;
  while (beg1 != end1) {
    double dist = (*beg1++) - (*beg2++);
    val += dist*dist;
  }
  return val;
}

3.1.1测试 vector 的性能

在下面的困惑表中，我总结了10次独立运行的平均执行时间以及最终容器的大小(取决于不同的公差(eps)值)。较小的公差值导致较多的唯一元素(更多的插入)，而较高的公差值导致较少的唯一 vector 但查找时间更长。

| eps |带有-O3标志/没有优化标志的时间|尺寸

| 1e-6 | 13.1496 / 111.83 | 100000 |

| 1e-3 | 14.1295 / 114.254 | 99978 |

| 1e-2 | 10.5931 / 90.674 | 82868 |

| 1e-1 | 0.0551718 / 0.462546 | 749 |

从结果看来，使用 vector 最耗时的部分是查找( find_if())。

编辑:同样，很明显，-O3优化确实在改善 vector 性能方面做得很好。

3.2使用 set
使用 set容器对实现进行基准化的部分:

// create a set of double arrays (sda) with a special sorting criterion
std::set<std::array<double, N>, compare_arrays> sda;
// create a vector of double arrays (vda)
std::vector<std::array<double, N>> vda;
// record start time
auto start = std::chrono::steady_clock::now();
// Generate and insert one hundred thousands new double arrays
for (size_t i = 0; i < 100000; ++i) {
  // Get a new random double array (da)
  std::array<double, N> da = getRandomArray();
  // Inserts into the container, if the container doesn't already contain it.
  sda.insert(da);
}
// record finish time
auto end = std::chrono::steady_clock::now();
std::chrono::duration<double> diff = end - start;
std::cout << "Time to generate and insert unique elements into SET: "
          << diff.count() << " s\n";
std::cout << "set size = " << sda.size() << std::endl;

排序标准基于有缺陷的(打破严格的弱排序) answer的地方。目前，我想(大概)看一下从不同的容器中可以得到什么，然后再决定哪个容器是最好的。

// return whether the elements in the arr1 are “lexicographically less than”
// the elements in the arr2
struct compare_arrays {
  bool operator() (const std::array<double, N>& arr1,
                   const std::array<double, N>& arr2) const {
    // Lexicographical comparison compares using element-by-element rule
    return std::lexicographical_compare(arr1.begin(), arr1.end(),  // 1st range
                                        arr2.begin(), arr2.end(),  // 2nd range
                                        compare_doubles);   // sorting criteria
   }
  // return true if x < y and not within tolerance distance
  static bool compare_doubles(double x, double y) {
    return (x < y) && !(fabs(x-y) < tolerance);
  }
 private:
  static constexpr double tolerance = 1e-6;  // Comparison tolerance
};

3.2.1测试设备的性能

在下面的表格中，我总结了执行时间和容器的大小，具体取决于不同的公差(eps)值。使用了相同的eps值，但对于集合而言，等效定义不同。

| eps |带有-O3标志/没有优化标志的时间|尺寸

| 1e-6 | 0.041414 / 1.51723 | 100000 |

| 1e-3 | 0.0457692 / 0.136944 | 99988 |

| 1e-2 | 0.0501 / 0.13808 | 90828 |

| 1e-1 | 0.0149597 / 0.0777621 | 2007 |

与 vector 方法相比，性能差异很大。现在主要关注的是排序标准存在缺陷。

编辑: -O3优化也可以很好地改善设备的性能。

3.3使用未排序集

最后，我急于尝试无序集合，因为在阅读了一些 Josuttis, The C++ Standard Library: A Tutorial and Reference之后我的期望

As long as you only insert, erase, and find elements with a specific value, unordered containers provide the best running-time behavior because all these operations have amortized constant complexity.

确实很高，但要谨慎

Providing a good hash function is trickier than it sounds.

使用 unordered_set容器对实现进行基准化的部分:

  // create a unordered set of double arrays (usda)
  std::unordered_set<std::array<double, N>, ArrayHash, ArrayEqual> usda;
  // record start time
  auto start = std::chrono::steady_clock::now();
  // Generate and insert one hundred thousands new double arrays
  for (size_t i = 0; i < 100000; ++i) {
    // Get a new random double array (da)
    std::array<double, N> da = getRandomArray();
    usda.insert(da);
  }
  // record finish time
  auto end = std::chrono::steady_clock::now();
  std::chrono::duration<double> diff = end - start;
  std::cout << "Time to generate and insert unique elements into UNORD. SET: "
            << diff.count() << " s\n";
  std::cout << "unord. set size() = " << usda.size() << std::endl;

天真的哈希函数:

// Hash Function
struct ArrayHash {
  std::size_t operator() (const std::array<double, N>& arr) const {
    std::size_t ret;
    for (const double elem : arr) {
      ret += std::hash<double>()(elem);
    }
    return ret;
  }
};

和等效标准:

// Equivalence Criterion
struct ArrayEqual {
  bool operator() (const std::array<double, N>& arr1,
                          const std::array<double, N>& arr2) const {
    return EuclideanDistance2(arr1.begin(), arr1.end(), arr2.begin()) < tol*tol;
  }
 private:
  static constexpr double tol = 1e-6;  // Comparison tolerance
};

3.3.1测试未排序集的性能

在下面的最后一个困惑表中，我再次根据不同的公差(eps)值总结执行时间和容器的大小。

| eps |带有-O3标志/没有优化标志的时间|尺寸

| 1e-6 | 57.4823 / 0.0590703 | 100000/100000 |

| 1e-3 | 57.9588 / 0.0618149 | 99978/100000 |

| 1e-2 | 43.2816 / 0.0595529 | 82873/100000 |

| 1e-1 | 0.238788 / 0.0578297 | 781/99759 |

很快，执行时间是与其他两种方法相比最好的，但是即使使用相当宽松的容差(1e-1)，几乎所有随机 vector 都被确定为唯一。因此，在我的情况下，可以节省查找时间，但在解决问题的其他昂贵步骤上浪费了更多时间。我猜这是因为我的哈希函数真的很幼稚吗？

编辑:这是最意外的行为。对无序集启用-O3优化，会严重降低性能。更令人惊讶的是，唯一元素的数量取决于优化标志，这不应该是唯一的意思，这意味着我必须提供更好的哈希函数!

4.公开问题

正如我事先所知，使用std::vector::reserve(100000)是否有意义？

根据 The C++ Programming Language by Bjarne Stroustrup， reserve对性能没有太大影响:

I used to be careful about using reserve() when I was reading into a vector. I was surprised to find that for essentially all of my uses, calling reserve() did not measurably affect performance. The default growth strategy worked just as well as my estimates, so I stopped trying to improve performance using reserve().

我使用 reserve() = 100000使用 vector 和eps = 1e-6重复了相同的实验，在这种情况下，总执行时间为111.461(s)，而没有reserve()的情况为111.83(s)。因此，差异可以忽略不计。

如何针对

中描述的情况提供更好的哈希函数

关于此比较的公平性的一般评论。我该如何改善？

任何关于如何使我的代码更好和更高效的一般评论都非常受欢迎-伙计们，我喜欢向您学习! ;)

附言最后，在StackOverflow中是否有适当的 Markdown 支持来创建表？在这个问题的最终版本(基准测试)中，我想提出最终的总结表。

P.P.S.请随时纠正我的英语不好。

Answer 1

对于哈希函数，最好使用^ =而不是+ =来使哈希更加随机。

为了进行比较，您可以将ArrayEqual与EuclideanDistance2结合使用:

struct ArrayEqual {
  bool operator() (const std::array<double, N>& arr1,
              const std::array<double, N>& arr2) const {
      auto beg1 = arr1.begin(), end1 = arr1.end(),  beg2 = arr2.begin();
      double val = 0.0;
      while (beg1 != end1) {
        double dist = (*beg1++) - (*beg2++);
        val += dist*dist;
        if (val >= tol*tol)
            return false;
      }
      return true;
  }
 private:
  static constexpr double tol = 1e-6;  // Comparison tolerance
};