Лучшая структура данных для хранения и поиска фраз в переполнении стека
Я использую структуру данных try для хранения слов. Теперь у меня есть требование, которое необходимо, учитывая данный абзац, если определенные фразы присутствуют в том же абзаце.
Что было бы наиболее эффективным способом сделать это? Общее количество фраз будет не более 100.
Решение
Если бы я был тобой, я бы просто сначала что-то скомбинировал, используя boost :: multi_index_container, потому что потом, если ты получишь еще больше требований позже, будет довольно легко расширить его дальше. Если позже вы измерите и обнаружите, что он не работает должным образом, вы можете заменить его оптимизированной структурой данных.
Другие решения
Указанное три является субоптимальным во многих отношениях.
- Для начала он строит несколько узлов на каждый вставленный элемент. Как пишет автор, «каждый символ клавиши ввода вставляется как отдельный узел Trie». Это ужасное и ненужное наказание! Использование
ALPHABET_SIZEбольше 2 добавляет оскорбление к травме здесь; Мало того, что фразе в пятьдесят байтов потребуется пятьдесят узлов, но каждый узел, вероятно, будет иметь размер более ста байтов … Каждый элемент или «фраза» длиной в пятьдесят байтов может потребовать до 5 КБ памяти с использованием этого кода! Это даже не самое худшее. - Алгоритм обеспечивает встраивание
mallocвнутренне, что делает его довольно сложным для оптимизации. Каждый узел имеет свое выделение, что делаетinsertоченьmalloc-heavy. Детали распределения должны быть отделены от обработки структуры данных, если не для целей оптимизации, то для простоты использования. Программы, которые интенсивно используют этот код, могут столкнуться с проблемами производительности, связанными с фрагментацией памяти и / или ошибками кэширования, без какой-либо простой или существенной оптимизации, за исключением замены дерева на что-то другое. - Это не единственное, что здесь не так … Этот код не слишком портативный, или! Если вы в конечном итоге запустить это на старом (не тот старый; они все еще существуют!) мэйнфрейм, который использует EBCDIC, а не ASCII, этот код вызовет переполнение буфера, и для исправления будет вызван программист (вы).
<sarcasm>Это так оптимально, верно?</sarcasm>
Я написал трехэлементную реализацию PATRICIA, которая использует ровно один узел на элемент, размер алфавита два (он использует биты каждого символа, а не каждого символа) и позволяет вам использовать любое распределение, которое вы пожелаете … увы, я еще не приложили много усилий для рефакторинга своего интерфейса, но он должен быть достаточно близок к оптимальному. Вы можете найти эту реализацию Вот. Вы можете увидеть примеры вставки (используя patricia_add), извлекая (используя patricia_get) и удаление (используя patricia_remove) в patricia_test.c файл теста.