Блог

В попытке понять, как ведут себя векторы, я закодировал следующие три игрушечных примера:

1. vector_using_assignment.cc : Инициализируйте вектор до 1 000 000 и назначьте его элементы в цикле for

 // 1. vector_using_assignment
#include <iostream>
#include <vector>

int main(int argc, char *argv[]) {
  int N = *argv[1];
  std::vector<int> V(N);
  for (int i =0; i < N; i  ) {
      V[i] = i;
  }  
}
$ g   -O0 -std=c  17 vector_using_assignment.cc -o vector_using_assignment
$ time ./vector_using_assignment 1000000
real    0m0.004s
user    0m0.003s
sys     0m0.001s

 

2. vector_using_push_back.cc : Создайте пустой вектор, а затем назначьте его элементы в цикле for, используя метод push_back

 // 2. vector_using_push_back.cc
#include <iostream>
#include <vector>
int main(int argc, char *argv[]) {
  int N = *argv[1];
  std::vector<int> V;
  for (int i =0; i < N; i  ) {
      V.push_back(i);
  }    
}
$ g   -O0 -std=c  17 vector_using_push_back.cc -o vector_using_push_back
$ time ./vector_using_push_back 1000000
real    0m0.004s
user    0m0.004s
sys     0m0.000s

 

3. vector_using_insert.cc Создайте пустой вектор, а затем назначьте его элементы в цикле for, используя метод insert

 // 3. vector_using_insert.cc
#include <iostream>
#include <vector>
int main(int argc, char *argv[]) {
  int N = *argv[1];
  std::vector<int> V;
  for (int i =0; i < N; i  ) {
  V.insert(V.begin(), N - i - 1);
  }
}
$ g   -O0 -std=c  17 vector_using_insert.cc -o vector_using_insert
$ time ./vector_using_insert 1000000
  real  0m0.004s
  user  0m0.003s
  sys   0m0.001s
 

Как вы можете видеть, все методы в точности равны. Я понимаю, что push_back это линейно по сложности (когда размер <емкость). В этом примере это явно не так. Разве insert метод не должен быть линейным?

Я предполагаю, что:

1. c 17 выполняется ли некоторая оптимизация, хотя я отключил оптимизацию?
2. На моей машине 2 процессора, я думаю, по 20 ядер каждый, и 32 ГБ оперативной памяти, так что это заставляет вести себя иначе, чем я думаю? Я попробовал 100 000 000, но по-прежнему не видел никаких изменений

Что я здесь делаю не так?

Как и ожидалось, была ошибка в том, как я преобразовал аргумент stdin в int. Правильный способ:

 int N = atoi(argv[1]);
std::cout << "N = " << N << std::endl;
 

Теперь я вижу некоторые реальные различия:

 $ time ./vector_using_push_back 1000000000
N = 1000000000

real    0m20.139s
user    0m16.437s
sys 0m3.701s

$ time ./vector_using_assignment 1000000000
N = 1000000000

real    0m7.530s
user    0m6.005s
sys 0m1.525s

$ time ./vector_using_insert 1000000000
N = 1000000000
# I gave up after a couple of min