Сэмплинг данных онлайн

Задание 1

Необходимо реализовать (на любом адекватном языке программирования, кроме R) структуру данных (т.е. контейнер), которая позволяет сделать следующие операции:

1. Добавить элемент \$x_i\$ с положительным вещественным весом \$w_i\$ в контейнер (если он уже там лежит – заменить вес).
2. Удалить элемент \$x_i\$ из контейнера.
3. Получить элемент случайным образом в соответствии с вероятностями \$p_i = w_i / (\sum_{j=1}^N w_j)\$, где \$N\$ – текущее количество элементов в контейнере.

Подход

Для начала стоит попробовать решить задачу для частных случаев:

1. Удалений нет, все операции добавления идут строго до операций получения элемента (оффлайн случай).
2. Удалений нет, все веса \$w_i\$ одинаковые, все \$x_i\$ при добавлении разные.
3. Предыдущий пункт, но удаления допускаются, \$x_i\$ могут повторяться.
4. Общий случай :).

Понятно, что каждый пункт можно решить “в лоб” достаточно тривиально, поэтому интересуют решения, в которых операции работают быстро (т.е. лучше, чем за \$O(N)\$). Естественно, что изобрести такую структуру сходу достаточно сложно (а доказать оптимальность решения и вовсе почти нереально), поэтому предполагается обсуждение решения с руководителем перед его реализацией. Реализацию нужно покрыть тестами, т.е. замерить время работы для больших наборов входящих данных и соответствие полученной выборки заданному распределению (например, с помощью критерия Хи-квадрат) + проверить на отсутствие ошибок и падений в частных случаях.

Задача предполагает интенсивное изучение и программирование алгоритмов и структур данных. Литературу предоставит руководитель.

Баллы

Фиксированной сетки нет, итог зависит от работы студента над задачами. Максимальный балл за всю задачу: 1 курс – 100 баллов, 2 курс – 50 баллов.

Руководитель

Звонарев Никита Константинович