Архитектор из дома

[crypto5]

вроде ключ можно генерить который сам будет сразу знать к какому масиву он принадлежит

Не совсем понял, можно подробностей?

[АццкоМото]

Возможно последовательный поиск будет и быстрее

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

почему нельзя ресайзить в фоне, чтобы размазать увеличенную латентность во времени, но избежать резкого провала - мне и вовсе не понять

[dotcom]

при поискe можно использовать http://en.wikipedia.org/wiki/Bloom_filter, и вуаля, получаем быстрый хешмеп который линейно не тормозит при вставке.

Какой-такой Блум? Куку хэшинг - наше все!

[crypto5]

Возможно последовательный поиск будет и быстрее

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

А что именно означает отказ от ресайза? Что именно делать когда элементов стало слишком много? Какая именно имплементация хештаблицы рассматривается?

почему нельзя ресайзить в фоне, чтобы размазать увеличенную латентность во времени, но избежать резкого провала - мне и вовсе не понять

Такой вариант тоже имеет право на жизнь наверное

[crypto5]

при поискe можно использовать http://en.wikipedia.org/wiki/Bloom_filter, и вуаля, получаем быстрый хешмеп который линейно не тормозит при вставке.

Какой-такой Блум? Куку хэшинг - наше все!

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

[Интеррапт]

а предложенный подход решает проблемы быстрой вставки

Ну то, что он решает эту проблему - это еще бабка надвое сказала.

[crypto5]

а предложенный подход решает проблемы быстрой вставки

Ну то, что он решает эту проблему - это еще бабка надвое сказала.

Помоему все очень очевидно
Какие именно подводные камни видны?

[Интеррапт]

а предложенный подход решает проблемы быстрой вставки

Ну то, что он решает эту проблему - это еще бабка надвое сказала.

Помоему все очень очевидно
Какие именно подводные камни видны?

Вероятность коллизий будет намного выше, если у вас будет много небольших сегментов памяти (таблиц), вместо одного большого. И увеличится время лукапа соответственно, т.к. один и тот же ключ нужно будет просматривать не в одной таблице, а в нескольких, к тому же еще и пробегать по всем бакетам будет занимать дольше времени, т.к. коллизий больше и бакетов соответственно тоже. При чем, если резайз делается не так уж и часто, то поиск происходит намного чаще, а вот поиск похоже, что замедлится.

[vopros]

вроде ключ можно генерить который сам будет сразу знать к какому масиву он принадлежит

Не совсем понял, можно подробностей?

некая функция, которая по ключу будет выдавать target map.
причем узнавать она это будет из самого ключа, например ключ starts with 10001 - map1, 10002-map2 и тд.

[Интеррапт]

вроде ключ можно генерить который сам будет сразу знать к какому масиву он принадлежит

Не совсем понял, можно подробностей?

некая функция, которая по ключу будет выдавать target map.
причем узнавать она это будет из самого ключа, например ключ starts with 10001 - map1, 10002-map2 и тд.

Зачем такие сложности, если можно сделать просто хеш таблицу, которая в качестве записей будет содержать ссылки на другие хеш таблицы?

[vopros]

вроде ключ можно генерить который сам будет сразу знать к какому масиву он принадлежит

Не совсем понял, можно подробностей?

некая функция, которая по ключу будет выдавать target map.
причем узнавать она это будет из самого ключа, например ключ starts with 10001 - map1, 10002-map2 и тд.

Зачем такие сложности, если можно сделать просто хеш таблицу, которая в качестве записей будет содержать ссылки на другие хеш таблицы?

в точку, лень было расписывать детали функции

[crypto5]

а предложенный подход решает проблемы быстрой вставки

Ну то, что он решает эту проблему - это еще бабка надвое сказала.

Помоему все очень очевидно
Какие именно подводные камни видны?

Вероятность коллизий будет намного выше, если у вас будет много небольших сегментов памяти (таблиц), вместо одного большого. И увеличится время лукапа соответственно, т.к. один и тот же ключ нужно будет просматривать не в одной таблице, а в нескольких, к тому же еще и пробегать по всем бакетам будет занимать дольше времени, т.к. коллизий больше и бакетов соответственно тоже. При чем, если резайз делается не так уж и часто, то поиск происходит намного чаще, а вот поиск похоже, что замедлится.

Поиск безусловно замедлится, но основная цель - полностью убрать ресайзинг таблицы и получить predictable latency у апликухи, что вполне достигнуто.

[Интеррапт]

а предложенный подход решает проблемы быстрой вставки

Ну то, что он решает эту проблему - это еще бабка надвое сказала.

