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

[avva]

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

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

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

Comments

[alexeybobkov]

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

[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, достаточно использовать в качестве подписи само это число ;)