Оптимальный * способ сделать функцию поиска в таблице в C?

Question

Мне нужно выполнить поиск в таблице для перевода с входа A на выход A '. У меня есть функция с входом A, который должен вернуть A '. Использование баз данных или простых файлов невозможно по определенным причинам. Я должен жестко закодировать поиск в самой программе.

Что было бы наиболее оптимальным (* по пространству и по времени отдельно): используя хэш-карту, с A в качестве ключа и A 'в качестве значения, или используйте операторы регистра переключателя в функции?

Таблица представляет собой строку для поиска строки с размером около 60 записей.

Answer 1

Если скорость крайне необходима, то я бы посчитал идеальным хешированием . В противном случае я бы использовал массив / вектор строки для пар строк, созданных статически в порядке сортировки, и использовал бы двоичный поиск. Я также написал бы небольшую тестовую программу для проверки скорости и ограничений памяти.

Answer 2

Я полагаю, что и переключатель, и поиск в таблице будут эквивалентны (хотя нужно выполнить некоторые тесты на используемом компиляторе). Современный компилятор C реализует большой переключатель с таблицей соответствия. Поиск в таблице можно легче создать с помощью макроса или языка сценариев.

Для обоих решений вход A должен быть целым числом. Если это не так, одним из решений будет реализация огромного оператора if-else.

Если у вас есть строки, вы можете создать два массива - один для ввода и один для вывода (это будет неэффективно, если они не одинакового размера). Затем вам нужно перебрать содержимое входного массива, чтобы найти совпадение. На основе найденного вами индекса вы возвращаете соответствующую выходную строку.

Answer 3

Несмотря на то, что метод hash быстрый, все же существует вероятность коллизии (два входа генерируют одинаковое значение хэш-функции). Быстрый метод зависит от типа данных ввода.

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

Для строковых типов ввода вложенный поиск может быть самым быстрым. Одним из примеров является разбивка таблиц по длине. Первый массив возвращает указатели на таблицу для поиска по длине, например, char * sub_table = First_Array [5] для строки длиной 5. Их можно настроить для специализированных входных данных.

Другой метод заключается в использовании B-дерева, которое представляет собой двоичное дерево «страниц». Поведение аналогично вложенным массивам.

Если вы сообщите нам тип ввода, мы можем лучше ответить на ваш вопрос.

Answer 4

Создайте ключ для быстрого расчета и хэш

Если таблица довольно статична и вряд ли изменится в будущем, вы можете посмотреть, если добавление нескольких выбранных символов (с индексами исправлений) в строку "ключ" может получить уникальные значения (значение К). Из них вставьте строки «value» в hash_table, используя предварительно рассчитанное значение «K» для каждой строки «key».