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

[avva]

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

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

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

Comments

[zhengxi.livejournal.com]

Дык, хеш-таблица (std::unordered_map в C++) + хранение default
Как раз O(1) для set и get

[avva.livejournal.com]

хеш-таблица дает O(1) только в среднем, а требуется жесткий предел в худшем случае.

[alexeybobkov]

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

[avva.livejournal.com]

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

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

[sascha (from livejournal.com)]

Но при этом разрешается использовать сколько угодно памяти? :-)
Если да, то я умею, буквально пару недель назад пришлось изобрести, чтобы не состариться за время инициализации :))

[avva.livejournal.com]

Сколько угодно памяти, но всю ее можно приводить в нужный вид лишь за O(1) времени.

[kosiakk.livejournal.com]

если массив фиксированной длины и c цифровыми индексами, это не так и сложно.

для хранения выделяется непрерывный участок виртуальной памяти - обычный массив в С++

плюс дополнительный "индексный" массив uint'ов длины array_length / sizeof(int) / 8 + 1 - т.е. по одному биту на элемент массива.

его придётся заполнить нулями, но эта операция в 32-64 раза быстрее чем заполнение нулями основного массива, которое в данном случае не потребуется

ну а дальше просто - по битовой маске и содержимому индексного массива понимаем были ли там пользовательские данные, и если нет - возвращаем текущее default-значение. Очевидно, set должен взводить бит соответствующей ячейки:

index[ i \ sizeof(int) ] & ( 1 << (i % sizeof(int)) )

[avva.livejournal.com]

С практической точки зрения это может и рещает проблему, но "в 32-64 раза быстрее" чем O(n), это все еще O(n). А нужно именно O(1).

[avva.livejournal.com]

Да, все верно, это более или менее каноническое решение этой задачи :) Я заскриню его на время.

[poteshnaya.livejournal.com]

Можно разъяснение по прошлой.
Что-то я не догоняю.
Смотрю питоновый код.
берем входящие данные 1123

Идем по коду

def finddup(arr):
i = len(arr) - 1 # last //i=3
looplen = 0
while looplen < n:
i = arr[i] //i = arr[3] = 3
looplen += 1

if arr[i] == i: //3 == 3
# no loop, fixed point
return i //Ответ = 3

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

[dmage-ru.livejournal.com]

Этот код чуть-чуть под другие условия (для удобства): массив содержит числа не от 1 до N-1, а от 0 до N-2.

Т.е. входящие данные должны быть 0012

[mixa.livejournal.com]

Пусть будет два массива, main[] в котором собственно значения, и вспомогательный aux[], и еще две переменных -- lastDef и defCounter.

При вызове setdefault(value) делаем lastDef = value и defCounter++.

При вызове set(i, value) в main[i] записываем value, а в aux[i] -- defCouner.

Смысл aux[i] -- "после aux[i] по счёту вызова setdefault() значение main[i] изменилось"

На вызов get(i) сначала сверям текущий defCounter и aux[i]. Если defCounter > aux[i], возвращаем lastDef (после последнего обновления дефолтного значения main[i] не менялся), если defCounter == aux[i], возвращаем main[i]

[mixa.livejournal.com]

Один раз однако aux[] надо будет нулями забить, это O(N), но на инициализацию ограничения не было.

[avva.livejournal.com]

Да, все верно, это решает проблему.

[avva.livejournal.com]

Не, не работает. В indexes и values случайно вместе может оказаться "неправильный" мусор, который приведет к неправильному чтению.

[yigal_s]

тяжело поверить, что это можно написать :-)

[avva.livejournal.com]

Можно! :)

[avva.livejournal.com]

Да, все верно :)

[avva.livejournal.com]

примерно так, хотя для set следует быть более экономным и делать reuse уже имеющегося слота.

[pesec.livejournal.com]

Дополнение к програмистской задаче: в каких средах может иметь место выделение памяти со случайными (неинициализированными) данными?.. Кажись, POSIX такое запрещает из-за вопросов безопасности, или я бегу впереди паровоза?

[avva.livejournal.com]

по-моему, malloc() нигде не гарантирует нулевую память, для этого есть calloc().

[avva.livejournal.com]

все верно, да. Скрою пока ваше решение.

[(Anonymous)]

Можно вести некоторый "лог изменений", в который при каждой операции записывается номер ячейки и её новое значение. В самом массиве хранить указатель на последнюю запись в логе (например, её номер, чтобы memory access violation на мусорном указателе не получить).

[nine_k]

Про массив с дефолтным значением тривиально решить битмэпом, потратив не более N/8+1 памяти (или меньше, если элементы крупнее байта).

Но это как-то слишком просто!

[avva.livejournal.com]

Это требует О(N) времени для инициализации битмэпа, а нужно O(1) для всего.

[neatfires.livejournal.com]

Кажется, я это тоже когда-то видел. Отличная задача, хоть и бесполезная на практике.

Что-нибудь такое?

[panikowsky.livejournal.com]

# будем учитывать все вызовы setval(), которые устанавливают значение для 
# какого-то индекса впервые

