Arseny Kapoulkine:
  • Решение номер один от @mehas (Михаил Окунев):
На самом деле чаще всего нужно не один раз запустить процедуру на строчке, а много раз на разных строчках.
Сложность тогда получается O(QN + QK), давайте попробуем убрать член QK.
Вместо булевого массива делаем массив интовых тегов, и глобальный "текущий" тег.
В первый запуск мы зануляем массив, во все остальные запуски мы просто увеличиваем глобальный тег на один.
И вместо того, чтобы проверять, true ли в элементе массива, мы проверяем, равен ли элемент массива текущему тегу.
При переполнении текущего тега приходится занулять массив еще раз.
Решение очень практичное, я такие теги в разных практических задачах использовал.
  • Решение номер два от меня (я не помню, где я о нем узнал, оно не совсем про эту задачу но применимо):
Как бы нам совсем избавиться от шага инициализации?
Чтобы если Q=1 то иметь не N+K операций а меньше.
Предположим, что нам массив из K элементов могут дать, но он не инициализирован.
Т.е. нам нужна вариация массива, в которой изначально все элементы заполнены случайными числами.
И можно узнать - элемент k ставили когда-нибудь в разумное значение или нет.
Делаем так - берем два массива длиной K, оба забиты случайными числами, и еще переменную count, инициализируем в 0.
Инвариант у нас такой:
Если arr0[k] = x, и arr1[x] = k (и x < count), то k - валидный индекс.
Т.е. функция contains выглядит просто как bool contains(unsigned int k) { return arr0[k] < count && arr1[arr0[k]] == k; }
upd: подразумевается что arr0 - массив unsigned, т.е. arr0[k] < count это bounds check на array lookup.
Функция вставки проверяет, валидный ли индекс, и если нет, то настраивает массив - в arr0[k] записывает count, в arr1[count] записывает k, count увеличивает на 1.
Эта штука по-моему не супер практичная, мне использовать не доводилось.
Но зато забавная.
Mikhail Bogatyrev:
... а в некоторых языках, можно массиву элементов давать любые индексы, так что значение из строки можно назначать как индекс и обращаться к нему через индекс, не пробегаясь по нему (хотя канеш в любом случае будет внутренний поиск...).
Denny Gursky:
а тонкий намек на юникод и хеш-табличку не спасет?
Arseny Kapoulkine:
Ну хеш табличка это не O(N+K) в худшем а хрен пойми что.
Ivan Dobrokotov:
Я помню в "programming pearls" была такая задача.
Михаил Окунев:
Что-то не очень понимаю, почему это срабатывает. Почему соответствующие значения не могут получиться случайно и у нас будет false positive?
Denny Gursky:
потому что никогда не бывает так что мы случайно получим память которую мы уже использовали для этого? :)
Михаил Окунев:
Ладно, перечитаю еще разок.
Arseny Kapoulkine:
Смотри, ты контролируешь целиком второй массив.
Т.е. у тебя заполнен твоими данными какой-то префикс второго массива (см. count)
И вот этот префикс не может стать невалидным - исходно он пустой.
Михаил Окунев:
Да, кажется догнал.
Красиво.
Ivan Dobrokotov:
mmap MAP_ANONYMOUS.
The mapping is not backed by any file; its contents are.
initialized to zero.
Иногда немножко обидно осознавать, что твои хитрые алгоритмы - бегут поверх аппаратно ускоренного дерева поиска ( http://en.wikipedia.org/wiki/Translation_lookaside_buffer http://en.wikipedia.org/wiki/Page_table#Multilevel_page_table ), и не имеет смысла выёживаться.
Arseny Kapoulkine:
Ну как бы не совсем.
Например, первая инициализация означает маппинг страниц в физическую память, page faults итп.
Если ее нет то это делать не надо!
Serguei Narojnyi:
cute, но да, я б за такой код в production бил бы :-)
Simon Kozlov:
Вторая штука прикольная, действительно. Как из случайной памяти сделать некую sparse лукап-таблицу через дополнительную память и мааахонький кусок памяти, которому ты можешь доверять.
Я запосчу это все добро?
Arseny Kapoulkine:
Ага.
Очевидным образом то что я написал - это sparse bitset, он расширяется до sparse set т.е. в ячейках можно хранить значения точно так же.
Более того, значения можно хранить в том самом втором массиве, т.е. не надо под них держать память на все.