Помоему все очень очевидно
Какие именно подводные камни видны?

Вероятность коллизий будет намного выше, если у вас будет много небольших сегментов памяти (таблиц), вместо одного большого. И увеличится время лукапа соответственно, т.к. один и тот же ключ нужно будет просматривать не в одной таблице, а в нескольких, к тому же еще и пробегать по всем бакетам будет занимать дольше времени, т.к. коллизий больше и бакетов соответственно тоже. При чем, если резайз делается не так уж и часто, то поиск происходит намного чаще, а вот поиск похоже, что замедлится.

Поиск безусловно замедлится, но основная цель - полностью убрать ресайзинг таблицы и получить predictable latency у апликухи, что вполне достигнуто.

Насчет предиктив латенси - это вы прямо сейчас в условие добавили. А вот то, что конкретно возрастет вероятность коллизии с увеличением кол-ва блоков - так это точно. Что в большинстве случаев будет хуже чем время затраченное на ресайзинг

[Интеррапт]

а предложенный подход решает проблемы быстрой вставки

Ну то, что он решает эту проблему - это еще бабка надвое сказала.

Помоему все очень очевидно
Какие именно подводные камни видны?

Вероятность коллизий будет намного выше, если у вас будет много небольших сегментов памяти (таблиц), вместо одного большого. И увеличится время лукапа соответственно, т.к. один и тот же ключ нужно будет просматривать не в одной таблице, а в нескольких, к тому же еще и пробегать по всем бакетам будет занимать дольше времени, т.к. коллизий больше и бакетов соответственно тоже. При чем, если резайз делается не так уж и часто, то поиск происходит намного чаще, а вот поиск похоже, что замедлится.

Поиск безусловно замедлится, но основная цель - полностью убрать ресайзинг таблицы и получить predictable latency у апликухи, что вполне достигнуто.

Насчет предиктив латенси - это вы прямо сейчас в условие добавили. А вот то, что конкретно возрастет вероятность коллизии с увеличением кол-ва блоков - так это точно. Что в большинстве случаев будет хуже чем время затраченное на ресайзинг

[dotcom]

Это да. С мульти хэшовыми алгоритмами можно функции добавлять при аллоцировании новых массивов. Понятно, что оно добавляет сложность на глубину цепочки функций.

[stenking]

Вот послушал я умных людей и понял что уже старый и глупый. Комми, принимай подкрепление, будем вместе на митинги ходить )

[crypto5]

Насчет предиктив латенси - это вы прямо сейчас в условие добавили.

Условия никакого не было, поэтому добавить я туда ничего не мог, а про высокую latency при ресайзинге таблицы я упомянул в самом первом своем посте.

А вот то, что конкретно возрастет вероятность коллизии с увеличением кол-ва блоков - так это точно. Что в большинстве случаев будет хуже чем время затраченное на ресайзинг

Конкретно - это во сколько? В каждом блоке вероятность коллизий будет не выше какого то порога, после которого будет выделятся новый блок. Блоков будет логарифмическое количество от числа элементов. Из старых блоков элементы будут тоже удалятся.

[АццкоМото]

А что именно означает отказ от ресайза? Что именно делать когда элементов стало слишком много? Какая именно имплементация хештаблицы рассматривается?

Отказ от ресайза - это не делать ничего, если элементов стало слишком много. Привязанная "еще одна" хэштаблица с последовательным поиском даст в среднем тот же результат. Если я ничего не упустил

[Интеррапт]

Конкретно - это во сколько? В каждом блоке вероятность коллизий будет не выше какого то порога, после которого будет выделятся новый блок. Блоков будет логарифмическое количество от числа элементов. Из старых блоков элементы будут тоже удалятся.

Если элементы из старых блоков будут удаляться, то как же мы будем принимать решение, в какой конкретно блок вставить элемент? Вот выдала у нас хеш функция, что нужно поместить элемент в позицию 20. В позицию 20 какого же из ста блоков мы будем помещать этот элемент? В первый пустой, у которого нет бакетов? А если у первых 99 для позиции 20 уже имеются бакеты - пробегать по всем будем? Увеличится время выполнения put. Или будем засовывать только в 1-й блок? Тогда кол-во бакетов может очень сильно увеличиться, что приведет к еще большему времени лукапа. Так что пока я не особо вижу выгоды от такой хэштаблицы.

[Леонид Ильич Брежнев]

