Мини опрос. Используете ли вы хэш-таблицы в своём трансляторе, компиляторе?
Хэш-таблицы
Страница: 1
Сообщений 1 страница 15 из 15
Опрос
Поделиться12017-06-22 18:40:39
- Активный участник
- Сообщений: 355
- Провел на форуме:
18 дней 8 часов - Последний визит:
2020-11-06 19:50:25
Поделиться22019-01-31 01:41:08
- Активный участник
- Сообщений: 408
- Провел на форуме:
2 дня 13 часов - Последний визит:
2021-07-13 18:36:29
Поделиться32019-01-31 03:03:24
Лис, там совершенно другие требования к хеш-функции.
Поделиться42019-01-31 03:13:32
- Активный участник
- Сообщений: 408
- Провел на форуме:
2 дня 13 часов - Последний визит:
2021-07-13 18:36:29
МихалНик, цитирую статью:
Базовый вариант t1ha является (самой) быстрой переносимой хэш-функцией для построения хэш-таблиц
Поделиться52019-01-31 10:40:32
У меня сейчас нет транслятора-компилятора, но не вижу смысла их не использовать. Это - эффективное отображение чего угодно на что угодно. При разработке на лиспе это была моя любимая структура данных, которая использовалась очень часто.
Отредактировано БудДен (2019-01-31 10:41:15)
Поделиться62019-01-31 11:38:11
ВежливыйЛис написал(а):
цитирую статью
А теперь попробуйте с ней построить подстановку (завершения) слов в IDE.
Поделиться72019-01-31 12:51:36
Для завершения слов в IDE, начиная с начала слова, конечно, быстрее будет сортированный контейнер.
Но во многих случаях слов мало и разница между сортированным и несортированным незаметна.
Поделиться82019-01-31 15:10:52
Но во многих случаях слов мало и разница между сортированным и несортированным незаметна.
В более менее крупных проектах десятки-сотни тысяч разных идентификаторов.
Поделиться92019-01-31 19:01:17
Но разве не будет более удобной структурой "обратный индекс по буквам" (т.е. дерево)?
Тогда, спрашивается, зачем "t1ha"? Который не учитывает алфавит конкретного языка, избыточен по размеру - хватает 32 бит, а часто и 16. И вряд ли быстрее, точнее почти всегда будет медленее.
Отредактировано МихалНик (2019-01-31 19:11:11)
Поделиться102019-01-31 21:38:37
Думается, что отфильтровать сто тысяч строк должно занимать малые доли секунды. Но я не против деревьев, конечно же.
Поделиться112019-01-31 22:26:22
Думается,
БудДен написал(а):
Думается, что отфильтровать сто тысяч строк должно занимать малые доли секунды. Но я не против деревьев, конечно же.
Сколько времени на вскидку занимала пересборка BBCB?
Поделиться122019-02-01 13:28:24
1-2 минуты, но давайте не будем. Тут особо и обсуждать-то нечего. Есть хеш-таблицы и есть деревья. Одними деревьями, по-хорошему, обойтись нельзя.
Поделиться132019-02-01 13:33:49
Хотя если подумать, то может и можно. Но не так уж нужно.
Поделиться142019-02-01 17:32:54
БудДен написал(а):
Есть хеш-таблицы и есть деревья. Одними деревьями, по-хорошему, обойтись нельзя.<...>
Хотя если подумать, то может и можно. Но не так уж нужно.
Оптимизацию руками делать неэффективно, как и жестко приколачивать хеш или дерево, если что-то может поменяться, поэтому, например, в реализациях CASE компиляторы могут сочетать оба варианта под конкретный оператор. Ничто не мешает сочетать деревья с хешами в произвольном порядке. Дерево тоже требует функцию выбора ветки, которая равносильна частному случаю хеш-функции.
Поделиться152019-02-09 12:36:24
Заметим в скобках, что в куче языков (Perl,JS,Lisp,Golang) хеш-таблица является примитивным типом, а чтобы дерево было примитивным типом - я нигде не видел. Разве только в Дельфи. Но, перейдя с Дельфи на Лисп, я почуствовал большое облегчение. Для хеша нужно понять, какие объекты идентичны, а какие - нет. Для дерева нужно знать, как их сравнивать. Может быть, требование к сравнимости - это более строгое требование, поэтому предпочитают более общую структуру. Хотя в хеше всё равно в итоге дело сводится к числу.
Страница: 1