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

[avva]

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

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

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

Comments

[ilya-dogolazky.livejournal.com]

Частным случаем этой задачки является задачка представления подмножества множества [1..N] для небольших N (небольших потому, что требуется линейная по N память) с опрерациями "добавить элемент" и "узнать входит ли элемент" (начинается всё с пустого подмножества). Сведение выглядит так --- функция set всегда вызывается со вторым параметром 1, а функция setdefault не вызывается никогда. При значении N=256 получается забавное приложение -- можно реализовать функцию стандартной библиотеки strpbrk: сначала "добавить" все элементы множества, заданного вторым параметром, а затем проверить элементы множества, заданного первым параметром.

А вот как эта функция реализована на самом деле (http://sourceware.org/git/?p=glibc.git;a=blob;f=string/strpbrk.c;h=620cfab7f9616ef45e7e059481f2f5232ae27e1e;hb=16c2895feabae0962e0eba2b9164c6a83014bfe4#l30). Ой.

[neatfires.livejournal.com]

хехе, прикольно

[(Anonymous)]

На самом деле так и надо ее реализовывать, потому что в большинстве случаев второй параметр — строка из 2—3, много 5 символов. В исходниках, которые случайно завалялись на моем компьютере, это так. Я бы посчитал по более массивной выборке, но скачивать для этого много исходников неохота, а как заставить гугель искать не определения, а вызовы, я не знаю.

Может быть, хитрая реализация и позволит получить какой-то небольшой выигрыш в скорости, но для этого придется как-то выделять 512 байт, а как? Из кучи слишком медленно. Для стека это нетривиальный размер. TLS? Э... нет, лучше уж наивная n*m реализация.

[ilya-dogolazky.livejournal.com]

да ничего, стек не обеднеет от полкилобайта. а если "наивно" реализовывать, тогда уж с битовой маской на 32 байта -- для инициализации там нужно всего-то 8 инструкций.

[(Anonymous)]

«стек не обеднеет от полкилобайта»

Полкилобайта тут, полкилобайта там, а контроллеры с пятью ножками и полутора регистрами кто поддерживать будет? Шутка.

«с битовой маской на 32 байта»

Я не уверен, что это оправдано в смысле производительности. Надо как-нибудь измерить на досуге.

На самом деле не в этом даже дело. Я нашел-таки в гугле вызовы strpbrk. В большинстве случаев там действительно несколько символов, редко — десяток, но это практически всегда константа, и чаще всего литерал. То есть там нужна битовая маска на 32 байта, которая заполняется один раз (возможно, во время компиляции) и больше не трогается. Можно и на 256 байт, и использовать разные ее биты для разных вызовов strpbrk, по типу функций/макросов «is*()» из ctype.h. Это точно будет быстрее всего.