предыдущая задачка, и еще одна (программистское)

[avva]

Я раскрываю все скрытые комментарии с правильными решениями к позавчерашней задачке. Если хотите все еще решать ее самостоятельно, не заглядывайте в комментарии. Спасибо всем, кто решал. Первый, кто нашел оптимальное решение за O(N) времени и O(1) памяти - ilyaraz.

Вот еще одна программистская задачка. Я когда-то знал ее решение и забыл, недавно с удовольствием решил снова. Эта задачка довольно хорошо известна, и в частности часто преподается на курсах продвинутых структур данных, и упоминается в учебниках. Так что многие наверняка ее знают - если вы знаете решение, то не пишите в комментариях. Для тех, кто не знает, это отличное упражнение для ума, по-моему.

Задача: требуется воплотить массив с дефолтным значением для всех элементов, т.е. структуру данных с тремя операциями: get(i), set(i, value) и setdefault(value). Любой вызов get() с индексом, который до сих пор ни разу не передавался set(), должен возвращать последнее выставленное дефолтное значение (или 0, если такого не было). Сложность в том, что все три операции: get, set и setdefault, должны занимать O(1) времени. При этом нельзя рассчитывать на то, что отведенная нам память имеет какой-либо специальный вид, например, заполнена нулями. Любая используемая память изначально содержит случайные байты, которые мы никак не можем контролировать.

Comments

[zhengxi.livejournal.com]

Дык, хеш-таблица (std::unordered_map в C++) + хранение default
Как раз O(1) для set и get

[avva.livejournal.com]

хеш-таблица дает O(1) только в среднем, а требуется жесткий предел в худшем случае.

[alexeybobkov]

Что-то я не понимаю условия задачи. Что значит "отведённая нам память"? Она что, ограничена? Если да, что значит ли это, что размер массива фиксирован? Если нет, то как работают аллокаторы, за какое время? Какие вообще условия на использование памяти? Ничего не понимаю...

[sascha (from livejournal.com)]

Но при этом разрешается использовать сколько угодно памяти? :-)
Если да, то я умею, буквально пару недель назад пришлось изобрести, чтобы не состариться за время инициализации :))

[zhengxi.livejournal.com]

Тогда после set() ослеживать длину списка в той bucket, куда был добавлен элемент, и увеличивать (удваивать) число bucket'ов, если список стал длиннее некоторого N.
Тогда будет жёсткий предел O(1) по времени, но за счёт памяти и операций копирования после некоторых set.

[kosiakk.livejournal.com]

если массив фиксированной длины и c цифровыми индексами, это не так и сложно.

для хранения выделяется непрерывный участок виртуальной памяти - обычный массив в С++

плюс дополнительный "индексный" массив uint'ов длины array_length / sizeof(int) / 8 + 1 - т.е. по одному биту на элемент массива.

его придётся заполнить нулями, но эта операция в 32-64 раза быстрее чем заполнение нулями основного массива, которое в данном случае не потребуется

ну а дальше просто - по битовой маске и содержимому индексного массива понимаем были ли там пользовательские данные, и если нет - возвращаем текущее default-значение. Очевидно, set должен взводить бит соответствующей ячейки:

index[ i \ sizeof(int) ] & ( 1 << (i % sizeof(int)) )

[avva.livejournal.com]

Попросту говоря, вызов malloc() занимает О(1) времени, но возвращает память, содержимое которой совершенно неизвестно. Так понятнее?

Вы можете предположить, простоты ради, что максимальный размер массива известен заранее, и подготовить под него вашу структуру данных, но все эти подготовки должны занимать O(1) времени, а не O(n). Т.е. можно например заранее выделить нужную память с помощью malloc(), но нельзя обнулить ее всю в цикле, или что-то еще во все ее ячейки записать.

[avva.livejournal.com]

С практической точки зрения это может и рещает проблему, но "в 32-64 раза быстрее" чем O(n), это все еще O(n). А нужно именно O(1).

[avva.livejournal.com]

