?

Log in

No account? Create an account
   Journal    Friends    Archive    Profile    Memories
 

Задачка - morfizm


Nov. 2nd, 2018 07:31 pm Задачка

Столкнулся с красивой задачкой на работе.
* Объекты можно хэшировать в K buckets.
* Сгенерировать минимальное число объектов, хэши которых покрывают все K buckets для каждого 1 <= K <= N.
* Сколько получается объектов для N = 100? Для N = 200?

Про хэшфункцию заранее ничего неизвестно, кроме того, что она равномерная.
Можно решить задачу двумя вариантами - в одном известно, что хэшфункция имеет вид hash(d) % K, а в другом она совершенно произвольная (и может быть принципиально разной для разных значений K).

42 comments - Leave a commentPrevious Entry Share Next Entry

Comments:

From:archaicos
Date:November 3rd, 2018 02:59 am (UTC)
(Link)

What’s N? Пиши подробней.

From:morfizm
Date:November 3rd, 2018 08:52 am (UTC)
(Link)
N это input.
From:birdwatcher
Date:November 3rd, 2018 03:04 am (UTC)
(Link)
Непонятное условие. Для разумной хеш-функции минимальное количество объектов, покрывающее K buckets, равно K, но непонятно, как их генерировать. Для безумной фунцкии (например, hash(d) ≡ 0) никакого количества объектов не хватит.
P.S. пропустил слово равномерная. Это значит, что в каждую из N buckets попадает строго одинаковое количество объектов данного типа? Есть ли у нас способ перечислить все объекты, начиная с некоторого первого?

Edited at 2018-11-03 03:22 am (UTC)
From:mrumka
Date:November 3rd, 2018 05:19 am (UTC)
(Link)

А как же разруливать hash коллизии?

From:mrumka
Date:November 3rd, 2018 05:17 am (UTC)
(Link)

Посмотри последнюю реализацию HashMap в Java. Там народ делает rehash в определенных случаях. Вдруг тебе подойдет.

From:victorbarinov
Date:November 3rd, 2018 05:26 am (UTC)
(Link)
> покрывают все K buckets для каждого 1 <= K <= N.
Эта часть не очень понятна.

Простая задача: сколько надо объектов, чтобы множество их хешей покрывало все K бакетов? -- Ответ: примерно K log K
Сложная задача: сколько надо объектов, чтобы множество хешей было полным для каждго К, где K=1, K=2, ..., K=N. Как решить пока не знаю, но ответ кажется где-то в [K log K + 1, 2 * K log K]. У меня есть идея решения, но она сложная и за разумное время я смогу рассчитать только для N<=9.

Ты знаешь как решить сложную задачу?
From:morfizm
Date:November 3rd, 2018 09:01 am (UTC)
(Link)
В твоей интерпретации задачи тебе допускается брать (случайные) объекты и нельзя их выкидывать. Представь себе, что можно, и подсчитываем только количество оставшихся (выбранных) объектов. Ну т.е. в простой задаче ответ ровно K. Сколько в сложной?

Я не знаю, как решить сложную, но у меня есть неплохие эвристики с конкретными числами.
From:spamsink
Date:November 3rd, 2018 07:15 am (UTC)
(Link)
При совершенно равномерной функции имеем:

Вероятность, что 1 объект покроет 1 бакет - 1.
Вероятность, что 2 объекта покроют 2 бакета - (k-1)/k
Вероятность, что 3 объекта покроют 3 бакета - (k-1)/k * (k-2)/k
...
Какую вероятность хочется получить?

При К, не равном степени двойки, hash(d) % K не совсем равномерная, и при желании это можно учесть, но разница будет невелика.
From:morfizm
Date:November 3rd, 2018 09:02 am (UTC)
(Link)
Хочется получить вероятность 100%, но объекты, которые не подошли, можно выкинуть. Оставляем только годные.
From:freeborn
Date:November 4th, 2018 04:25 am (UTC)
(Link)
Антипарадокс дней рождения - сколько людей набрать, чтобы за именинника выпить можно было каждый день? )
From:morfizm
Date:November 4th, 2018 04:31 am (UTC)
(Link)
Вы тоже неправильно поняли задачу. Если сгенерированные объекты не покрывают дополнительные хэши, то их можно выкинуть и сгенерировать новых.
From:morfizm
Date:November 4th, 2018 04:57 am (UTC)
(Link)
Нет, не оно.
From:freeborn
Date:November 4th, 2018 08:22 am (UTC)
(Link)
Я туплю, или покрытие всех бакетов для к=н означает и покрытие для всех меньших к? Для модуля, естественно?
From:morfizm
Date:November 4th, 2018 08:58 am (UTC)
(Link)
Да. Но советую таки почитать другие комменты - я там, во-первых, уточняю варианты формулировки задачи, во-вторых, там уже озвучено доказательство оптимального решения. Осталась практическая часть - найти достаточно хорошее решение за разумное время.