cache.cpp

// forward
const int N = 1000;
int* array = new int[N];
for (int i = 0; i < N; ++i) {
  array[i] = i + 1;
}

// время замеряем отсюда
int count = 0;
int next_index = 0;
while (count < N) {
  ++count;
  next_index = array[next_index];
}
// до сюда

std::cout << next_index << std::endl;


// backward
const int N = 1000;
int* array = new int[N];
for (int i = 0; i < N; ++i) {
  array[i] = i - 1;
}

// время замеряем отсюда
int count = 0;
int next_index = N - 1;
while (count < N) {
  ++count;
  next_index = array[next_index];
}
// до сюда

std::cout << next_index << std::endl;


// random
const int N = 1000;
int* array = new int[N];
for (int i = 0; i < N; ++i) {
  array[i] = // тут погеморней, но можно применить std::shuffle
}

// время замеряем отсюда
int count = 0;
int next_index = 0;
while (count < N) {
  ++count;
  next_index = array[next_index];
}
// до сюда

std::cout << next_index << std::endl;