Что происходит быстрее: «дерево оснований» или «b-tree»

Question

Для обработки языка, как в обычных словарных словах, который будет быстрее на , читает, дерево оснований или обычное дерево b? Есть ли более быстрый метод, например, словарь с ведрами & хеширование?

Answer 1

Как и всегда, вам нужно будет ориентироваться в контексте приложения, чтобы быть уверенным.

Однако я ожидаю, что в этом случае хорошо реализованная хеш-таблица, вероятно, окажется самой быстрой. В основном это требует:

• Один сканирования через строку для вычисления значения хеш-функции, как правило, с использованием очень быстрые операции, такие как немного зыбучих/операцию XOR
• Один хэш-таблица подстановки на основе значения хэш-
• Одна строка сравнения чтобы подтвердить, что вы имеете право слово
• немного дополнительной обработки в случае, когда есть хэш столкновения - однако вы можете настроить ваш размер хеш, чтобы минимизировать этот

десятичную дерево также будет очень быстрым, есть лишь немного дополнительных накладных расходов из-за необходимости пересечения нескольких уровней узлов дерева. Если ваше дерево относительно скудное, вполне вероятно, что поисковые запросы будут нуждаться только в небольшом количестве уровней, чтобы найти уникальный ответ. Одним из преимуществ дерева оснований является то, что он расскажет вам очень рано, если у вас нет возможных совпадений (например, пустая ветвь для дерева, начинающаяся с «qq»)

Бинарное дерево, вероятно, будет самым медленным, так как оно будет в среднем приходится искать через несколько уровней узлов дерева. Однако для большинства целей он будет достаточно быстрым.