crypto5 wrote:
Конкретно - это во сколько? В каждом блоке вероятность коллизий будет не выше какого то порога, после которого будет выделятся новый блок. Блоков будет логарифмическое количество от числа элементов. Из старых блоков элементы будут тоже удалятся.
Если элементы из старых блоков будут удаляться, то как же мы будем принимать решение, в какой конкретно блок вставить элемент?
Можно придумать много стратегий, это детали, например:
- вставлять только в последний блок и удалять опустевшие блоки
- вставлять в наиболее пустые блоки
В позицию 20 какого же из ста блоков мы будем помещать этот элемент?
100 блоков вряд ли будет, если начальный блок имеет размер 50, и каждый последующий будет в два раза больше, мы получаем 6 * 10^32 число элементов в таблице, число слабодостижимое в реальности.
crypto5 wrote:
А что именно означает отказ от ресайза? Что именно делать когда элементов стало слишком много? Какая именно имплементация хештаблицы рассматривается?
Отказ от ресайза - это не делать ничего, если элементов стало слишком много. Привязанная "еще одна" хэштаблица с последовательным поиском даст в среднем тот же результат. Если я ничего не упустил
Если углублятся то хештаблица без ресайза в среднем будет работать за 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), то и мое решение будет быстрее.
Ну вообще да, если каждый последующий блок - в 2 раза больше предыдущего, то, действительно, будет быстрее. Мое рассуждение верно только если новые блоки того же размера, что и первый. Что, очевидно, довольно глупо
crypto5 wrote:
Конкретно - это во сколько? В каждом блоке вероятность коллизий будет не выше какого то порога, после которого будет выделятся новый блок. Блоков будет логарифмическое количество от числа элементов. Из старых блоков элементы будут тоже удалятся.
Если элементы из старых блоков будут удаляться, то как же мы будем принимать решение, в какой конкретно блок вставить элемент?
Можно придумать много стратегий, это детали, например:
- вставлять только в последний блок и удалять опустевшие блоки
- вставлять в наиболее пустые блоки
В позицию 20 какого же из ста блоков мы будем помещать этот элемент?
100 блоков вряд ли будет, если начальный блок имеет размер 50, и каждый последующий будет в два раза больше, мы получаем 6 * 10^32 число элементов в таблице, число слабодостижимое в реальности.
Ну так в традиционном подходе - перекалькуляция хеша при ресайзинге памяти случится относительно небольшое кол-во раз (ну сколько там раз будет хеш таблица расти, особенно при load factor = 2), а вот потери на то, что чтение и вставка данных станет медленней - будут ощущаться при каждой операции.
crypto5 wrote:
Конкретно - это во сколько? В каждом блоке вероятность коллизий будет не выше какого то порога, после которого будет выделятся новый блок. Блоков будет логарифмическое количество от числа элементов. Из старых блоков элементы будут тоже удалятся.
Если элементы из старых блоков будут удаляться, то как же мы будем принимать решение, в какой конкретно блок вставить элемент?
Можно придумать много стратегий, это детали, например:
- вставлять только в последний блок и удалять опустевшие блоки
- вставлять в наиболее пустые блоки
В позицию 20 какого же из ста блоков мы будем помещать этот элемент?
100 блоков вряд ли будет, если начальный блок имеет размер 50, и каждый последующий будет в два раза больше, мы получаем 6 * 10^32 число элементов в таблице, число слабодостижимое в реальности.
Ну так в традиционном подходе - перекалькуляция хеша при ресайзинге памяти случится относительно небольшое кол-во раз (ну сколько там раз будет хеш таблица расти, особенно при load factor = 2), а вот потери на то, что чтение и вставка данных станет медленней - будут ощущаться при каждой операции.
Ну есть же наверное приложения, которым не допустимо что-бы программа задумалась на лишнюю секунду, пусть и раз в миллион запросов ))
Тем более очень неочевидно что сумарные потери в классическом хеше от быстрых вставок + ресайзинг будут как то меньше чем мои "медленные" вставки без ресайзинга.
crypto5 wrote:
Ну есть же наверное приложения, которым не допустимо что-бы программа задумалась на лишнюю секунду, пусть и раз в миллион запросов ))
Тем более очень неочевидно что сумарные потери в классическом хеше от быстрых вставок + ресайзинг будут как то меньше чем мои "медленные" вставки без ресайзинга.
Для такого рода приложений, которым нельзя задумываться на лишнюю секунду - уже давно придуман подход с инкрементальным ресайзингом, когда используется две хеш таблицы. При таком методе аллоцируется отдельная хеш таблица, но и старая остается. При каждом лукапе (для get или delete) поиск происходит в обеих таблицах, а вот вставка происходит только в новую таблицу и еще и во время вставки перемещается определенное кол-во элементов из старой таблицы в новую (кол-во этих элементов сами регулируете в зависимости от того, какое вам minimal latency нужно). Ну и когда элементов в старой таблице не осталось - она удаляется.
Такой подход тоже имеет место на жизнь. Его недостаток по сравнению с моим заключается в том что для каждого вставленного элемента придется вычислять хеш m раз, где m - количество resizes, а в моем случае только один раз.
fruit6 wrote:
Вы нанимаете на неоплачивамые должости?
(рука тянется к телефону.. где у нас номер для федерельного закона о минимальной оплате труда)
Вот, о чем и речь, сейчас те, кто никогда не контрибьютил в опен-сорс комьюнити, а только активно потреблял - начнут возмущаться Но ничего, подход к интервью поменяется в результате, и так уже есть сведения, что некоторые стартапы, нанимая, спрашивают про github. Если мобил - то показать свои приложения в магазине и т.п. А в результате такой подход станет мейнстримом.
Меня недавно знакомый спрашивал про участие в опенсорсе. Я честно сказал, что больше верю в доллары и в свободное от основной работы время занимаюсь халтурой на других клиентов, опенсорсу времени не остаётся...
stenking wrote:Если кандидат исповедует TTD , т.е. сразу будет страницы вики в тесты вставлять +1 к карме и так за все плюшки.
Я сам исповедую TDD
Мне на днях один Директор (+2 уровня вверх от меня) сказал дословно следующее: Уж не хочешь ли ты сказать, что мы должны внедрить TDD?
Из чего я заключил, что в среде менеджеров это чуть ли не ругательство порой...
stenking wrote:Если кандидат исповедует TTD , т.е. сразу будет страницы вики в тесты вставлять +1 к карме и так за все плюшки.
Я сам исповедую TDD
Мне на днях один Директор (+2 уровня вверх от меня) сказал дословно следующее: Уж не хочешь ли ты сказать, что мы должны внедрить TDD?
Из чего я заключил, что в среде менеджеров это чуть ли не ругательство порой...
Заключение мощное, конечно.
TDD требует намного больше дисциплины - это правда. Да и как бы и понятно, что намного интересней писать сам код, чем тесты к нему, кто бы спорил, девелоперы на разнообразное тестирование вообще криво смотрят, т.к. не царское это дело. Но и дивиденды соответствующие. А так да, как бы здорово было бы писать код, который гарантированно не ломается из-за того, что где-то чего-то поменялось или добавилось. Опять же, очень многое от задач зависит, если нужно слепить быстро прототип продукта или если под рукой всегда есть большой отряд QA, то может овчинка выделки и не стоит.
crypto5 wrote:А ТДД, это там где вначале тесты пишут, а потом код?
Ага. Ну т.е. не полностью конечно тесты для всего приложения сразу пишутся, а для определенной единицы (например, класса). Фактически при помощи тестов вначале описывается спецификация, что собственно этот класс/модуль умеет делать и какие результаты ожидаются от той или иной операции, а уже потом под него имплементируется функциональность.
crypto5 wrote:А ТДД, это там где вначале тесты пишут, а потом код?
угу, сначала трахаются, потом презерватив надевают. ведь как не потрахавшись специфицировать все сценарии использования кондома? им кажется это логичным
crypto5 wrote:А ТДД, это там где вначале тесты пишут, а потом код?
Ага. Ну т.е. не полностью конечно тесты для всего приложения сразу пишутся, а для определенной единицы (например, класса). Фактически при помощи тестов вначале описывается спецификация, что собственно этот класс/модуль умеет делать и какие результаты ожидаются от той или иной операции, а уже потом под него имплементируется функциональность.
Для меня ТДД был просто пустой концепции ей пока я не увидела ее хорошее исполнение, с тех пор нет вопроса что именно так и надо делать по уму
crypto5 wrote:А ТДД, это там где вначале тесты пишут, а потом код?
угу, сначала трахаются, потом презерватив надевают. ведь как не потрахавшись специфицировать все сценарии использования кондома? им кажется это логичным
Нет это как раз таки наоборот - сначала надевают чтобы потом не поймать чего не надо незаметно
crypto5 wrote:А ТДД, это там где вначале тесты пишут, а потом код?
Ага. Ну т.е. не полностью конечно тесты для всего приложения сразу пишутся, а для определенной единицы (например, класса). Фактически при помощи тестов вначале описывается спецификация, что собственно этот класс/модуль умеет делать и какие результаты ожидаются от той или иной операции, а уже потом под него имплементируется функциональность.
Для меня ТДД был просто пустой концепции ей пока я не увидела ее хорошее исполнение, с тех пор нет вопроса что именно так и надо делать по уму
Конечно. TDD это ведь определенная методология, со своими best practices, отлично вписывается в agile. Когда привыкаешь и получаешь определенную практику в TDD, то это превращается в очень полезный инструмент разработчика. Другое дело, что действительно нужна определенная дисциплина, чтобы вначале начинать с самой неинтересной части - с тестирования еще неготового функционала.
