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

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

LVV>Хеш-функция — это вычисление значения многочлена от строки, так что никаких О(длина строки тут нет).
Это как так? Ты хочешь сказать, что от строки в 10 букв и в 10 мегабайт хэш за одинаковое время считается?
Кроме того, ещё в хэш-таблице, в конце, надо сравнивать строку со строкой, при наличии коллизий, неоднократно. Это тоже пропорционально длине строки. Так что хэш-таблица строк, по добавлению это никак не меньше O(размер добавляемого текста)? а по поиску никак не меньше O(объём текста, который ищем).
Очевидно бор в этом смысле не хуже, а если не жаль памяти, то и лучше


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

Ну это да, но если самому писать конкуренты STL-контейнерам, трудно адекватные контексты использования перебрать.
С другой стороны в конкретном случае словаря из строк в что угодно, логичнее написать самом бор и сравнить с STL-ной мапой и хэш-мапой (которая беспорядочная)

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

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

Давай лучше "malloc" писать

Вот хороший пример.
— Оптимальная реализация.
— Отлажен.
— Хорошо умеет в многоядерность.
— Чистый С, без питоновской мути.
— Много комментариев.
— Всё просто и понятно.
— Ещё и куча отладочных инструментов встроена.

LVV>>Хеш-функция — это вычисление значения многочлена от строки, так что никаких О(длина строки тут нет).
E>Это как так? Ты хочешь сказать, что от строки в 10 букв и в 10 мегабайт хэш за одинаковое время считается?
Ты в словаре слова видел? Они по 10 метров?
E>Кроме того, ещё в хэш-таблице, в конце, надо сравнивать строку со строкой, при наличии коллизий, неоднократно. Это тоже пропорционально длине строки. Так что хэш-таблица строк, по добавлению это никак не меньше O(размер добавляемого текста)? а по поиску никак не меньше O(объём текста, который ищем).
Коллизии разными способами решаются, не только последовательным рехешированием.
Ну, и как всякая вероятностная система, сильно зависит от распределения.
Далее надо учитывать специфику словаря — универсальный всемогутер нам нафиг не нужен.
E>Очевидно бор в этом смысле не хуже, а если не жаль памяти, то и лучше
Может быть.
E>Ну это да, но если самому писать конкуренты STL-контейнерам, трудно адекватные контексты использования перебрать.
E>С другой стороны в конкретном случае словаря из строк в что угодно, логичнее написать самом бор и сравнить с STL-ной мапой и хэш-мапой (которая беспорядочная)
Ну, время будет — попробую.

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

LVV>Ты в словаре слова видел? Они по 10 метров?
Какая разница? 1 слово в 10 метров или миллион слов по 10 букв -- суммарный объём добавленного в словарь текста будет одинаковый и именно ему будет пропорционально время работы...
Та же асимптотика и для объём текста, который ищем.

LVV>Коллизии разными способами решаются, не только последовательным рехешированием.
Есть способ хеширования, при котором в конце не надо сравнивать со всеми элементами в корзине?

E>>Очевидно бор в этом смысле не хуже, а если не жаль памяти, то и лучше
LVV>Может быть.
такая модальность ответа от преподавателя с твоим стажем доставляет. Неужели студни ни разу такого рода вопросов не задавали?

E>>Ну это да, но если самому писать конкуренты STL-контейнерам, трудно адекватные контексты использования перебрать.
E>>С другой стороны в конкретном случае словаря из строк в что угодно, логичнее написать самом бор и сравнить с STL-ной мапой и хэш-мапой (которая беспорядочная)
LVV>Ну, время будет — попробую.
Пиши, что выйдет!

E>>Очевидно бор в этом смысле не хуже, а если не жаль памяти, то и лучше
Если не жаль памяти, то можно сделать таблицу вообще практически без коллизий, просто увеличив ее размер.
И подобрав хорошую функцию хеширования.

LVV>>Ты в словаре слова видел? Они по 10 метров?
E>Какая разница? 1 слово в 10 метров или миллион слов по 10 букв -- суммарный объём добавленного в словарь текста будет одинаковый и именно ему будет пропорционально время работы...
E>Та же асимптотика и для объём текста, который ищем.
Не. Если я знаю, что у меня "слова" могут быть по 10 метров — я сильно подумаю, как это скажется на реализации.
И, возможно, выберу другой метод.
LVV>>Коллизии разными способами решаются, не только последовательным рехешированием.
E>Есть способ хеширования, при котором в конце не надо сравнивать со всеми элементами в корзине?
Корзина — относительно небольшая по сравнению с таблицей.
Тем более, как я уже в отдельном посте написал, если памяти не жалко, то можно таблицу сделать большой и, тем самым, практически без коллизий.
И функцию хещирования подобрать равномерно распределяющую.
E>>>Очевидно бор в этом смысле не хуже, а если не жаль памяти, то и лучше
LVV>>Может быть.
E> такая модальность ответа от преподавателя с твоим стажем доставляет. Неужели студни ни разу такого рода вопросов не задавали?
Студни про бор не знают...
Они Кнута не читали, а лекций у меня (благодаря минобру и нашему руководству) осталось так мало, что успеть бы про б-деревья рассказать...
E>>>Ну это да, но если самому писать конкуренты STL-контейнерам, трудно адекватные контексты использования перебрать.
E>>>С другой стороны в конкретном случае словаря из строк в что угодно, логичнее написать самом бор и сравнить с STL-ной мапой и хэш-мапой (которая беспорядочная)
LVV>>Ну, время будет — попробую.
E>Пиши, что выйдет!
Обязательно.

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

нормальный такой malloc на 6000 строк

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

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

S>нормальный такой malloc на 6000 строк

А сколько надо? Сколько в канонической реализации в CRT?

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

S>А сколько надо? Сколько в канонической реализации в CRT?
В CRT? Как правило нынче ровно одна — вызов системного аллокатора.

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

S>>А сколько надо? Сколько в канонической реализации в CRT?
CC>В CRT? Как правило нынче ровно одна — вызов системного аллокатора.

А он как реализован, сколько строк, где посмотреть? Насколько понимаю, можно свой аллокатор подсунуть, верно?

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

S>А он как реализован, сколько строк, где посмотреть?
Зависит от системы жеж.

S>Насколько понимаю, можно свой аллокатор подсунуть, верно?
В смысле перекрыть то, что в CRT?
Да, можно.

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

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

Я да, но понимаешь в чём дело: у меня работа такая, трансляторы пишу.