What is the fastest way access random (non-sequential) elements in an array if the access pattern is known beforehand? The access is random for different needs at every step so rearranging the elements is expensive option. The code below is represents important sample of the whole application.

```
#include <iostream>
#include "chrono"
#include <cstdlib>

#define NN 1000000

struct Astr{
    double x[3], v[3];
    int i, j, k;
    long rank, p, q, r;
};

int main ()
{
    struct Astr *key;
    key = new Astr[NN];
    int ii, *sequence;
    sequence = new int[NN]; // access pattern is stored here
    float frac ;

    // create array of structs
    // create array for random numbers between 0 to NN to access 'key'
    for(int i=0; i < NN; i++){
        key[i].x[1] = static_cast<double>(i);
        key[i].p = static_cast<long>(i);
        frac = static_cast<float>(rand()) / static_cast<float>(RAND_MAX);
        sequence[i] = static_cast<int>(frac  * static_cast<float>(NN));
    }

    // part to check and improve
    // =========================================Random=======================================================
    std::chrono::high_resolution_clock::time_point TstartMain = std::chrono::high_resolution_clock::now();
    double tmp;
    long rnk;

    for(int j=0; j < 1000; j++)
    for(int i=0; i < NN; i++){
        ii = sequence[i];
        tmp = key[ii].x[1];
        rnk = key[ii].p;
        key[ii].x[1] = tmp * 1.01;
        key[ii].p = rnk * 1.01;
    }

    std::chrono::high_resolution_clock::time_point TendMain = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::microseconds>( TendMain - TstartMain );
    double time_uni = static_cast<double>(duration.count()) / 1000000;

    std::cout << "\n Random array access " << time_uni << "s \n" ;

    // ==========================================Sequential======================================================
    TstartMain = std::chrono::high_resolution_clock::now();

    for(int j=0; j < 1000; j++)
    for(int i=0; i < NN; i++){
        tmp = key[i].x[1];
        rnk = key[i].p;
        key[i].x[1] = tmp * 1.01;
        key[i].p = rnk * 1.01;
    }

    TendMain = std::chrono::high_resolution_clock::now();
    duration = std::chrono::duration_cast<std::chrono::microseconds>( TendMain - TstartMain );
    time_uni = static_cast<double>(duration.count()) / 1000000;

    std::cout << " Sequential array access " << time_uni << "s \n" ;
    // ================================================================================================
    delete [] key;
    delete [] sequence;
}

```

As expected, sequential access is faster; the answer is following on my machine- 

```
Random array access 21.3763s 
Sequential array access 8.7755s 

```

The main question is whether random access could be made any faster.
The code improvement could be in terms of the container itself ( e.g. list/vector rather than array). Could software prefetching be implemented?