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

[avva]

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

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

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

Comments

[http://users.livejournal.com/_winnie/]

>Второе решение - та же инициализация за O(N), только размазанная во времени
Эм. Третье - такое же размазанное. Если мы прочитаем из массива всё, то мы получим замедление в несколько раз, по сравнению с быстрым (за счёт локальности) memset(,0,)+обычным доступом по индексу.

Скорее, можно придраться что второе решение - требует log(N) операций при чтении/записи (где log равен 3-5 для практических значений). хотя как я заметил, что почему-то пытаются закрыть глаза на то, что доступ к массиву по индексу - это нифига не O(1) на практике. Рандомный доступ к массиву в терабайт не такой же как к массиву в килобайт.

>Первое решение не годится, так как не будет работать на компьютере Apple II, где нет ни SEH, ни сигналов :) Если серьёзно, то это должен быть чисто процедурный алгоритм, никак не опирающийся на особенности операционной системы.
Можно сэмулировать операционную систему на машине тьюринга!

исправил N на log(N)

[alexeybobkov]

Если мы прочитаем из массива всё, то мы получим замедление в несколько раз, по сравнению с быстрым (за счёт локальности) memset(,0,)+обычным доступом по индексу
Это так, но в условиях задачи не сказано, что мы будем обращаться ко всем элементам массива. Если мы обращаемся только к K элементам, где K << N, то в третьем случае (со стеком) мы всегда будем иметь O(1) на каждое обращение, то есть всего O(K). Для второго же решения, насколько я понимаю, и как вы сами написали, в худшем случае общее время будет хуже, чем O(K) (не соображу, какое именно, мозги уже не работают к концу дня).