Есть ли подход к обходу массива случайным образом?

Question

Я пытаюсь сравнить линейный доступ к памяти со случайным доступом к памяти. Я просматриваю массив в порядке его индексов, чтобы регистрировать производительность линейного доступа к памяти. Однако, чтобы регистрировать производительность памяти при произвольном доступе к памяти, я хочу случайно просмотреть мой массив, т.е. arr[8], arr[17], arr[34], arr[2] ...

Могу ли я использовать погоню указателя для достижения этой цели, при этом гарантируя, что к индексу не обращаются дважды? Является ли погоня за указателем наиболее оптимальным подходом в этом случае?

Answer 1

Я могу вам сказать, что для массивов в C время доступа является постоянным независимо от того, к какому индексу обращаются. Между случайным или последовательным доступом к ним не будет никакой разницы, кроме того факта, что рандомизация сама по себе приведет к дополнительным вычислениям.

Но, чтобы действительно ответить на ваш вопрос, вам, вероятно, лучше было бы создать какой-нибудь массив подстановки и несколько раз перемешать его и использовать этот массив для получения следующего индекса. Очевидно, что при этом вы будете получать доступ к двум массивам, один последовательно, а другой случайным образом, делая это упражнение практически бесполезным.

Answer 2

Если ваша цель - показать, что последовательный доступ быстрее, чем непоследовательный доступ, просто указатель, преследующий последний, не является хорошим способом продемонстрировать это. Вы бы сравнивали доступ через один указатель плюс простое смещение против сдерживания одного или нескольких указателей перед смещением.

Чтобы использовать отслеживание указателя, вы должны применить его к обоим случаям. Вот пример:

int arr[n], i;
int *unshuffled[n];
int *shuffled[n];

for(i = 0; i < n; i++) {
    unshuffled[i] = arr + i;
}
/* I'll let you figure out how to randomize your indices */
shuffle(unshuffled, shuffled)

/* Do toning on these two loops */
for(i = 0; i < n; i++) {
    do_stuff(*unshuffled[i]);
}
for(i = 0; i < n; i++) {
    do_stuff(*shuffled[i]);
}

Если вы хотите лучше рассчитать время прямого доступа, вы можете создать простую формулу для продвижения индекса вместо полной рандомизации доступа:

for(i = 0; i < n; i++) {
    do_stuff(arr[i]);
}
for(i = 0; i < n; i++) {
    do_stuff(arr[i / 2 + (i % 2) * (n / 2)]);
}

Это будет работать правильно даже для n, как показано, но это иллюстрирует идею. Вы можете пойти так далеко, чтобы компенсировать дополнительные провалы в вычислении индекса в пределах do_stuff.

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

do_stuff(arr[0]);
do_stuff(arr[1]);
do_stuff(arr[2]);
...

do_stuff(arr[123]);
do_stuff(arr[17]);
do_stuff(arr[566]);
...

Поскольку я предполагаю, что вы захотите тестировать с большими массивами, вы можете написать программу, которая сгенерирует для вас реальный тестовый код и, возможно, скомпилирует и запустит результат.