有没有比矢量更快的东西？

Question

我正在尝试向在线评委(不是现场比赛)提交挑战,而我的代码几乎没有时间.由于所涉及的限制很大,每一个小优化都很重要 - 所以我正在寻找加快速度的地方.

我已经使用了printf/scanf,unordered_map等.

但我也使用矢量,如下:

vector<int> myVec;
unordered_map<int, vector<int> > mapToSomeVec;
vector< vector<int> > vecOfVecs;
anotherVecofVecs = vector< vector<int> >(N+1, vector<int>(1));
regularVec[index].push_back(element);

(这些只是为了显示我正在使用的声明类型以及我如何使用它们).

根据我在这里发布的内容,在最小化整体运行时方面是否存在"更快"的等价物？

Answer 1

(你必须做一些类似于这个人的事情如何在不到1秒的时间内运行这个代码？)

我认为在那篇文章中给出的答案对你有帮助.矢量并不慢,但根据您的任务,矢量矢量可能会有所改善.

最明显的优化机会是,而不是vector<vector<int>>使用a vector<int>并手动将2D指数调整为1D.您可以编写一个简单的包装类来为您执行此操作.

这将更快的原因是所有内存将被分配为单个连续单元.如果你有一个向量向量,那么每一行都会在其他地方,你会有很多缓存未命中.

这是一个代码示例:

struct 2D_Vector {
  std::vector<int> me_;
  int ncols_;
  2D_Vector(int nrows, int ncols) : me_(nrows * ncols), ncols_(ncols) {}

  int & get(int y, int x) { return me_[y * ncols_ + x]; }
  const int & get(int y, int x) const { return me_[y * ncols_ + x]; }

  ...
};