Здравствуйте, Ватакуси, Вы писали:

В>>>Может, мне везёт, но меня 3 раза просили написать словарь.

S>>Где собеседуетесь, в России или за бугром? На какую позицию?
В>Не поверишь, все эти случаи произошли когда на меня выходили какие-то люди и без подготовки просили пройти собеседование в обалденные конторы, про которые они не могут много рассказать, ибо NDA! :D
В>Время было, я проходил, но толку, понятно, 0. Потом или пропадали или конторы совсем не интересные или денег зажимали.

На вопрос так и не ответили Т.е. это были забугорные конторы? Находили по резюме или рекомендациям? Резюме на SO было?

S>На вопрос так и не ответили Т.е. это были забугорные конторы? Находили по резюме или рекомендациям? Резюме на SO было?
Подозреваю, что забугорные. Говорю же, тайна покрытая мраком.
Резюме с линкеда они находили.

Здравствуйте, CreatorCray, Вы писали:

S>>с функцией отображения слов начинающихся с уже введенных символов
CC>Для такого будет удобнее какой нить вариант radix tree, например patricia trie, но не hash как ты просишь.

Merkle Tree- с хешом. Правда я хз, как оно поможет с "начинающихся с уже введённых символов".

Здравствуйте, Ватакуси, Вы писали:

В>Не поверишь, все эти случаи произошли когда на меня выходили какие-то люди и без подготовки просили пройти собеседование в обалденные конторы, про которые они не могут много рассказать, ибо NDA! :D

Этим обычно DarkMatter и их дочки грешат. Но там настолько жуткая репутация, что иначе не заманить вменяемых людей
Думаю что и другие компании со столь же подпорченной репутацией поступают аналогично.

Здравствуйте, $$, Вы писали:

$>Merkle Tree- с хешом.
Шта?

$> Правда я хз, как оно поможет с "начинающихся с уже введённых символов".
Да примерно как собаке — пятая нога.

Здравствуйте, $$, Вы писали:

$>Здравствуйте, CreatorCray, Вы писали:

S>>>с функцией отображения слов начинающихся с уже введенных символов
CC>>Для такого будет удобнее какой нить вариант radix tree, например patricia trie, но не hash как ты просишь.

$>Merkle Tree- с хешом. Правда я хз, как оно поможет с "начинающихся с уже введённых символов".

Сильно, однако. А давайте сделаем так. ХЗ, как оно поможет решению задачи, но давайте сделаем. Как это понимать

Здравствуйте, sergey2b, Вы писали:
S>Проффесор поделитесь пожалуйста вопросами которые вы сейчас даете по алгоритмам и С++
Вот топ-10 вопросов, которые профессора сейчас дают по алгоритмам и C++
1. Мой экран всем видно?
2. Что значит "котик"?
3. Кто-нибудь знает, как в этой зуме со второго монитора трансляцию настроить?
4. У всех мой емейл есть, или кто-то опять будет рассказывать что отправил ответы мне в воцап?
5. То, что защит дипломов в этом году не будет, уже всем понятно, или вам надо ещё раз ссылку на выступление ректора дать?
6. У кого там микрофон включен и ребёнок меня перекрикивает?
7. А как вы себе представляете запрет на списывание во время онлайн-экзамена?
8. Наташа, я через десять минут заканчиваю с этими дебилами, ты суп поставила греть?
9. А что, микрофон не отключается, когда я камеру отключаю?
10. И когда, ***, всё это кончится уже?

Здравствуйте, Ватакуси, Вы писали:

В>С хешем, без деревьев.

с хреновой хеш функцией(с большой вероятностью коллизий) — да

TMU>>А как же ты работаешь??
KP>Зажмуриваюсь и по клавиатуре херачу, как же еще?
KP>А ты сбалансированные деревья по памяти пишешь? Уважаю!



Да ладно, я примерно также, на ощупь...

В>С хешем, без деревьев.

на ассемблере ЕС ЭВМ на векторах

Здравствуйте, Ватакуси, Вы писали:

В>С хешем, без деревьев.
А смысл в нём без подготовки? Хороший словарь — это который проходил "подготовку" лет 20 (отлаживался и тэстировался на реальных задачах).

Здравствуйте, Андруха, Вы писали:

В>>С хешем, без деревьев.

А>с хешем думаю напишу. Там не должно быть сложно. Списки подвешенные к хеш таблице.
А>единственно что — рехешинг при достижении размера > 75% capacity никогда не решал но думаю тоже не должно быть сложно, но надо подумать как эффективно перетащить на новое место.

А в чём проблема? Тупо создаёшь новый массив, в цикле у старого delete у нового insert и всё.

Здравствуйте, LaptevVV, Вы писали:

LVV>А если слово целиком без поиска посимвольно — то лучше хеша ничего нет.
А что тут означает слово "лучше"? Лучше по какому критерию?

LVV>У меня пацаны пишут транслЯторы с ассемблера — там таблицу имен делают все. Оно — то самое.
А они на чём пишут, что им нужно реализовывать словарь с нуля? На чистом Си?

LVV>>А если слово целиком без поиска посимвольно — то лучше хеша ничего нет.
E>А что тут означает слово "лучше"? Лучше по какому критерию?
Хеш = О(1)
LVV>>У меня пацаны пишут транслЯторы с ассемблера — там таблицу имен делают все. Оно — то самое.
E>А они на чём пишут, что им нужно реализовывать словарь с нуля? На чистом Си?
Им с нуля как раз не нужно. Они STL используют — map и/или unodered_map/

