Комментарии 18
Вода какая-то.
> Эффективнее всего хранит и извлекает данные таблица хэшей. Если ее использовать, анализировать предложение двадцать шесть раз не придется – хватит и одного.
С деревом тоже 1 проход. И дерево будет эффективнее хэша, потому что получение хэша для одной буквы будет медленнее, чем испоьзование этой самой буквы.
Если только Латинские буквы, то и с массивом один проход будет.
С деревом тоже 1 проход. И дерево будет эффективнее хэша, потому что получение хэша для одной буквы будет медленнее, чем испоьзование этой самой буквы.
Если только Латинские буквы, то и с массивом один проход будет.
Да если и не латинские тоже. Двухбайтовый код буквы вполне ложится на массив как индекс, при условии что у нас достаточно памяти (совсем не запредельно много). Хеши имеют смысл тогда, когда исходный ключ — произвольная длинная строка, а если мы подсчитываем буквы — это далеко не лучшее решение.
Ну да, если юникод, то можно и 64К элемента массив использовать. А вот если мультибайт и какой-нибудь диалект китайского, который занимает больше двух байт, то с массивом могут возникнуть «неудбства» :)
>Ну, например, перед вами стоит задача:
>Дано предложение, рассчитайте, сколько раз в нем появляется каждая из букв алфавита.
Ну вот же исходная задача. Тут не написано, какого размера алфавит ) А мы как-бы не в Китае сейчас. Так что автор отступает от своего же совета сразу уточнить задачу, и уже сделал вывод, что лучше всего хеш. А выходит что нифига — зависит от.
P.S. Строго говоря, машинки с терабайтом памяти тоже уже не какое-то невиданное чудо. Так что параметры железки тоже можно уточнить.
>Дано предложение, рассчитайте, сколько раз в нем появляется каждая из букв алфавита.
Ну вот же исходная задача. Тут не написано, какого размера алфавит ) А мы как-бы не в Китае сейчас. Так что автор отступает от своего же совета сразу уточнить задачу, и уже сделал вывод, что лучше всего хеш. А выходит что нифига — зависит от.
P.S. Строго говоря, машинки с терабайтом памяти тоже уже не какое-то невиданное чудо. Так что параметры железки тоже можно уточнить.
— Обоснуйте необходимость покупки сервера с терабайтом оперативной памяти?
— Мне тут надо посчитать, сколько раз буквы в предложении встречаются…
%)
P.S. А ещё собеседование может происходит в какой-ибудь Китайской. Короче, мы оба согласны, что заявление автора про «Эффективнее всего» было преждевременным.
— Мне тут надо посчитать, сколько раз буквы в предложении встречаются…
%)
P.S. А ещё собеседование может происходит в какой-ибудь Китайской. Короче, мы оба согласны, что заявление автора про «Эффективнее всего» было преждевременным.
дело не в том, сколько памяти используется, а в том, что будет тяжело выделить массив такого размера уже даже по времени и быстрее будет работать с хэшами
Ну, вопрос в том, какого «такого» размера. И автор его даже не попытался решить, а сразу сделал вывод, что хеш функции лучше.
ну там речь шла о терабайтах
>Дано предложение, рассчитайте, сколько раз в нем появляется каждая из букв алфавита.
Где тут про терабайты?
Где тут про терабайты?
P.S. Строго говоря, машинки с терабайтом памяти тоже уже не какое-то невиданное чудо. Так что параметры железки тоже можно уточнить.
P.S. А ещё собеседование может происходит в какой-ибудь Китайской. Короче, мы оба согласны, что заявление автора про «Эффективнее всего» было преждевременным.
я же написал в ответ к этим записям
Из того, что машинки с терабайтом существуют, не следует, что нам нужен терабайт. Я лишь имел в виду, что если надо, то он у нас есть, и мы можем алгоритмы строить в расчете на него.
Размер структуры для подсчета частоты букв в тексте не зависит от размеров текста, а только от размеров словаря языка. И даже для четырехбайтовой кодировки это будет всего-то порядка десятков гигабайт, если я нигде не ошибся. А столько даже на ноуте можно найти.
А массив такого размера будет быстрее хеш таблицы просто всегда.
Размер структуры для подсчета частоты букв в тексте не зависит от размеров текста, а только от размеров словаря языка. И даже для четырехбайтовой кодировки это будет всего-то порядка десятков гигабайт, если я нигде не ошибся. А столько даже на ноуте можно найти.
А массив такого размера будет быстрее хеш таблицы просто всегда.
Если мы начинаем говорить о юникоде, то сразу возникает множество проблем. Например, нормализация: считать ли букву ё как один символ и букву ё как комбинацию е и диакритики одним и тем же символом? Если мы хотим считать вместе прописные и строчные, то возникает проблема задания локали. В общем, задача не такая простая, как кажется. :)
Ну это все правда, только это другие аспекты. И да, они очень важные — но при этом к выбору хеш таблиц как структуры для хранения результата, о которой говорит автор, они вообще отношения не имеют, на первый взгляд.
Причём, эта проблема будет при любом варианте реализации.
Повело рекрутеру, что мы на собеседование не пришли, а то своими уточняющими вопросами задолбали…
Повело рекрутеру, что мы на собеседование не пришли, а то своими уточняющими вопросами задолбали…
Все таки N*log(K) > N. Даже если K = 26. Более того с BST будут постоянные сбросы кэшей.
И после всех таких офигительных интервью оказывается что пароли клиентов тупо хранятся в открытом виде в текстовых файлах.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Советы для кандидатов от программиста, проводящего собеседования в Facebook