6

我正在制作一个解决此问题的程序：http: //opc.iarcs.org.in/index.php/problems/BOOKLIST

我使用向量的唯一地方是：

for(int i =0;i < total_books; i++){
    int temp;
    cin >> temp;
    books_order.push_back(temp);
}

和

for(int i = 0;i < total_entries; i++){
    int index;
    cin >> index;
    index--;
    cout << books_order[index] << endl;
    books_order.erase(books_order.begin()+index);
}

（这是我的完整代码：http ://cpaste.org/1377/ ）

我从向量中使用的唯一函数是vector::erase、vector::push_back 和vector::begin。对于大型输入，我的代码花费的时间超过 3 秒（这是该问题的时间限制），但是当我删除向量函数时，它运行得更快（但当然给出了错误的答案）

我知道在这个问题中使用向量是错误的，而且我的算法很慢，但我不明白为什么它很慢。

如果您知道为什么我使用的功能很慢，请向我解释。谢谢你。

4

7 回答 7

10

我从向量中使用的唯一函数是vector::erase、vector::push_back 和vector::begin

我会说这是你的问题。vector::erase就是O(n)，其他都是常数时间，应该不会导致在线判断问题的效率问题。避免擦除方法。

但是，一般来说，如果您事先知道数组的大小，我只会使用一个简单的数组。如果您能提供帮助，请不要增加任何不必要的开销。

要解决您链接到的问题，请考虑使用set：它的擦除方法是O(log n)，它的插入方法也是。如果您需要随机删除，那通常是您应该使用的。

编辑：我忘记了 C++ 也有优先级队列，所以也要研究一下。由于您只关心这里的最大值，因此它可能比集合更快，尽管它们都具有相同的理论复杂性（堆可以检索中的最小值/最大值O(1)，但删除它，您必须为这个问题做的是O(log n)）在这种情况下，任何一个都应该可以正常工作。

于 2012-10-19T12:36:46.563 回答
7

IMO 罪魁祸首是vector::erase因为它会在移除一个元素后移动所有元素。所以除非你总是删除最后一个元素，否则它可能会很慢。

于 2012-10-19T12:36:32.867 回答
3

除非您已调用将向量的大小调整为您拥有的元素数量，否则每次新大小超过向量容量时reserve，调用都会重新分配内存。push_back考虑使用reserve为您的元素分配足够的内存，您应该会看到性能加速，特别是在向量很大的情况下。还要注意有关使用的其他答案erase。

于 2012-10-19T12:35:37.747 回答
2

您的问题是“擦除”的调用。如果您在此处查看文档，您会注意到：

因为向量保持数组格式，擦除向量末端以外的位置也会将擦除段之后的所有元素移动到它们的新位置，这可能不像在其他类型的序列容器（deque，list）中擦除那样有效.

从末尾运行循环或在循环后擦除。

于 2012-10-19T12:38:48.077 回答
2

从向量中间移除元素（带有vector::erase）很慢。这是因为必须向下移动向量的所有较高元素以填充您已删除的元素留下的空白。

所以这不是向量很慢的情况，而是你的算法很慢，因为你选择了不合适的数据结构。

于 2012-10-19T12:36:13.550 回答
1

如果您事先知道向量中有一定数量的元素，则可以保留足够的空间来包含所有内容，以节省向量内空间的重新分配：

books_order.reserve(total_books)
for(int i=0 ;i < total_books; ++i){
    int temp;
    cin >> temp;
    books_order.push_back(temp);
}

然而，这不是这里的问题，我敢肯定，如果你分析你的代码，你会看到使用带来的巨大开销.erase()。从向量中间移除元素很慢，因为向量是如何实现的，它需要移动所有元素的一部分，即被移除的元素。考虑使用不同的数据结构，例如std::array代替。

于 2012-10-19T12:36:14.033 回答
0

你真的需要一个向量来实现你正在做的事情吗？

您必须牢记向量是如何工作的：它们本质上是动态数组，当您在其中添加更多项目时，它们会调整大小。调整向量的大小是一个 O(n) 操作（其中 n 是向量中的项目数），因为它分配新内存并将项目复制到新向量。

您可以在此处阅读有关向量擅长的内容。

我建议改用标准数组——这似乎完全合理，因为您已经知道总共有多少元素（即total_books）

于 2012-10-19T12:38:08.733 回答