Случайные нули

venco · Post by **venco** » 16 May 2007 22:16

После выполнения кода

    int a[N];
    for (int i = 0; i < N; ++i)
        a[i] = rand() % N;
    for (int i = 0; i < N; ++i)
        a[a[i]] = 0;

сколько в среднем нулей будет в массиве?

PavelM · Post by **PavelM** » 16 May 2007 22:38

Один

dimp · Post by **dimp** » 16 May 2007 23:33

Чисто интуитивно... N/2

PavelM · Post by **PavelM** » 16 May 2007 23:38

PavelM wrote:Один

N

AndreyT · Post by **AndreyT** » 17 May 2007 00:33

N/2 навскидку. Может можно чуть уточнить...

Разумеется, всякий неумеренно педантичный С/С++-ник должен заметить, что поведение выражения 'a[a[i]]= 0' в потенциально возможной ситуации, когда 'a[i] == i' вызывает определенные подозрения

http://open-std.org/jtc1/sc22/wg21/docs ... e.html#438

И ежу понятно, что, если подобная задачка попадается вам на интервью, от вас ожидают именно такого неумеренно педантичного ответа :mrgreen:

Hamster · Post by **Hamster** » 17 May 2007 05:53

аналитической формы, скорее всего нет.
Для маленьких N:

1: все нули
2: все нули
3: 70/27 ~ 2.593
4: 401/128 ~ 3.133
5: 11431/3125 ~ 3.658
6: 4057/972 ~ 4.174

Для больших N асимптотически ~N/2

AndreyT · Post by **AndreyT** » 17 May 2007 07:35

Hamster wrote:аналитической формы, скорее всего нет.

Хм... Мне кажется, что асимптотически количество финальных нулей совпадает с количеством элементов в изначальном назначении, для которых 'a[i] <= i'. Отсюда и получается N/2.

lolka · Post by **lolka** » 17 May 2007 22:07

у меня какое-то зубодробительное решение.

асимптотическая пропорция мат. ожидаемого нулей = 1-exp(-1). venco, признавайтесь, красивое решение имеется?

venco · Post by **venco** » 17 May 2007 23:47

У меня решения нет, но метод Монте-Карло даёт ~ N/2 + 1.2

lolka · Post by **lolka** » 18 May 2007 00:11

MC, фи-с.

AndreyT · Post by **AndreyT** » 18 May 2007 00:46

"Лобовое" решение достаточно красиво, по-моему...

Перед началом процесса обнуления (т.е. циклического выполнения 'a[a[i]] = 0') элементы нашего массива можно разделить на две группы: a[i] <= i и a[i] > i.

1) Обработка элемента из группы a[i] <= i будет "как правило" приводить к обнулению элемента с индексом j = a[i] (т.е. "как правило" будет добавлять один ноль в результат). Это элемент располагатся в уже пройденной части массива (j <= i) и на дальнейшее поведение никак не влияет.

2) Обработка элемента из группы a[i] > i тоже "как правило" будет приводить к обнулению одного элемента c индексом j = a[i], т.е. добавлять один ноль в результат. Но тут надо заметить, что этот элемент располагается в еще не пройденной части массива (j > i). Рано или поздно мы в цикле доберемся до элемента a[j], и, так как a[j] теперь равно нулю, выполнение 'a[a[j]] = 0' приведет к обнулению элемента a[0]. Т.е. обработка таких элементов a[j] новых нулей в массив "в среднем" не привносит т.к. она будет лишь многократно обнулять один и тот же элемент a[0].

Таким образом получаем, что элементы второй группы с одной стороны добавляют в массив 0, но с другой стороны побочным эффектом этого является то, что позже из массива "убавляется" потенциальный новый 0. Т.е. в конечном итоге суммарный эффект "в среднем" от таких элементов отсутствует - они не меняют финального количества нулей.

Получаем поэтому, что финальное количество нулей равно изначальному количеству элементов вида a[i] <= i. Оно равно (при таком способе заполнения) N/2. Это грубый ответ.

Можно учесть, что элементы второй группы все вместе таки будут "в среднем" добавлять в массив один единственный ноль "на всех" - а именно, как описано выше, приводить к многократному обнулению элемента a[0]. Т.е. более точный ответ: N/2 + 1. Вот и все решение.

А вот откуда берется N/2 + 1.2 и так ли это на самом деле - пока не знаю.

Hamster · Post by **Hamster** » 18 May 2007 03:05

