post_56922793_speedtest

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <chrono>
#include <utility>

class hiddenVector {
 private:
  std::vector<int> a;
 public:
  hiddenVector (int N) {
    a.resize (N);
    // make all them different, except two equal elements
    for (int i = 0; i < N; i++)
      a[i] = (i % 2 ? i : -i);
    a[1] = 0;
    // shuffle all
    auto seed = std::chrono::system_clock::now().time_since_epoch().count();
    std::shuffle (a.begin(), a.end(), std::default_random_engine(seed));
  }
  int getSize() const {
    return a.size();
  }
  bool iLessThanj(int i, int j) const {
    return a[i] < a[j];
  }
};

std::pair<int,int> squared_solution (const hiddenVector &v) {
  int n = v.getSize();
  for (int a = 0; a < n; ++a) {
    int b;
    for (b = a+1; b < n; ++b)
      if (!v.iLessThanj(a, b) && !v.iLessThanj(b, a))
        return {a, b};
    if (b < n)
      return {};
  }
  return {};
}

std::pair<int,int> sublinear_solution (const hiddenVector &v) {
  std::vector<int> a_ind (v.getSize ());
  for (int i = 0; i < v.getSize(); i++)
    a_ind[i] = i;

  std::sort(begin(a_ind), end(a_ind), [&v] (int i, int j) {
    return v.iLessThanj(i, j); });

  for (int k = 0; k < a_ind.size()-1; k++)
    if (!v.iLessThanj(a_ind[k], a_ind[k+1]))
      return {a_ind[k], a_ind[k+1]};

  return {};
}

void run_tests (int N, int test_num) {
  std::chrono::duration<double> squared_time (0);
  std::chrono::duration<double> sublinear_time (0);
  for (int i = 0 ; i < test_num; i++) {
    hiddenVector a (N);
    // squared test
    auto start = std::chrono::system_clock::now();
    auto res_1 = squared_solution (a);
    auto end = std::chrono::system_clock::now();
    squared_time += end-start;
    // sublinear test
    start = std::chrono::system_clock::now();
    auto res_2 = sublinear_solution (a);
    end = std::chrono::system_clock::now();
    sublinear_time += end-start;
    // check correctness
    if (res_1.first != res_2.first || res_1.second != res_2.second)
      if (res_1.first != res_2.second || res_1.second != res_2.first)
        throw 1;
  }
  // normalize time
  squared_time /= test_num;
  sublinear_time /= test_num;

  std::cout << squared_time.count() << " " <<
               sublinear_time.count() << std::endl;
}

int main () {
  for (int N = 10; N < 1'000'000 ; N *= 10) {
    std::cout << N << " ";
    run_tests (N, 10 /*test_num*/);
  }
  return 0;
}