counter=0   # количество вызовов setval(), впервые установивших значение для какого-либо индекса 
set_at=[]   # для данного индекса i, set_at[i] == порядковому номеру вызова setval()
iset_is=[]  # для данного n - номера вызова setval(), iset_is[n] == индексу, для которого
            # установлено значение
defval=0
size=1000
values=[]  

for i in range(size):   # имитация случайной памяти 
	values.append(random.randint(1,10000))
	set_at.append(random.randint(1,10000))
	iset_is.append(random.randint(1,10000))

def setdefval(x):
	global defval
	defval=x

def setval(i,val):
	global iset_is, set_at, counter, values
	set_no=iset_is[i]
	if (set_no>=counter or set_at[set_no]<>i):
		iset_is[i]=counter
		set_at[counter]=i
		counter = counter + 1
	values[i]=val

		
def get(i):
	global iset_is, set_at, counter, values
	set_no=iset_is[i]
	if (set_no>=counter or set_at[set_no]<>i):
		return defval
	else:
		return values[i]

Re: Что-нибудь такое?

[neatfires.livejournal.com]

iset_is[i] может быть отрицательным, кроме этого - верно

[schurschur.livejournal.com]

int *data = malloc(1000);
int *aux1 = malloc(1000);
int *aux2 = malloc(1000);

int default = 0;
int counter = 0;

int get( int i )
{
if( counter >= 1000 )
return data[i];
if( i < counter && aux1[aux2[i]]!=i )
return default;
if( i >= counter )
return default;
return data[i];
}

void set( int i, int value )
{
data[i] = value;
if( counter >= 1000 )
return;
if( i >= counter ||
aux1[aux2[i]] != i )
{
aux1[counter] = i;
aux2[i] = counter;
++counter;
}
}

Как-то так, мне кажется :)

[(Anonymous)]

Точно помню, что где-то встречал что-то очень похожее, но не помню что.

Попробуем так:
X[i] содержит значения.
default_x - значение по умолчанию.
Y[i] содержит "время" первой записи в X[i]. Эти "времена" представляют собой числа от 0 до максимально возможного i.
Z[t] содержит номер элемента, который был записан в момент времени t (t - от 0 до max_i).
max_t - содержит масимальное "время" на текущий момент.

init(): default_x = 0; max_t = 0;

setdefault(v): default_x = v;

is_set(i): return (Y[i] < max_t) && (Z[Y[i]] == i)

set(i, v): if (!is_set(i)) { Y[i]=max_t; Z[max_t++]=i; } X[i]=v;

get(i) if (is_set(i)) return X[i]; else return default_x;

Хотя мне почему-то кажется, что там, где я эту задачу встречал раньше, она решалась не с двумя, а с одним доп. массивом.

[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]

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

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

Но ведь для того что бы что-то сделать с числом порядка N нужно порядка log(N) операций? Для массива на N = терабайт это будет не то же самое O(1) что для массива на килобайт?

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

Выделяем большой промежуток виртуальное пространство, но не выделяем физическую память. При каждом обращении к страничке будет исключение от операционной системы (SEH в windows, signal в unix afaik). В момент исключения - обнуляем страничку и разрешаем чтение/запись из неё.

Делаем вид, что не знаем про TLB (http://en.wikipedia.org/wiki/Translation_lookaside_buffer).

TLB для битовых флажокв dirty/read-write можно сделать руками, иерархичный. Тут уже несколько раз предлагали сделать битовый массив инициализации. Можно сделать битовый массив инициализированности для битового массива, затем битовый массив для битового массива инициализированности битового массива и тд. Один бит может соответствовать как раз размеру странички. Трёх-четырёх слоёв хватит для практических целей ( четыре слоя - это 4096⁴ = 2⁴⁸ ).

Ещё можно в стек (реализованный как динамический массив типа std::vector<size_t> vec с capacity = N или std::deque) заносить уже инициализированные индексы массива array[i]. Что бы за (типа как бы) O(1) количества операций проверить есть ли индекс i в стеке - дополнительный массив index_at_vec[i] -> индекс в стеке. Если на месте index_at_vec[i] мусор из-за которого vec[index_at_vec[i]] не равно i ( или OutOfRange для vec ) - значит значение array[i] не инициализировано

[alexeybobkov]

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

Второе решение - та же инициализация за O(N), только размазанная во времени.

Третье решение правильное.

[migmit.livejournal.com]

Если можно считать размер массива известным заранее, то так как-то:

int values[10000];
int wasSet[10000];
int indices[10000];
int defaultValue;
int setCount = 0;
void setDefault(int value) {defaultValue = value;}
int get(int i) {
if (i < 0 || i >= 10000) return defaultValue;
int setIndex = wasSet[i];
if (setIndex < 0 || setIndex >= setCount) return defaultValue;
if (indices[setIndex] != i) return defaultValue;
return values[i];
}
void set(int i, int value) {
if (i < 0 || i >= 10000) return;
values[i] = value;
int setIndex = wasSet[i];
if (setIndex >= 0 && setIndex < setCount && indices[setIndex] == i) return;
wasSet[i] = setCount;
indices[setCount] = i;
setCount++;
}


[migmit.livejournal.com]

Блин, отступы съелись к чёрту.