venco wrote:У меня решения нет, но метод Монте-Карло даёт ~ N/2 + 1.2

все намного сложнее, попробуйте Монте-Карло для нескольких последовательных N>200.

AndreyT · Post by **AndreyT** » 18 May 2007 06:12

Hamster wrote:
venco wrote:У меня решения нет, но метод Монте-Карло даёт ~ N/2 + 1.2

все намного сложнее, попробуйте Монте-Карло для нескольких последовательных N>200.

И? Попробовали. Совершенно четко получается, как и предсказывалось: N/2 + 1. Где тут "намного сложнее"?

Hamster · Post by **Hamster** » 18 May 2007 08:17

AndreyT · Post by **AndreyT** » 18 May 2007 08:45

А пояснить? Что там по вертикальной оси на графике отложено?

Hamster · Post by **Hamster** » 18 May 2007 08:52

среднее число нулей минус N/2.

venco · Post by **venco** » 18 May 2007 14:26

Hamster, а у вас хороший генератор случайных чисел?
У меня разница получается очень близко к 1.25, и от N практически не зависит, отклонение в пределах статистической ошибки.

lolka · Post by **lolka** » 18 May 2007 17:18

Ничего себе. Hamster, сколько runs for every n? Нарисуйте график наблюденной дисперсии, пожалуйста.

Hamster · Post by **Hamster** » 19 May 2007 01:21

ага, разобрался. Дело частично в генераторе, частично в моей ошибке, частично в неточной постановке задачи.

1) генератор в MSVC выдает числа в диапазоне от 0 до 32767
2) генераторы случайных чисел, как известно, часто не гарантируют достаточной случайности нижних бит
3) чтобы этого избежать, я сдвинул результат rand() на несколько бит
4) rand() % N не выдает числа от 0 до N-1 с равными вероятностями, если N это не не делитель RAND_MAX+1 ( в данном случае 32768 ).

Даже без моего сдвига в MSVC будет тот же результат, только для больших N.

Правильная постановка задачи:

Code: Select all


    unsigned int a[N];
    unsigned int divisor = (RAND_MAX-N+1) / N;
    unsigned int max_rand = divisor * N + N - 1;
    ++divisor;
    int i;
    for (i = 0; i < N; ++i)
    {
        unsigned int random_number = rand();
        if(random_number <= max_rand)
           a[i] = random_number / divisor;
        else
        {
           --i;
          continue;
        }
    } 
    for (i = 0; i < N; ++i)
        a[a[i]] = 0;

lolka · Post by **lolka** » 19 May 2007 14:38

Hamster, Вы одной реализацией случайной величины оцениваете мат. ожидание? Ну да ладно, график, по крайней мере первый, был pretty tight. А не поделитесь с публикой новым графиком? Если можно, для большего диапазона для n. Дело в том, что на первом графике прозлеживалась возрастающяя поправка. Я все пытаюсь убедиться что 1/2 на самом деле не правильный ответ. :mrgreen:

venco · Post by **venco** » 20 May 2007 23:48

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

N = 100, Z = 51.24561 = 100/2 + 1.25 - .44/100
N = 200, Z = 101.24781 = 200/2 + 1.25 - .44/200
N = 400, Z = 201.24891 = 400/2 + 1.25 - .44/400
N = 800, Z = 401.24945 = 800/2 + 1.25 - .44/800
:gen1:

Flash-04 · Post by **Flash-04** » 21 May 2007 00:41

то довольно фиговые генераторы. правильный PRNG - одобренный FIPS 140-2

кстати, неплохой результат дает вычисления хеша MD5 или SHA-1 - классический генератор для превращения последовательности с низкой энтропией в последовательность с высокой энтропией. всебудет лучше чем стандартный rand

venco · Post by **venco** » 21 May 2007 01:46

Нынешний GNU-шный rand() весьма неплох.
Я собственно им пользовался, ну ещё для проверки прогнал с MersenneTwister.

venco · Post by **venco** » 21 May 2007 01:53

Я немного уточнил формулу:

Z = N/2 + 5/4 - 7/16N - 7/64N^2 - 9/256N^3

Дальше пока точности не хватает.

kostia00 · Post by **kostia00** » 21 May 2007 04:23

venco wrote:Я нашёл способ посчитать точно за полиномиальное время. Правда степень четвёртая, так что для действительно больших N пока посчитать не могу.

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