Rejection Sampling and Uniform Distribution

Одна из характеристик хорошей rand-функции — равномерное распределение. Это означает, что каждое возможное значение имеет одинаковую вероятность быть выбрано

Представим, что у вас есть функция rand7(), которая равномерно возвращает случайное число в диапазоне [1, 7]. Наша задача — написать функцию rand10() с диапазоном [1, 10], сохранив равномерное распределение. Дальше вместо rand7() будут использоваться переменные a и b. Скорее всего, вы сходу предложите одну из примитивных реализаций. Вот примеры:

func rand10() int {  
    a, b := rand7(), rand7()
    return a + b % 3
}

func rand10() int {  
    a, b := rand7(), rand7()
    return (a * b) % 10 + 1
}

Обе реализации неправильны

В первом варианте b % 3 даёт остатки от деления на 3, т.е. 0, 1 или 2 не с одинаковой вероятностью. Остаток 1 встречается чаще остальных, из-за чего получается неравномерное распределение итоговых значений.

Во втором варианте количество способов получить каждое произведение a * b тоже неравномерное.
Например:
- 1 = 1 * 1 → 1 комбинация
- 6 = 1*6, 2*3, 3*2, 6*1 → 4 комбинации
- 12 = 2*6, 3*4, 4*3, 6*2 → 4 комбинации
- 36 = 6*6 → 1 комбинация
и так далее

(...) % 10 + 1 ещё больше усугубляет ситуацию, потому что например при product = 2, 12, 22, 32, 42 мы будем везде получать значение 3

На графиках можно наглядно увидеть перекос, перебрав все 49 возможных комбинаций a и b.

Правильное решение

Рассмотрим формулу:
((a - 1) * 7 + b ) % 10 + 1

Она почти равномерна: значения от 1 до 10 встречаются почти с одинаковой частотой, за исключением 10, которое появляется всего 4 раза, тогда как остальные — по 5 раз.

Причина проста - всего комбинаций 7 × 7 = 49, нам не хватает числа 50.

Можно ли без него? Можно - проблема решается с помощью rejection sampling - мы отбрасываем значения больше 40. На языке кода мы делем пересчёт if num > 40. Тогда остаются только 40 комбинаций, которые можно равномерно разбить на 10 групп по 4 значения, что и видно на последней диаграмме

Финальный код:

func rand10() int {  
    for {  
       a, b := rand7(), rand7()
       num := (a-1)*7 + b  
  
       if num <= 40 {  
          return 1 + (num-1)%10  
       }  
    }  
}

Задача на Leetcode: https://leetcode.com/problems/implement-rand10-using-rand7/

Кратенький фанфакт. Обычно используется 0 как литерал для null pointer (говоря о С, макрос NULL там тоже обычно раскрывается в (void*)0 (иногда может в просто 0 или 0L)). Но совершенно не гарантируется стандартом, что 0 будет валидным null pointer для архитектуры! Вот тут hall of shame для именно таких динозавров с nullptr != 0.

Когда-то давно нулл реально дефайнился условно, т.е. он раскрывался в разные вещи для разных целевых платформ. Сейчас этого уже нет, но стандарт-то ведь не изменился. А решение придумали смешное.

Сейчас компилятор (что С, что плюсовый) сам подставляет корректный нулевой адрес вместо литерала 0 в контексте указателей.

Ну, то есть, получили, что ноль не всегда ноль. Ноль в контексте инта - ноль. Ноль в контексте указателя - нихуя не гарантированно ноль. Ноль ноль!

Прикольно. Не знал, что они умеют избегать зануления.

Правда, я всё равно считаю не самым лучшим дизайнерским решением то, что ты подсказываешь компилятору, что ты хочешь не посредством явных подсказок, а с помощью просто тупых стейтментов в надежде, что оно там всё само поймёт. Подстановка runtime.mapclear заместо delete(k, v) в цикле туда же в копилочку

Каждый кадр представляет из себя полный код программы)

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

С другой стороны, с выразительностью Го, хуй я это лучше сделаю. Обидно.

я пока копал, нашел в исходниках го вот такую красивую штуку

там ниже по функции еще смешнее

Интересно, а анализатор вот такую штуку в прологе функции поймёт и элиминирует баундчеки?

Да, элиминирует. Круто

УПД: элиминирует не то, что на предыдущем скрине. Оно поняло только проверку на 16й строке, про аппенды оно ничего не говорит. Скорее всего, не раздуплило

УПД2: очень даже поняло:)

Без условия в начале функции, я получаю 1000нс в бенчмарке на тестовых данных. С условием - 800нс.

Ну нихуя себе, прям как в расте

Мелочь, а приятно

Внезапный факт. Костный мозг - не умный нихуя, но мозгом называется от того, что раньше всё, что внутри костей - называли мозгом. Собственно, головной мозг-то ведь тоже в кости находится.

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

О рандоме, энтропии и статистических текстах

Изначально планировалось запостить на телеграфе, там шрифт покрасивше, чем на телетайпе. Но оказалось, картинки туда больше загружать нельзя - только ссылками оставлять. Позор. Буду делать свое. Какие на жс есть wysiwyg редакторы с драг-н-дропом картинок? А еще лучше - с TeX

https://teletype.in/@floordiv/aopzfO0yNPW

Полтора года у меня дефолтным заголовком висело Accept-Encodings. Если что, он должен быть Accept-Encoding🤭