我有2個完全相同的程序版本，迷宮生成器，用Python編寫，C++。在Python中優化它后，我的想法是，如果我用C++重寫它，它將更快，更有效率。然而，我發現了一件令人驚訝的事情（當你想到它時，這并不奇怪）。對于Python：我的算法從列表中選擇一個隨機項目，處理它，然后從那里刪除它。對于C++：都是一樣的，但不是列表，而是使用向量。從C++中的向量中刪除元素比在Python中對列表執行相同的操作要慢得多，因為當您刪除它們時，向量的元素會發生變化。我的問題是：C++中可以編制索引并比vector更快地執行其項目刪除的最佳數據結構是什么？現在C++的刪除時間是Python平均時間的5-6倍。
2 回答
千巷貓影
TA貢獻1829條經驗 獲得超7個贊
std::list是一個鏈接列表，與動態數組的線性復雜性相比，它具有任意元素的恒定復雜性去除。對于少量元素，由于更好地使用緩存，vector 仍然可以更快，但漸近復雜性決定了大量元素的速度。std::vector
也就是說，為了從鏈表中選擇一個隨機元素進行刪除，您需要使用輔助數據結構來實現低于線性的復雜性。
此外，python列表也具有刪除的線性復雜性，因此不清楚為什么您會認為它更快。
隨機刪除可能更有效的可能是由不同大小的段組成的繩索數據結構。但是標準庫中沒有使用此類數據結構實現的容器。
關于您的特定程序的更多信息，而不是隨機或任意刪除：似乎更好的算法可能是一種選擇：
使用矢量。將最后一個有效元素移到“已刪除”元素上，并擦除矢量末尾的已移動對象。除非有效部分的順序很重要，否則可以使用此算法。
翻閱古今
TA貢獻1780條經驗 獲得超5個贊
嘗試創建一個專用類，該類不是在要刪除項目時實際刪除項目，而是將項目交換到垃圾部分的末尾。vectorvector
下面是可用于測試性能的代碼示例：
#include <vector>
#include <iostream>
using namespace std;
template <typename T>
struct FastDelVec {
vector<T> data;
int deleteIndex;
FastDelVec(int size) {
data.resize(size);
deleteIndex = size - 1;
}
void Delete(int index) {
swap(data[index], data[deleteIndex]);
--deleteIndex;
}
size_t size() {
return deleteIndex + 1;
}
};
int main() {
FastDelVec<int> v(100);
for (int i = 0; i < 100; ++i) {
v.data[i] = i;
}
v.Delete(30);
v.Delete(5);
v.Delete(21);
cout << v.size() << endl;
system("pause");
return 0;
}
您還可以嘗試其他幾種技巧。這會將刪除推遲到以后，因為不斷釋放堆內存并可能調整大小會降低性能vector
添加回答
舉報
0/150
提交
取消