1. JavaScript / Говнокод #20316

    −44

    1. 1
    2. 2
    3. 3
    for (i = 0; i < Math.random() * 100; i++) {
    //stuff(i);
}

    Нормальное распределение

    Запостил: Stefan, 03 Июля 2016

    Комментарии (25) RSS

    • ava 3_dar 03.07.2016 18:08 # 0

      круто!
      Ответить

    • ava Vindicar 04.07.2016 10:17 # +2

      С какого оно нормальное? Math.random() же дает равномерное?
      Или это шлёптимизация суммы N равномерных случайных для получения нормально распределенного?
      Ответить

      • ava kurwa 04.07.2016 12:32 # 0

        Ну Math.random() на каждой итерации вызывается. Хотя сходу не ясно, какое распределение там в итоге получается.
        Ответить

        • ava Soul_re@ver 04.07.2016 12:44 # +2

          Шанс не пройти итерацию n: Pn = (1 - P(n-1))*n/100

          Х.з. какое это распределение.
          Ответить

          • ava dxd 04.07.2016 14:44 # +1

            Это если рандом хороший.

            Распределение стрёмное, ответ вольфрамальфы я даже причесать толком не смог. Впрочем, никакой порнографии там нет, только факториалы и неполная гамма-функция.
            Ответить

          • ava wvxvw 04.07.2016 16:20 # 0

            Разве это не просто: 99/100 * 98/100 * ... * k/100
            где k - номер итерации которую нужно пройти? Или мы считаем что события как-то зависят друг от друга?
            Т.е. шанс зафейлить первую итерацию: 1 из 100 (т.как i=0, и шанс того, что рандом выкатит 0 - 1/100). На следующией итерации, i=1, и шанс, что рандом выкатит 0 или 1 - 2/100).
            Дальше скадываем разность всех событий и неудач.
            Вцелом, я так понимаю, мы должны ожидать, что примерно 10 итераций пройдем (т.как вероятность около 50%).
            Пройти 27 итераций - вероятность 1%.
            Ответить

            • ava wvxvw 04.07.2016 16:28 # 0

              Эмпирически установлено, что не 10, а 12, вобщем, где-то недалеко от истины.
              Ответить

            • ava wvxvw 04.07.2016 16:37 # +1 

              (defun prob (k)
  (loop :for i :from 99.0 :downto (- 100 k)
     :with result = 1.0
     :do (setf result (* result (/ i 100.0)))
     :finally (return result)))

(defun test-avg ()
  (loop :repeat 1000
     :sum (test) :into x
     :finally (return (/ x 1000.0))))

(defun test ()
  (loop :for i :below 100
     :when (> i (random 100))
     :do (return (1- i))))

              Вобщем, не 12, а 11. Нужно было возвращать последнюю удачную итерацию.
              Ответить

              • ava guestinho 04.07.2016 23:24 # 0

                А всё потому что ...внимание... LispGovno
                Ответить

              • ava nihau 05.07.2016 01:04 # 0 

                
function f() {
	var x = 0;
	var i;
	for (i = 0; i < Math.random() * 100; i++) {
		x++;
	}
	
	return x;
}

Array.prototype.countOf = function(el) {
	var x = 0;
	
	for (var i = 0; i < this.length; i++) {
		if (this[i] === el)
			x++;
	}
	
	return x;
}

var ar = [];

for (var i = 0; i < 100000; i++) {
	ar.push(f());
}

var sorted = {};

for (var i = 0; i < ar.length; i++) {
	var arVal = ar[i];

	if (typeof(sorted[arVal]) === 'undefined')
		sorted[arVal] = { times: 0 };
		
	sorted[arVal].times++;
}

