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

[avva]

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

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

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

Comments

[avva.livejournal.com]

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

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

[alexeybobkov]

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

[zhengxi.livejournal.com]

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

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

[dmage-ru.livejournal.com]

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

[(Anonymous)]

Даже практически может. Память, которую нам система выделяет, мы же в систему и положили. Вот там и осталось (value, sha256(value)) с прошлого раза.

[zhengxi.livejournal.com]

Эта проблема решается счётчиком generations, увеличивающимся при каждом malloc'е такой структуры и как-то участвующем в подсчёте sha: вместо sha(value) будет или sha(concat(generation, value)) или sha(value)^generation

[(Anonymous)]

Это тоже не поможет. Мало ли откуда можно получить такую пару. Может по сети прийти.

Длинное случайное число решило бы проблему, но алгоритмически случайное число получить невозможно ;)

[(Anonymous)]

кстати, с длинным случайным числом не нужно и sha, достаточно использовать в качестве подписи само это число ;)