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

[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() нигде не гарантирует нулевую память, для этого есть calloc().

[pesec.livejournal.com]

При reuse - определённо. Но если malloc внутри себя сделает mmap (glibc), то память вернётся обнулённая.

[dmarck.livejournal.com]

А вот, кажется, фига с два. Даже mmap, если работает внутри private allocator, вполне имеет право не зацищать содержимое.

Вот ядро -- другое дело, оно обязуется не выдавать предыдущего; заметим, при этом совершенно не гарантируется, шо там нули! (блин, может, конешно, наврал в чём-то, но в POSIX NNN в ночи лазить лень совсем ;-)

[pesec.livejournal.com]

Я не знаю, что такое в данном контексте private allocator. mmap не должен выдавать мне "чужой мусор", т.к. это небезопасно. В кернеле, думаю, ситуация не настолько ограничена, и "мусор" можно получать.

http://uw714doc.sco.com/en/man/html.2/mmap.2.html

With MAP_ANONYMOUS, one can mmap zero-filled space without having a file descriptor that refers to /dev/zero.