Лучшие устройства хеш таблиц 2

[krlz]

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

Comments

[mr_aleph]

*facepalm*

впрочем меня это не удивляет. на третьем курсе (который для меня было всего-то 5 лет назад) людей на 3ей пересдече тервера просили нарисовать график y = sqrt(x). Угадаете, что они рисовали?

[n1919]

повернутую параболу ?

[mr_aleph]

повернутая порабола это вообщем-то не фейспалм.

они рисовали ветвь параболы y = x^2.

[dmitrits]

Неудивительно. Главное, чтобы процент таких людей на матмехе был не слишком высок. На моем первом программистском собеседовании человек (весьма уважаемый), который задавал мне вопросы, в том числе и про хеш таблицу, сам неправильно понимал обозначение O(n), путал с \Theta(n).

[krlz]

Судя по моему опыту собеседований, процент таких людей, особенно на кафедре информатики, около 90%.

[ext_8865]

Нуу определение O(f) или предела оно не так уж нужно в повседневной жизни, я второе тоже например забыл, а первое помню исключительно с целью повые^W для общего развития.

А что не так с O(n) у хэш таблицы?

[skavish]

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

[mehas]

А еще существуют хеш-таблицы с гарантированно константным get. Вроде Cuckoo и Hopscotch Hash. Вставка - амортизированно O(1).

[ext_8865]

Ето то понятно, но какбэ когда говорят "алгоритм X работает за O(f)", без уточнений (amortized там или че-то еще), обычно подразумевается как раз самый плохой случай.

[skavish]

предел настолько фундаментальная вещь что сложно представить как его можно не знать и при этом что-то понимать в математике. там же весь матан через предел определен :)

[skavish]

вот ради интереса сел сейчас и написал на бумажке определение. это при том что никогда не был каким то выдающимся математиком и окончил матмех 15 лет назад

философское

[n1919]

1) людей не учат учиться.
и не учат пониманию важности знаний.
так было даже (!) в СССР. что уж говорить про сейчас

2) у нас общество потребления
потребителям знания не нужны, даже вредны

Re: философское

[raydac]

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

Re: философское

[raydac]

ага.. все ждут что по Адаму Смиту будет, а начинается всё по Кейнсу )))