Локальная или интегральная теорема Лапласа?

Alexandroppolus,

если продолжить испытания после 600 успехов, но результаты, условно говоря, никуда не записывать, то это всё равно что этих испытаний не проводили. Так что фиксированные 2300 испытаний ничего не ломают.

я имел в виду, что взять и просуммировать бернулли для всех k от 600 до 2300 (то что и делает теорема лапласа) точно нельзя, как минимум потому что в задаче говорится, что попытки заканчиваются в двух случаях: либо мы таки нашли 600 чисел и завершились успхом, либо вытащили 2300 и не нашли и завершились неудачей. но про "никуда не записывать" если честно не понял
вообще, мне кажется в задаче имеется в виду, что берётся 2300 за раз и уже там ищатся 600 чисел, потому что она как раз из главы с теоремой лапласа

если я правильно понял рекурентную формулу F(i, j), где i - число испытаний, j - число успехов, а F - вероятность события при i и j, то F(i, j) считается просто по формуле бернулли, но тогда P(N) = F(N-1, 599) * 1/4 же будет вычисляться, как F(N-1, 599) * 1/4 и ещё это произведение нужно разделить на биноминальный коэффициент для i-1, j и умножить на тот же коэффициент но для i, j

Такие варианты, очевидно, не пересекаются. Полная вероятность будет суммой
P =1/4 * sum[n = 599...2299](F(n, 599))

вот здесь, если честно не понял

Локальная или интегральная теорема Лапласа?

Хм, но ведь в задаче сказано: "пока их не наберется 600 штук", то есть: как я понял, отбираются по одному, а не сразу, например, 2300 за раз и там ищется 600 нужных. А значит для случая, когда, например 601, 601, 800 и т.д. успехов модель построена неправильно, ну то есть должно быть p^600 * (1-p)^(n-600) * C(n;600), для всех n от 600 до 2300 (C(n;600) - это сочетания из n по 600)

Например, вероятность для числа испытаний n = 2000 будет включать вероятность для n = 1000, в том числе потому что для n = 2000 за первые 1000 испытаний может произойти событие для n = 1000. Поэтому вероятности для числа испытаний n от 600 до 2300 нужно суммировать, но так, чтобы учитывать дублирование, то есть тут нужна какая-то формула включений-исключения

Где могла закрасться ошибка?

Wataru, спасибо, довольно неплохая метафора с площадью

Где могла закрасться ошибка?

Кстати, всегда мучил следующий вопрос в теории вероятностей: вот тут есть 3 способа решить эту задачу:
1. Через комбинаторику (достаточно легко запутаться, но можно)
2. Через условную вероятность + умножение вероятностей (тоже легко что-то не учесть, но попроще, чем 1-й способ)
3. Через умножение вероятностей (хотя умножение, насколько я понимаю выводится из усл. вероятности, которая является вообще аксиомой)

Все эти 3 модели опираются на некоторые простые факты:
1-й способ на равновероятность всех возможных игр и классическую формулу вероятности;
2-й способ на теорему усл. вероятности, умножение вероятностей, классическую формулу вероятности
3-й способ на умножение вероятностей, классическую формулу вероятности

При этом у этих 3-х моделей, казалось бы, совсем непохожих, одинаковый результат при довольно нетрривиальных вычислениях.
И любопытно: есть ли у этих 3-х моделей под собой какая-то единая база (как, например, в геометрии). Ну вот, например, у 2-го и 3-го способа вроде бы есть, а вот у 1-го и 2,3-х способов уже довольно затруднительно сказать. Хотя я вот для себя это понимаю (что 3 модели дают одинаковый результат) просто, что у них у всех в конечном счёте одинаковые меры множества

Где могла закрасться ошибка?

Спасибо за ответ :)

Где могла закрасться ошибка?

Несовсем понял, почему тег сменили с математики на алгоритмы, когда в вопросе представлена задача по теории вероятности, неужели потому что в тексте есть ссылка на код

Нужно ли здесь выравнивание на стеке?

А, ещё вопрос:
если есть момент, когда ROOT_POS = insertPosition, но именно в этот момент в buffer будет находиться мусор, может ли привести такой memcpy к UB с логической точки зрения ? Ну то есть поскольку области будут перекрываться, то это UB формально, но так как там уже лежит мусор, то, если мусорные объекты станут в невалидном состоянии, то это не UB. Или может что-то ещё произойти ?

memcpy(&buffer[ROOT_POS], &buffer[insertPosition], sizeof(Entry<K, V>));

Нужно ли здесь выравнивание на стеке?

Не уверен, поэтому и делаю )

Является ли безопасным отнять от указателя 1 и итерироваться по массиву [1,N], а не [0, N-1]?

