Обработка каждого числа из диапазона в случайном порядке
1,00
р.
Имеется два числа задающих диапазон, нужно в цикле что-то сделать с каждым числом но не по порядку циклом, а в случайном порядке. Диапазоны заведомо не известны и являются большими поэтому сложность и потребление памяти нужны O(1). Какие алгоритмы/паттерны для этого можно использовать?
Ответ
Набросал код, беглые тесты показывают, что он вроде решает Вашу задачу. код написан на с99 (то есть, используется объявление переменных не в начале блока), поэтому в gcc нужно компилировать с -std=c99, студия 2013 может не скомпилировать, а 2015 скорее всего справиться. Но переписать код не проблема, что бы он работал даже с древними компиляторами.
Потребление памяти тут точно O(1), так как память выделяется только под всякие локальные переменные, никаких массивов и скрытых рекурсий.
Самая сложная часть - это поиск шага. Данный алгоритм пытается найти минимальный шаг. Но в теории там сложность O(n). Данный алгоритм в лоб ищет первое нечетное взаимопростое с длинной число. Данную часть можно дорабатывать до получения нужных значений.
Если посмотреть визуализацию заполнения, то это будет выглядеть так. Весь диапазон будет поделен на группы по step и step-1 элементов и вначале будет заполнен каждый первый элемент в группах, потом каждый второй и так далее. То есть, порядок не случайный, но достаточно размазаный. Если же хочется немного большей случайности, то следует посмотреть на Линейный конгруэнтный метод глубже и научиться генерировать для него коэффициенты.
#include
/* нод, взято с википедии */
int gcd(int a, int b) { while (b != 0) { int r = a % b a = b b = r } return a }
/* что то сделать с i */ void doit(int i) { printf("do with %i
", i) }
/* включая a и не включая b, то есть [a,b) */ void processrange(int a, int b) { int len = b - a if (len <= 0) { return /* диапазон вырожден*/ } /* поищем хороший шаг */ /* если такое случиться, что шаг не будет найден, то будет 1 */ int step = 1 for (int i = 3 i < len/2 i+=2) { if (gcd(i, len) == 1) { step = i break } } /* собственно цикл */ int ind = 0 for (int i = 0 i < len i++) { doit(a + ind) ind = (ind + step) % len } }<br>int main(void) { processrange(100,200) return 0 }
Ответ
Набросал код, беглые тесты показывают, что он вроде решает Вашу задачу. код написан на с99 (то есть, используется объявление переменных не в начале блока), поэтому в gcc нужно компилировать с -std=c99, студия 2013 может не скомпилировать, а 2015 скорее всего справиться. Но переписать код не проблема, что бы он работал даже с древними компиляторами.
Потребление памяти тут точно O(1), так как память выделяется только под всякие локальные переменные, никаких массивов и скрытых рекурсий.
Самая сложная часть - это поиск шага. Данный алгоритм пытается найти минимальный шаг. Но в теории там сложность O(n). Данный алгоритм в лоб ищет первое нечетное взаимопростое с длинной число. Данную часть можно дорабатывать до получения нужных значений.
Если посмотреть визуализацию заполнения, то это будет выглядеть так. Весь диапазон будет поделен на группы по step и step-1 элементов и вначале будет заполнен каждый первый элемент в группах, потом каждый второй и так далее. То есть, порядок не случайный, но достаточно размазаный. Если же хочется немного большей случайности, то следует посмотреть на Линейный конгруэнтный метод глубже и научиться генерировать для него коэффициенты.
#include
/* нод, взято с википедии */
int gcd(int a, int b) { while (b != 0) { int r = a % b a = b b = r } return a }
/* что то сделать с i */ void doit(int i) { printf("do with %i
", i) }
/* включая a и не включая b, то есть [a,b) */ void processrange(int a, int b) { int len = b - a if (len <= 0) { return /* диапазон вырожден*/ } /* поищем хороший шаг */ /* если такое случиться, что шаг не будет найден, то будет 1 */ int step = 1 for (int i = 3 i < len/2 i+=2) { if (gcd(i, len) == 1) { step = i break } } /* собственно цикл */ int ind = 0 for (int i = 0 i < len i++) { doit(a + ind) ind = (ind + step) % len } }<br>int main(void) { processrange(100,200) return 0 }