for(var name in sorted) {
    if (sorted.hasOwnProperty(name)) {
		console.log(name + ':' + sorted[name].times);
    }
}

                http://i042.radikal.ru/1607/af/18baf1b01833.png
                Ответить

                • ava Soul_re@ver 05.07.2016 01:20 # 0

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

            • ava roman-kashitsyn 04.07.2016 16:38 # +1

              >> Шанс не пройти итерацию
              > Разве это не просто

              Нет. Твоя формула вычисляет вероятность пройти не менее k итераций. Формула Soul_re@ver вычисляет вероятность пройти ровно n-1 итерацию, и упасть на итерации n.

              Правда, он забыл указать основание рекуррентной формулы P0 = 0, видимо, посчитал очевидным.
              Ответить

            • ava roman-kashitsyn 04.07.2016 16:39 # 0

              > мы должны ожидать, что примерно 10 итераций пройдем (т.как вероятность около 50%).

              > не 10, а 12

              Возможно, кто-то путает медиану и матожидание.
              Ответить

              • ava wvxvw 04.07.2016 16:45 # 0

                Х.з. я по-русски не знаю статистических терминов. Что такое матожидание?
                А почему это вообще интересно считать вероятность пройти конкретное количество итераций?

                Вообще идея похожа на "нанять секретаря". Т.е. задача где нужно посчитать затраты если нанимать секретаря по принципу: за собеседование платим всегда, и если нашли кандидата лучше, то нанимаем нового кандидата (и платим агентству). Это какой-то известный пример анализа амортизированой стоимости.
                Ответить

                • ava inkanus-gray 04.07.2016 16:52 # 0

                  Матожидание — это предел среднего арифметического при количестве испытаний, стремящемся к бесконечности.

                  The expected value is also known as the expectation, mathematical expectation, EV, average, mean value, mean, or first moment.
                  Ответить

                  • ava wvxvw 04.07.2016 17:00 # 0

                    А, ну ок. В том примере о котором я говорил можно использовать E[X], а можно I[X] (indicator variable). С последней считать проще, но не так точно.
                    В любом случае, вывод был, что нужно будет сделать ln n выплат агентству, что примерно сходится.
                    Ответить

                • ava roman-kashitsyn 04.07.2016 17:01 # +3

                  > А почему это вообще интересно считать вероятность пройти конкретное количество итераций?

                  Потому что только так и можно посчитать матожидание (expected value (en), Erwartungswert (de) для иностранных господ), образованный ты наш.
                  Как всегда, много умных слов и выпендрёжа, а в основах плаваем.
                  Ответить

                  • ava wvxvw 04.07.2016 17:09 # 0

                    Как уже было сказано выше: можно использовать indicator variable, и считать исходя из предположения, что события независимые. Тогда не нужно считать вероятность пройти точно Х итераций, а просто использовать вероятность пройти итерацию безотносительно предыдущих попыток.
                    Ответить

          • ava kissarat 11.09.2016 16:00 # 0

            Всмысле шанс получить бесконечний цыкл?
            Ответить

    • ava kurwa-nextgen 04.07.2016 18:21 # 0

      Корочи получается ((n+1) / 100) *(99! / (99-n)! / 100^n). Рекурентные формулы не нужны. График конечно похож на нормальный, но из формулы мне не понятно, действительно ли там такая зависимость или просто похож.
      Ответить

      • ava habrophag 05.07.2016 13:55 # +1

        Да ну, совсем не похож. Нормальное распределение умеет выдавать вообще все значения, в то время как тут - жестко фиксировано от 0 (почти невероятно) и может проползти до 30 (0.5%).
        У нормального распределения совпадают мода, м.о. и медиана, в то время как тут: 10, 12.2 и 12 соответственно. И это еще и не середина диапазона (15 с дов. интервалом 99.5%), как можно было бы хотеть.
        У нормального распределения левая и правая сторона имеют одинаковые по пологости края, в то время как у данного распределения коэффициент асимметрии аж 1.6 (!!!) (впрочем, его положительность следует из порядка мода-медиана-матожидание как раз)
        Если уж есть потребность в подобной дискретизации, нормальное лучше всего моделируется биномиальным. А это просто - подкинуть монетку 100 раз и подсчитать количество "решек". Получается "почти нормальное" распределение с м.о. 50 и дисперсией 25. Легко управляется, считается так же за O(N).
        И это не говоря о человеческих способах преобразования равномерного в нормальное, навроде Бокса — Мюллера.
        Ответить

        • ava kurwa-nextgen 05.07.2016 14:03 # −3

          И вообще оно дискретное, а нормальное - непрерывное, ага. Че еще спизданешь?
          Ответить

          • ava habrophag 05.07.2016 17:04 # +1

            Про дискретность я уже спизданул, предложив биномиальное. Спиздануть чего-нибудь еще, пока я тут?
            Например, могу дать явный ответ на страдания в поисках: "мне не понятно, действительно ли там такая зависимость или просто похож". Нет, не такая даже близко. Ближе биномиального не получится (в том числе, по упомянутым критериям), а от биномиального оно отличается сильно формулой, графиком, поведением моментов и прочих числовых характеристик.
            Ответить

            • ava guest 05.07.2016 17:55 # −3

              Иди мамке свой учебник пересказывай.
              Ответить

    Добавить комментарий