06.11.2013 10:22, avpavlov пишет:
> получается О(1). При этом, естественно, всегда стоит упомянуть, что это > при наличии хорошей хэш-функции, а при плохой хэш-функции можем просесть > вплоть до худшего случая — О(n).
Как говориться, главное как продать (тьфю подать). Итого O(1) или в
промежутке от O(1) до O(n) в зависимости от много.
V>Как говориться, главное как продать (тьфю подать). Итого O(1) или в V>промежутке от O(1) до O(n) в зависимости от много.
Во многих случаях ключи известны заранее, можно проверить хэш-фунцию. В остальных случаях можно собирать статистику, так что проблема внезапного перехода от О(1) к О(n) надумана
Здравствуйте, avpavlov, Вы писали:
A>Ну, давай, покажи, как размер ключа зависит от размера коллекции, а то какой-то пустопорожний спор получается.
Количество коллизий зависит от размера коллекции и длины ключа. Соответственно для больших коллекций нужны более длинные ключи. Как ты будешь делать ресайзинг с ростом коллекции без изменения размера ключа?
Здравствуйте, AlexMld, Вы писали:
AM>Количество коллизий зависит от размера коллекции и длины ключа. Соответственно для больших коллекций нужны более длинные ключи. Как ты будешь делать ресайзинг с ростом коллекции без изменения размера ключа?
Блин, не так выразился. Это я про размер значения хеш-функции, который тоже растет.
А с ключами — Ключи должны быть уникальными? Значит, чем больше коллекция, тем длиннее нужны ключи. Длина уникального ключа должна быть минимум log от размера коллекции.
06.11.2013 11:29, avpavlov пишет:
> Во многих случаях ключи известны заранее, можно проверить хэш-фунцию.
Корректнее сказать, в тех случаях, где хеш-функции уже придуманы. А
много это или мало, зависит от области применения.
> В > остальных случаях можно собирать статистику, так что проблема внезапного > перехода от О(1) к О(n) надумана
Перешли в область верований?
З.Ы. Но, я уже понял, с хешами это новая дурь на собеседованиях (до
этого были i+++++++++i, затем виртуальные деструкторы с конструкторами,
теперь это).
Я раньше не решал эту задачу. У меня спросили точную цифру, вывести совсем было не сложно — воспользовался отрицанием событий. Но довести до конкретного числа я уже в одиночку не смог
Здравствуйте, AlexMld, Вы писали:
AM>Здравствуйте, Vzhyk, Вы писали:
V>>Да, к чему это я привел, что если не знаете что это, фиг даже за V>>несколько лет сами сделаете. V>>Так и с задачей на дни рождения, если есть несколько дней поразмышлять V>>над ней и это будет оплачено, то ее решить можно, но на собеседовании за V>>15 мин, только вспомнить, если читал пару дней назад. V>>Бред, что они этими тестами проверяют, что кандидат получил инсайдерскую V>>инфу о вопросах на собеседовании или то, что случайно пару дней назад V>>прочитал от нефиг делать.
AM>Хешмапы — самые быстрые структуры для поиска информации, поэтому все Гуглы/Бинги на них повернуты. Меня Гугл пытал с одной задачей, бинарный поиск их по скорости не устраивал, не успокоились, пока я на хешмап ее не переделал. Так что коллизии — это один из популярных вопросов. Не обязательно помнить точно, но вывести надо уметь.
Здравствуйте, dilmah, Вы писали:
D>O(1) это условность. Я бы настороженно относился к индивидам которые бездумно делают выводы о быстроте из этого O(1).
+1. Нотацию O придумали математики, информатики украли у математиков, программисты у математиков. Я понимаю, что у бедных информатиков нету ничего круче Тьюринговой машины, но (блин) у программистов имеется профайлеры, и меня удивляют программисты, которые смело говорят про O, да еще и гордятся
Здравствуйте, AlexMld, Вы писали:
AM>Здравствуйте, AlexMld, Вы писали:
AM>>Количество коллизий зависит от размера коллекции и длины ключа. Соответственно для больших коллекций нужны более длинные ключи. Как ты будешь делать ресайзинг с ростом коллекции без изменения размера ключа?
AM>Блин, не так выразился. Это я про размер значения хеш-функции, который тоже растет.
Я, думаю, что ты опять не так выразился Значение хэш-функции — это номер цепочки/bucket'а
Никуда это значение не растёт, оно просто всегда равно одному из доступных номеров
Вот число доступных корзин может меняться, если хэш-таблица достаточно умная и подстраивается под размер коллекции для уменьшения числа коллизий. Но это зависит от имплементации и не имеет никакого отношения к обсуждению абстрактной хэш-тбалицы и её О-нотации.
AM>А с ключами — Ключи должны быть уникальными? Значит, чем больше коллекция, тем длиннее нужны ключи.
Длина ключа не зависит от размеров коллекции. Длина ключа вообше не имеет отношение к хэш таблицам. Бывают маленькие коллекции с большими ключами, бывают большие коллекции с маленькими ключами.
AM>Длина уникального ключа должна быть минимум log от размера коллекции.
Коллекция на 4 млрд 32х битных интов прекрасно мэппится на 4байтные ключи. Расскажи, где ты здесь видишь "минимум лог от размера коллекции"?
06.11.2013 13:32, kashtan пишет:
> но (блин) у программистов имеется > профайлеры, и меня удивляют программисты, которые смело говорят про O, > да еще и гордятся
Это сейчас основной критерий отбора сильных программистов. И неважно,
что эта нотация означает, главное O(1) это круто O(n^n) это фуууууууу.
Здравствуйте, avpavlov, Вы писали:
AM>>Блин, не так выразился. Это я про размер значения хеш-функции, который тоже растет.
A>Я, думаю, что ты опять не так выразился Значение хэш-функции — это номер цепочки/bucket'а A>Никуда это значение не растёт, оно просто всегда равно одному из доступных номеров
Не значение растет, а его размер, т.е. диапазон. Значение хэш-функции — это типа индекса для массива. Чем больше массив, тем больший диапазон индексов тебе нужен. Скажем, байтом ты можешь адресовать 256 bucket'ов, а двумя байтами — 65536
A>Длина ключа не зависит от размеров коллекции. Длина ключа вообше не имеет отношение к хэш таблицам. Бывают маленькие коллекции с большими ключами, бывают большие коллекции с маленькими ключами.
Большие коллекции с маленькими _уникальными_ ключами? Это как?
AM>>Длина уникального ключа должна быть минимум log от размера коллекции.
A>Коллекция на 4 млрд 32х битных интов прекрасно мэппится на 4байтные ключи. Расскажи, где ты здесь видишь "минимум лог от размера коллекции"?
05.11.2013 21:17, Vzhyk пишет:
> Да, к чему это я привел, что если не знаете что это, фиг даже за > несколько лет сами сделаете.
Так что с этой задачкей по ТВ?