Wataru, они, как правило внутри даже malloc не используют, а прямо системные вызовы типа mmap

Является ли безопасным отнять от указателя 1 и итерироваться по массиву [1,N], а не [0, N-1]?

maaGames, график

Тут на графике зеленым цветом обозначены количества сравнений в зависимости от d, а фиолетовым - глубина дерева, то есть максимальное количество скачков по рандомным областям памяти
Ну а там, где прямые линии это графики для d=2, то есть классической кучи
Параметр 1'000'000 - количество элементов
Это для sift down/up

Является ли безопасным отнять от указателя 1 и итерироваться по массиву [1,N], а не [0, N-1]?

maaGames,

cache line разного размера всё же бывает. Если Entry больше размера cache line, то можно особо и не париться. Например, если это 64 байта, то из чего вообще Entry состоит, чтобы не только указатель на дочерний(дочерние) элементы хранить, но ещё и полезные даные были?

Ну просто сделать отдельную сборку для чипов с 64 и 128 байтами длинной кеш линии, чтобы в compile-time d вычислять. Ну либо в рантайме вычислять, но всё же в compile-time безопаснее намного

Ключ K это число (теоретически может быть последовательность байт, но такого для куч не встречал никогда, если всё-таки это она, то d heap ничего не даст по сравнению с бинарной), т.е. размер не превосходит 8 байт. А V, если размер V, больше 8 байт делают указателем, итого K+V не больше 16 байт и уже можно сделать d = 4. При увеличении d падает количество рандомных скачков по памяти, например при увеличении d с 2 до 4 - в 2 раза, но при этом растёт количество сравнений, поэтому d обычно берут от 4 до 16
Ну и да, все дети одного родителя должны лежать в одной кеш линии, тогда по ним по всем пробежаться можно будет за 1 промах по кешу

Является ли безопасным отнять от указателя 1 и итерироваться по массиву [1,N], а не [0, N-1]?

Где в вопросе упоминание хотя бы архитектуры процессора, на котором будет работать? А какие данные в массиве?

не понимаю, что это даст в данном контексте, на мой взгляд, в вопросе достаточно инфы

Entry это K, V или K, Void
d выбирается таким образом чтобы d = cache_line_size / k.size + v.size, если нацело не делится, то в Entry padding добавляется, то есть по умолчанию он 0

вроде бы стандартная реализация d кучи )

Является ли безопасным отнять от указателя 1 и итерироваться по массиву [1,N], а не [0, N-1]?

Wataru, ну, например если пишешь свой кастомный аллокатор типа jemalloc или tcmalloc, то какими правилами руководствоваться, хотя по идее там просто работа с void*, мб оно спасает

Является ли безопасным отнять от указателя 1 и итерироваться по массиву [1,N], а не [0, N-1]?

Any other use of an invalid pointer value has implementation-defined behavior.

Хм, по этим правилам выведения является ли указатель невалидным непонятно, как тогда оно будет работать в коде аллокатора

Является ли безопасным отнять от указателя 1 и итерироваться по массиву [1,N], а не [0, N-1]?

Для 1го случая тогда уж взять "некрасивую" формулу (хотя , как выяснилось, если скобки в ней раскрыть, то норм) и с 0го по N-1 работать
А во втором случае дети ребёнка не лягут в одну кеш линию

Является ли безопасным отнять от указателя 1 и итерироваться по массиву [1,N], а не [0, N-1]?

Весь низкоуровневый код один большой фокус )

Является ли безопасным отнять от указателя 1 и итерироваться по массиву [1,N], а не [0, N-1]?

mayton2019, короч действительно, получилась проблема XY

Является ли безопасным отнять от указателя 1 и итерироваться по массиву [1,N], а не [0, N-1]?

mayton2019,

а, точно, можно же скобки раскрыть:
j-й child j[d; 2d-1] : i*d + j

Является ли безопасным отнять от указателя 1 и итерироваться по массиву [1,N], а не [0, N-1]?

mayton2019,

Индексация с 1:
j-й child j[1; d] : i*d+j
parent: (i-1)/d

Индексация с 0:
j-й child j[0; d-1] : (i+1)*d+j
parent: (i-d)/d

Всё-таки для индексации с 1 формулы получше + даже быстрее немного доступ к ребенку

Seed для CRC32?

mayton2019, я не знал, что там речь шла именно о популярных/непопулярных ключах
Почему O(1) нельзя в данном случае ? Всегда можно сделать размер таблицы n^2 и захешировать, в среднем за 2 раза без коллизий сойдётся. Но с одной стороны так много памяти жалко, с другой, даже, если там будет всего лишь 10к интов, то оно даже в L3 не уложится (нужно 400 мб для этого, а стандавртный серверный L3 обычно 128/256 мб)