?

Log in

No account? Create an account

Задачка по арифметике - Ваши рубидии уже у кобальта во ртути

Apr. 24th, 2013

11:42 pm - Задачка по арифметике

Previous Entry Share Next Entry



Дано: Реализация хеш-таблицы, первоначально написанная для 32-битной архитектуры (значения размера таблицы и количества элементов в ней - 32-битные целые без знака), но в данный момент работающая на 64-битной с неограниченным в целях задачи объемом памяти. Масштабирование таблицы путем увеличения ее размера вдвое делается при вставке очередного элемента в том случае, если таблица уже заполнена на 80% или больше.
При создании таблицы ее начальный размер - 1024. При попытке удвоения размера таблицы при ее текущем размере 231 фиксируется (или возникает) ошибка.

Вопрос: Сколько элементов удастся вставить в таблицу, прежде чем произойдет ошибка?

Примечание: Если вам кажется, что в условии не хватает данных, сделайте реалистичное или пессимистичное предположение.

Comments:

From:rezkiy
Date:April 25th, 2013 07:36 am (UTC)
(Link)
Будем считать, что при коллиженах мы не мудрствуем лукаво, а пишем в бакет для данного значения.
Будем считать, что 80% -- это количество занятых бакетов.
будем считать, что хеш-функция хорошая.

Кажется, дофига. Потому что когда мы допустим заняли половину хеш-таблицы, вставление новой записи будет добавлять бакет с вероятностью поменьше половинки, и чем дальше, тем меньше.
(Reply) (Thread)
From:rezkiy
Date:April 25th, 2013 08:48 am (UTC)
(Link)
http://www.wolframalpha.com/input/?i=sum%281%2F%281+-+n%2F2%5E31%29%2C+n%3D1%2C+n%3D1717986918%29

чуть меньше трех с половиной миллиардов, в рамках разумного.

Под суммой то, сколько значений надо засунуть в хеш, чтобы он добавил бакет
(Reply) (Parent) (Thread)
[User Picture]
From:archaicos
Date:April 25th, 2013 09:17 am (UTC)
(Link)
Хм... А как именно ~3*109 элементов помещаются в таблице из ~2*109 байт?
(Reply) (Parent) (Thread)
From:rezkiy
Date:April 25th, 2013 10:58 am (UTC)
(Link)
В таблице не 2 миллиарда байтов, а два миллиарда хеш бакетов.
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:spamsink
Date:April 25th, 2013 02:50 pm (UTC)
(Link)
Будем считать, что 80% -- это количество занятых бакетов.

Это странное предположение, дающее очень оптимистичный результат. Кроме того, бывают и таблицы с открытой адресацией.
(Reply) (Parent) (Thread)
From:rezkiy
Date:April 25th, 2013 10:31 pm (UTC)
(Link)
бывают. А бывают и другие, с цепочками.
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:archaicos
Date:April 25th, 2013 08:14 am (UTC)
(Link)
Если предположить, что это хеш таблица с открытой адресацией, то 80% от 231 байт - это 1717986918 байт занятых элементами. В этом случае можно вставить около (1717986918 / размер элемента (пары ключ + значение) в байтах) элементов. Если элементы восьмибайтные, то 200 с чем-то миллионов можно вставить.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:April 25th, 2013 02:39 pm (UTC)
(Link)
Память, считай, неограниченная. Не хватает данных не там.

Ответ, тем не менее, забавным образом близок к ожидаемому.

Edited at 2013-04-25 02:56 pm (UTC)
(Reply) (Parent) (Thread)
[User Picture]
From:archaicos
Date:April 25th, 2013 03:00 pm (UTC)
(Link)
Если таки поменяли размеры на 64-битные, то на текущем железе облом может наступить на размере порядка 240 с чем-то, т.к. процессоры поддерживают 48-битные физические адреса, т.е. больше ОЗУ нельзя будет отобразить в адресное пространство (в принципе, виртуальная дисковая память должна помочь, но не уверен, что она не ограничивается тем же).

UPD: ещё возможна фрагментация адресного пространства. Она может ограничить рост непрерывной таблицы даже если физической памяти навалом.

Наверное я не в том направлении думаю.


Edited at 2013-04-25 03:04 pm (UTC)
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:April 25th, 2013 03:19 pm (UTC)
(Link)
Не в том. Задачка чисто арифметическая. В идеале, облом наступит на 2^31*0.8+1-м элементе: в этот момент размер таблицы попытается удвоиться (а 2^32 в 32-битное целое не помещается), и произойдет ошибка. А не в идеале?
(Reply) (Parent) (Thread) (Expand)
From:rezkiy
Date:April 25th, 2013 10:32 pm (UTC)
(Link)
чтобы зафрагментировать 64-битное адресное пространство, надо постараться немало.
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:fatoff
Date:April 25th, 2013 02:11 pm (UTC)
(Link)
(2 ^ 31) * 0.8 ?

Понял, в чём подвох, коллизии и списки с элементами, ломившимися в одну дверь. Здесь задача повыше арифметики.

Ну а про 64-битную архитектуру написано для внесения в условие задачи интриги?

Edited at 2013-04-25 02:13 pm (UTC)
(Reply) (Thread)
[User Picture]
From:spamsink
Date:April 25th, 2013 02:40 pm (UTC)
(Link)
Нет, подвох не в этом. Память, в рамках задачи, считается неограниченной - для этого и сказано про 64-битную архитектуру.
(Reply) (Parent) (Thread)
[User Picture]
From:fatoff
Date:April 25th, 2013 02:42 pm (UTC)
(Link)
Ну, то есть, таблица failed to grow. Сколько всего навставляли значений, зависит от средней длины цепочки коллизий при такой заполняемости таблицы.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:April 25th, 2013 02:54 pm (UTC)
(Link)
Ну, то есть, таблица failed to grow.

Почему сделан такой вывод? Заполненность таблицы считается как отношение количества элементов к размеру и не зависит от способа адресации.
(Reply) (Parent) (Thread) (Expand)