#c #data-structures #dictionary
#c #структуры данных #словарь
Вопрос:
Как я могу создать быстрый диктонарий (String => Pointer и Int => Pointer ) в C без линейного поиска? Мне нужно несколько (или более) строк кода, а не библиотека, и должна быть возможность использовать его в программном обеспечении с закрытым исходным кодом (LGPL, …).
Ответ №1:
Используйте хэш-таблицу. Хэш-таблица будет иметь поиск в постоянном времени. Вот несколько выдержек на C и реализация на C (и португальском языке 🙂.
Комментарии:
1. Или двоичное дерево, если вы не можете использовать хэш.
2. Вряд ли португальский, если имена переменных и комментарии на английском? 😉
3. Хэш-таблица потенциально может выполнять O (1) операций чтения и ожидаемые амортизированные O (1) операции записи.
Ответ №2:
Вам необходимо реализовать хэш-таблицу, в которой хранятся объекты с использованием хэш-кода. Время поиска постоянно.
Двоичное дерево может перемещаться и находить элемент за логарифмическое (n) время.
Комментарии:
1. Хэш-функция для строк НЕ является постоянной по времени.
2. Бинарное дерево для поиска строк занимает НЕ много (n) времени.
Ответ №3:
Троичное дерево поиска было создано для этой миссии.
Ответ №4:
Если ваши строки будут длинными, вы не сможете рассматривать «Хэш-таблицу» как постоянное время! время выполнения зависит от длины строки! для длинных строк это вызовет проблемы. кроме того, у вас возникает проблема столкновений со слишком маленькой таблицей или слишком плохой хэш-функцией.
если вы хотите использовать хеширование, пожалуйста, посмотрите на karp-rabin. если вам нужен алгоритм, зависящий ИСКЛЮЧИТЕЛЬНО от размера слова, которое вы ищете, пожалуйста, посмотрите на aho-corasick.
Комментарии:
1. Это постоянное время относительно N (количества строк), но также может варьироваться в зависимости от других факторов (например, длины строки). Термин «постоянное время» подразумевает «в отношении размера / количества входных значений». Является ли это «достаточно производительным» в данном случае, подлежит обсуждению.