Имеется два числа задающих диапазон, нужно в цикле что-то сделать с каждым числом но не по порядку циклом, а в случайном порядке.
Диапазоны заведомо не известны и являются большими поэтому сложность и потребление памяти нужны O(1).
Какие алгоритмы/паттерны для этого можно использовать?
-
Уточните, насколько случайным должен быть случайный порядок? Нужна ли истинная случайность, псевдо, или может даже простой перебор с шагом сгодится?– Kromster13 сен 2016 в 10:59
-
Какой-то истинной случайности точно не нужно, можете себе представить что диапазон разделен на блоки разного неизвестного мне размера(известно разве что максимум чисел которые может вместить блок) и вот мне надо как можно реже обрабатывать число из каждого блока. Возможно и какой либо шаг сгодится даже но разумеется не статичный.– Віталій Карпенко13 сен 2016 в 11:07
-
2используйте "алгоритм Иосифа". Выбирается какое то число, желательно, что бы НОД(число, размер массива) было 1. а дальше следующий индекст это предыдущий + число и делить по модулю на размер массива.– KoVadim13 сен 2016 в 11:14
-
Можете написать примерную реализацию, а то я не особо понял как это реализовать? Хотел бы так же уточнить на всякий случай что массивов у меня нет, то есть число != индекс в массиве например, для меня нужная информация в числе.– Віталій Карпенко13 сен 2016 в 11:26
-
А где и как у вас лежат эти числа?– Kromster13 сен 2016 в 14:12
1 ответ
Набросал код, беглые тесты показывают, что он вроде решает Вашу задачу.
код написан на с99 (то есть, используется объявление переменных не в начале блока), поэтому в gcc нужно компилировать с -std=c99
, студия 2013 может не скомпилировать, а 2015 скорее всего справиться. Но переписать код не проблема, что бы он работал даже с древними компиляторами.
Потребление памяти тут точно O(1)
, так как память выделяется только под всякие локальные переменные, никаких массивов и скрытых рекурсий.
Самая сложная часть - это поиск шага. Данный алгоритм пытается найти минимальный шаг. Но в теории там сложность O(n)
. Данный алгоритм в лоб ищет первое нечетное взаимопростое с длинной число. Данную часть можно дорабатывать до получения нужных значений.
Если посмотреть визуализацию заполнения, то это будет выглядеть так. Весь диапазон будет поделен на группы по step и step-1 элементов и вначале будет заполнен каждый первый элемент в группах, потом каждый второй и так далее. То есть, порядок не случайный, но достаточно размазаный. Если же хочется немного большей случайности, то следует посмотреть на Линейный конгруэнтный метод глубже и научиться генерировать для него коэффициенты.
#include <stdio.h>
/* нод, взято с википедии */
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\n", 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;
}
}
int main(void) {
processrange(100,200);
return 0;
}
-
В принципе можно добавить случайность в выбор шага (искать нод от
rand() % (len/2) + 1
до 1). Я спрашивал ТС в комментарии о таком подходе, но он что-то молчит. По хорошему, тут надо бы придумать какую-то формулу для переменного шага, обеспечивающую однократное посещение всех чисел, но у меня не получается.– avp14 сен 2016 в 10:13 -
Не знаю как в теории но на практике О(n) не заметно, если вы конечно имели в ввиду время между вызовом фунции
doit
. Оно у меня одинаковое и при диапазоне 1-1000000 и при 1-1000000000. Алгоритм отлично подходит. 14 сен 2016 в 11:52 -
-
Да, уже понял, в вычислении шага О(n) но оно роли не играет ибо действительно происходит очень быстро 14 сен 2016 в 12:07