Здравствуйте, Sinclair, Вы писали:

S>Вот топ-10 вопросов, которые профессора сейчас дают по алгоритмам и C++
S>1. Мой экран всем видно?
S>...
Нулевой:
0. Меня слышно? Меня всем слышно?

Здравствуйте, LaptevVV, Вы писали:

LVV>>>А если слово целиком без поиска посимвольно — то лучше хеша ничего нет.
E>>А что тут означает слово "лучше"? Лучше по какому критерию?
LVV>Хеш = О(1)

Эмм, но это ведь только в среднем, для большого количества элементов. И не забывайте, что строку ключа придется просканировать от начала до конца, чтобы посчитать её хэш. В реальных сценариях может оказаться, что упорядоченный std::map с небольшим количеством элементов будет не хуже unordered_map с его теоретическим O(1). И оба эти {unordered_}map могут проиграть линейному поиску в массиве с небольшим количеством элементов, которому современные процессоры отлично сделают prefetch памяти в кэш.

Хорошо, что вы рассказываете студентам про O(1), но стоит сказать и про разные константы такой сложности. И вообще, как всё в современных системах сложно

Здравствуйте, LaptevVV, Вы писали:

LVV>>>А если слово целиком без поиска посимвольно — то лучше хеша ничего нет.
E>>А что тут означает слово "лучше"? Лучше по какому критерию?
LVV>Хеш = О(1)
1. Видимо речь идёт о времени исполнения каких-то операций? Каких?
2. Очевидно, что, как минимум О(длина_строки). По идее, если не нужно экономить память, то бор имеет такую же асимптотику при добавлении/поиске...

E>>А они на чём пишут, что им нужно реализовывать словарь с нуля? На чистом Си?
LVV>Им с нуля как раз не нужно. Они STL используют — map и/или unodered_map/
Ну в STL больше ничего подходящего нет, вроде как..

PM>Хорошо, что вы рассказываете студентам про O(1), но стоит сказать и про разные константы такой сложности. И вообще, как всё в современных системах сложно
Это все понятно. Я им рассказываю даже случаи из моей практики.
Здесь несколько лет задавал вопрос, но повторю.
Писал на стандартном С++ прогу научную по перколяции.
Надо было написать обход графа — специального.
В качестве контейнера поставил дек — удобнее так было.
Написал в студии — все работает.
Перенес в Code::Blocks — тоже работает.
А поскольку прога — очень критична по времени, надо заказчику показывать в каком-нить виде время выполнения.
Стандартно поставил clock() спереди-сзади, вывожу в секундах с 3 знаками.
И замечаю, что прога из Code::Blocks примерно в 5 раз быстрее работает.
Предыдущие проги отличались по времени примерно процентов на 10.
А тут в 5 раз!
В результате выискивания блох под ковром — ничего не нашел.
Задал вопрос на РСДН.
Дня через 2 один пацан пишет — проблема в реализации дека в Студии.
Хреново реализована работа с памятью.
Порекомендовали переделать под вектор (о чем я уже и сам подумывал).
Естественно, после рефакторинга под вектор все встало на свои места: разница во времени примерно 10-12% в пользу gcc.
Так что мы не голой теорией занимаемся.

LVV>>>>А если слово целиком без поиска посимвольно — то лучше хеша ничего нет.
E>>>А что тут означает слово "лучше"? Лучше по какому критерию?
LVV>>Хеш = О(1)
E>1. Видимо речь идёт о времени исполнения каких-то операций? Каких?
E>2. Очевидно, что, как минимум О(длина_строки). По идее, если не нужно экономить память, то бор имеет такую же асимптотику при добавлении/поиске...
Ты как с Луны вообще.
Операции поиска и вставки в словарь.
Хеш-функция — это вычисление значения многочлена от строки, так что никаких О(длина строки тут нет).
Но коэффициент некий есть, да.
E>>>А они на чём пишут, что им нужно реализовывать словарь с нуля? На чистом Си?
LVV>>Им с нуля как раз не нужно. Они STL используют — map и/или unodered_map/
E>Ну в STL больше ничего подходящего нет, вроде как.
Можно еще самому написать... Они у меня лабы пишут по алгоритмам — на основе самостоятельно реализованного класса.
И сравнивают время работы стандартных и своих.
Очень полезные упражнения.

Здравствуйте, LaptevVV, Вы писали:

PM>>Хорошо, что вы рассказываете студентам про O(1), но стоит сказать и про разные константы такой сложности. И вообще, как всё в современных системах сложно
LVV>Это все понятно. Я им рассказываю даже случаи из моей практики.
...
LVV>Дня через 2 один пацан пишет — проблема в реализации дека в Студии.
LVV>Хреново реализована работа с памятью.
LVV>Порекомендовали переделать под вектор (о чем я уже и сам подумывал).
LVV>Естественно, после рефакторинга под вектор все встало на свои места: разница во времени примерно 10-12% в пользу gcc.
LVV>Так что мы не голой теорией занимаемся.

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

Хороший пример, почему стоит начинать выбор линейного контейнера с std::vector и в 99,99% случаях на нем же и останавливаться.