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

Хм, но ведь в задаче сказано: "пока их не наберется 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 мб)

Seed для CRC32?

floppa322, я вот решил следующее посчитать. Допустим я не буду вставлять конфликтующие ключи. А просто буду вести их список. Долг типа. Вот получилось так на 5 млн.

2023-07-28 20:06:28,511 : [INFO] - Start demo
2023-07-28 20:06:29,417 : [INFO] - Populated successfully!
2023-07-28 20:06:29,417 : [INFO] - Inserted : 3160854
2023-07-28 20:06:29,419 : [INFO] - Collision list size : 1839146
2023-07-28 20:06:29,419 : [INFO] - Hash set physical size is 5000000 slots (20000000 bytes)
2023-07-28 20:06:29,419 : [INFO] - Inserted/slots ratio : 63%
2023-07-28 20:06:29,419 : [INFO] - Finish

Из 5 лямов успешно вставились порядка 3.1 млн. Долговых ключей на 1.8. Хорошая новость
их хотя-бы не так много. Далее я могу рекурсивно применить алгоритм построения этой-же
таблицы к списку долговых ключей. Но теперь мне уже не нужно 5 млн слотов. Я сразу создаю
1.8. И если эта геометрическая прогрессия работает (100% - 63% = 37%) то каждый раз
я буду получать треть от оригнального размера. Хеш функцию в данном случае можно
даже не менять. Просто меняется у нас остаток от деления. Будет пирамида таблиц.

Если честно, у меня пока нет никаких мыслей, как это можно развить, чтобы было O(1) без жирных констант на contains