Я вот не знаю, кого можно нанять вот такой тухлятиной? Причем и написанием/разворачиванием linked lists и atoi() они имхо все одинаково тухло пахнут. Видел массу нардоу, которые просто в указателях, всяких вторых/третих волкерах и темпах тонули. Причем стоит чуть притопить себя, как дальче тебя начинает просто захлестывать волной.
Я даже не знаю, может оно спрашивать про третий параметер функции CreateWindowEx() это и не самая плохая идея идея сама по себе? Отвечать можно даже не вставая с места.
Я давеча беседовал с Gayle Laakmann, которая автор книжки про интевью "Cracking the Coding Interview", она новую книгу пишет теперь про PM-омов, так вот она упорно считает, что спрашивать такие вот вопросы это правильно. И книга у нее сoстоит из них же.

почему? интересно

Дело в том, что это все эти задачки, это задачки на запоминнание, или на знание конкретной методы, как именно это делать. И есть масса сайтов и книг, где все решения есть, ну т.е. написаны. Ну заучил человек все эти решения и что? Меня вот выше поймали на использовании for (и не использовании сравнений указателей в while) и вообще на ошибку. И о чем эта ошибка говорит? Или более сложный вопрос, о чем отсутсвие этой ошибки будет говорить, если я таки запомню это решение, или вернее не забуду, когда в след. раз буду где-то писать?
Далее идет продолжение. Си програмисты которых жизнь закинула в джаву будут довольно долго писать int len = myString.length(), что бы не дай бог не использовать myString.length() в цикле. И не то что бы они так уж и не не правы.
Будут еще вопросы от, как я их называю, радостных идиотов, которые будут тебе на интервью задавать вопросы из своего domain knowledge. Тут в ход идут уже всякие имплементации parking lots, колоды карт, лифтов, и прочая фигня, где проверяется уже даже не само программирование, а умение задавать вопросы, а сколько кард в колоде, а работает ли лот в паcxу и так далее.

Короче говоря, народ приноровился как-то отвечать на интервью, иногда по принципу на 5 заваленных интервью будет одно успешное, и получив работу радостно забывает тот бред, который он учил готовясь к интервью. Отсюда, такое количество вариантов написания reverse string. Неужели Вы думаете, если бы их кто-то писал бы каждый день, тут бы ошибки были?

Имхо, после того, как проверено базовое умение писать код, а его тут подтвердили все 100% отметившихся (верно они написали или не совсем), надо имхо переходить либо к вопросам конкретной библиотеки или фраймворка / технологии (допустим тебя берут в оптимизацию компилятора, или программирование под Андроид), либо к общим вопросам дизайна и решения конкретных задач. Но для этого имхо код не нужен, нужны желтые стики ноутс и белая доска. Особенно, если речь идет о написании распределенных приложений.

[Сабина]

Это да. С мульти хэшовыми алгоритмами можно функции добавлять при аллоцировании новых массивов.

Аллокации

[Леонид Ильич Брежнев]

....

В продолжении ....

Вот что бы далеко не ходить, наш коллега решает конкретную задачу как реализовать SSTable bulk loader для Cassandra NoSql database на С++. И чем ему все эти интервьюшные вопросы помогут?

[Albert_al]

ковбойцы на лошадях погоняют дикие стада мексиканцев

Так -вам спецов по укровищам данных не нать?

[АццкоМото]

ковбойцы на лошадях погоняют дикие стада мексиканцев

Так -вам спецов по укровищам данных не нать?

Вы же наверняка не поедете в ТХ?
Спецы по дазам банных, на удивление, сейчас нужны только с точки зрения разработки (девелопер или архитект), но там кроме БД много чего еще нужно, всякие вебсервисы, С++, жаба и далее по списку. Детали в личку надо?

[crypto5]

А что именно означает отказ от ресайза? Что именно делать когда элементов стало слишком много? Какая именно имплементация хештаблицы рассматривается?

Отказ от ресайза - это не делать ничего, если элементов стало слишком много. Привязанная "еще одна" хэштаблица с последовательным поиском даст в среднем тот же результат. Если я ничего не упустил

Если углублятся то хештаблица без ресайза в среднем будет работать за O(n/initial_capacity) = O(n) операций, потому что она фактически будет initial_capacity связных списков.

В моем случае у каждого блока количество коллизий ограничено некоторым параметром, т.е. каждый блок будет давать не больше чем colision_treshold колизий, и этот порог - константа, блоков будет некоторая f(n), где f я ленюсь посчитать, но f будет далеко не линейной, а скорее логарифмической, если каждый следующий блок будет в два раза больше предыдущего.
Общая сложность будет O(colision_threshold * f(n)) = O(f(n)), поскольку f(n) быстрее чем O(n), то и мое решение будет быстрее.