Все равно можно подобрать такой поток входных данных, чтобы они все время попадали в один и тот же bucket, и заставили ваш алгоритм быть медленее, чем O(1) - если не за счет самих добавлений, то за счет удваиваний.

[alexeybobkov]

Да, теперь понятно, спасибо. Подумаю.

[avva.livejournal.com]

Сколько угодно памяти, но всю ее можно приводить в нужный вид лишь за O(1) времени.

[zhengxi.livejournal.com]

set записывает в такую ячейку пару (value, sha256(value))

get возвращает
entry[1]==sha256(entry[0]) ? entry[0] : default

[zhengxi.livejournal.com]

А если в bucket хранить не list, как обычно, а другую хеш-таблицу, с другим алгоритмом хеширования?

[poteshnaya.livejournal.com]

Можно разъяснение по прошлой.
Что-то я не догоняю.
Смотрю питоновый код.
берем входящие данные 1123

Идем по коду

def finddup(arr):
i = len(arr) - 1 # last //i=3
looplen = 0
while looplen < n:
i = arr[i] //i = arr[3] = 3
looplen += 1

if arr[i] == i: //3 == 3
# no loop, fixed point
return i //Ответ = 3

А должно быть 1.
Я понимаю, что это я дурак, но не пойму, где именно.
Просто я тоже, когда пытался решить, уперся в циклы, но не смог из них пользы достать со сложностью O(n).

[dmage-ru.livejournal.com]

Теоретически мусор может оказаться именно вида (мусор, sha256(мусор)) :)

[avva.livejournal.com]

Да, все верно, это более или менее каноническое решение этой задачи :) Я заскриню его на время.

[avva.livejournal.com]

все равно какой-нибудь плохой вход да найдется.

[dmage-ru.livejournal.com]

Этот код чуть-чуть под другие условия (для удобства): массив содержит числа не от 1 до N-1, а от 0 до N-2.

Т.е. входящие данные должны быть 0012

[poteshnaya.livejournal.com]

А!) вот поэтому я и не решил.
Хотя крутился вокруг.
Спасибо

[mixa.livejournal.com]

Пусть будет два массива, main[] в котором собственно значения, и вспомогательный aux[], и еще две переменных -- lastDef и defCounter.

При вызове setdefault(value) делаем lastDef = value и defCounter++.

При вызове set(i, value) в main[i] записываем value, а в aux[i] -- defCouner.

Смысл aux[i] -- "после aux[i] по счёту вызова setdefault() значение main[i] изменилось"

На вызов get(i) сначала сверям текущий defCounter и aux[i]. Если defCounter > aux[i], возвращаем lastDef (после последнего обновления дефолтного значения main[i] не менялся), если defCounter == aux[i], возвращаем main[i]

[avva.livejournal.com]

Возможно, там недочет в коде, я уже не помню. Суть в том, что надо начинать искать цикл с точки, в которую невозможно вернуться обратно, потому что ее индекс за пределами значений массива. Какая эта точка, зависит от того, откуда массив считать. Если мы считаем индексы от 1 до N, значения от 1 до N-1, надо начинать с индекса N, но иметь в виду, что индексы концептуально начинаются с 1, и код строить соответственно. Поскольку в Питоне индексы начинаются с 0, нужно писать что-то вроде i = arr[i-1]. Если вы пройдете так по вашим данным, то дойдете до единицы.

Или можно наоборот сказать: будем считать индексы массива от 0 до N-1, а значения от 1 до N-1, и тогда начнем цикл с первого значения (индекс 0), потому что к нему невозможно будет вернуться. Тогда начинаем с i=0 и делаем i = arr[i].

[mixa.livejournal.com]

Один раз однако aux[] надо будет нулями забить, это O(N), но на инициализацию ограничения не было.

[avva.livejournal.com]

Нет, увы, любая инициализация тоже должна быть за O(1).

[avva.livejournal.com]

Да, все верно, это решает проблему.

[alexeybobkov]

Интересно, а в каноническом решении та же идея?