C++ 从矢量效率问题中删除

Question

我有2个完全相同的程序版本，迷宫生成器，用Python编写，C++。在Python中优化它后，我的想法是，如果我用C++重写它，它将更快，更有效率。然而，我发现了一件令人惊讶的事情（当你想到它时，这并不奇怪）。对于Python：我的算法从列表中选择一个随机项目，处理它，然后从那里删除它。对于C++：都是一样的，但不是列表，而是使用向量。从C++中的向量中删除元素比在Python中对列表执行相同的操作要慢得多，因为当您删除它们时，向量的元素会发生变化。我的问题是：C++中可以编制索引并比vector更快地执行其项目删除的最佳数据结构是什么？

现在C++的删除时间是Python平均时间的5-6倍。

Answer 1

std::list是一个链接列表，与动态数组的线性复杂性相比，它具有任意元素的恒定复杂性去除。对于少量元素，由于更好地使用缓存，vector 仍然可以更快，但渐近复杂性决定了大量元素的速度。std::vector也就是说，为了从链表中选择一个随机元素进行删除，您需要使用辅助数据结构来实现低于线性的复杂性。此外，python列表也具有删除的线性复杂性，因此不清楚为什么您会认为它更快。随机删除可能更有效的可能是由不同大小的段组成的绳索数据结构。但是标准库中没有使用此类数据结构实现的容器。关于您的特定程序的更多信息，而不是随机或任意删除：似乎更好的算法可能是一种选择：使用矢量。将最后一个有效元素移到“已删除”元素上，并擦除矢量末尾的已移动对象。除非有效部分的顺序很重要，否则可以使用此算法。

Answer 2

尝试创建一个专用类，该类不是在要删除项目时实际删除项目，而是将项目交换到垃圾部分的末尾。vectorvector下面是可用于测试性能的代码示例：#include <vector>#include <iostream>using namespace std;template <typename T>struct FastDelVec {&nbsp; &nbsp; vector<T> data;&nbsp; &nbsp; int deleteIndex;&nbsp; &nbsp; FastDelVec(int size) {&nbsp; &nbsp; &nbsp; &nbsp; data.resize(size);&nbsp; &nbsp; &nbsp; &nbsp; deleteIndex = size - 1;&nbsp; &nbsp; }&nbsp; &nbsp; void Delete(int index) {&nbsp; &nbsp; &nbsp; &nbsp; swap(data[index], data[deleteIndex]);&nbsp; &nbsp; &nbsp; &nbsp; --deleteIndex;&nbsp; &nbsp; }&nbsp; &nbsp; size_t size() {&nbsp; &nbsp; &nbsp; &nbsp; return deleteIndex + 1;&nbsp; &nbsp; }};int main() {&nbsp; &nbsp; FastDelVec<int> v(100);&nbsp; &nbsp; for (int i = 0; i < 100; ++i) {&nbsp; &nbsp; &nbsp; &nbsp; v.data[i] = i;&nbsp; &nbsp; }&nbsp; &nbsp; v.Delete(30);&nbsp; &nbsp; v.Delete(5);&nbsp; &nbsp; v.Delete(21);&nbsp; &nbsp; cout << v.size() << endl;&nbsp; &nbsp; system("pause");&nbsp; &nbsp; return 0;}您还可以尝试其他几种技巧。这会将删除推迟到以后，因为不断释放堆内存并可能调整大小会降低性能vector