C: Хранить и индексировать огромное количество информации! Школьный проект

Question

Мне нужно сделать школьный проект на C (я тоже не знаю c ++).

Мне нужна структура данных для индексации каждого слова из примерно 34 тыс. Документов, это много слов, и мне нужно составить рейтинг слов, я уже делал этот проект около 2 лет назад (я в школе и в этом году) и я использую хэш-таблицу двоичного дерева, но я получил небольшую оценку, потому что моему проекту потребовалось около 2 часов, чтобы проиндексировать все слова. Мне нужно что-то немного быстро ... любые предложения?

ТКЗ Roberto

Answer 1

Если у вас есть возможность, я настоятельно рекомендую использовать ядро ​​базы данных (MSSQL, MySQL и т. Д.), Так как это именно тот набор данных и операции, для которых они написаны. Лучше не изобретать велосипед.

Иначе зачем вообще использовать btree? Из того, что вы описали (и я понимаю, что мы, вероятно, не получаем полную историю ...), может быть полезна прямая хеш-таблица со словом в качестве ключа и его рангом / числом случаев?

Answer 2

bogofilter (фильтр спама) должен вести подсчет слов. Он использует dbm в качестве бэкэнда, так как ему требуется постоянное хранение слова -> счетная карта. Возможно, вы захотите взглянуть на код для вдохновения. Или нет, поскольку вам нужно реализовать часть db для школьного проекта, а не часть фильтра спама.

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

Если это медленно, профилируйте это, и посмотрите, является ли ваша проблема одной медленной функцией, или это пропускает кэш, или это неправильные предсказания ветвления.