Эффективный алгоритм поиска для конкретных полей данных

Question

Таким образом, мне фактически поручено написать алгоритмы фильтрации / поиска.

Задача: Фильтр: поиск и список объектов, которые удовлетворяют указанному атрибуту (ам)

Скажем, вся система представляет собой систему регистрации студентов.

У меня есть данные, как показано ниже. Мне нужно будет отфильтровать и выполнить поиск по этим атрибутам, например, поиск / фильтр по полу, имени студента или дате рождения и т. Д.

Имя студента, Пол, Дата рождения, № мобильного телефона

Существует ли конкретная эффективная формула алгоритма или метод для каждого из этих полей.

Например, у каждой строки и целого числа есть свой собственный тип эффективного алгоритма поиска, верно?

Вот что я собираюсь сделать. Я собираюсь кодировать двоичный алгоритм поиска для поиска / фильтрации на основе этих полей выше.

Вот и все. Но да, это просто, если честно.

Но мне просто любопытно, какой правильный и подходящий подход к кодированию для эффективного алгоритма поиска / фильтрации для каждого из этих полей вы, ребята, сделаете?

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

При необходимости будет использоваться алгоритм последовательного поиска, если данных меньше.

Answer 1

Поиск - это очень широкая тема, которая полностью зависит от вашего варианта использования. при построении эффективного алгоритма поиска вы должны учитывать следующие факторы

• Каков размер ваших данных? - это исправлено или периодически меняется?
• Как часто вы собираетесь вставить / изменить / удалить ваши данные?
• Ваши данные отсортированы или не отсортированы ?

• Вам нужен поиск * 109 * по префиксам , такой как автоматический поиск, автозаполнение, поиск по длинному префиксу и т. Д. ?

  Теперь давайте подумаем о решении / подходе

  1. , если ваши данные меньше и не отсортированы, как вы можете попробовать Линейный поиск (который имеет O(n) временная сложность, где «n» - это размер ваших данных / массива)

  2. , если ваши данные уже отсортированы, что не всегда так, вы можете использовать Бинарный поиск , поскольку его сложность составляет 0 (log n) . если ваши данные не отсортированы, то для сортировки данных потребуется (n logn) ~, как правило, если вы используете Java, Arrays.sort () по умолчанию использует сортировку слиянием илиБыстрая сортировка (n logn) .

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

  4. Поиск по префиксу : поскольку вы упоминали о поиске по именам, у вас также есть возможность использовать структуру данных " Tries ".

Tries - отличный вариант, если вы выполняете Вставка / Удаление / Обновление Функциональность Часто . Поиск элементов в Trie равен 0 ( k ), где "k" - длина строки, которую нужно искать.

Поскольку у вас есть регистрационные данные, где вставка, обновление, удалениеобщая структура данных TRIES - хороший вариант для рассмотрения.

Кроме того, проверьте эту ссылку, чтобы выбрать между Tries и HashTables TriesVsMaps

Ниже приведенпримерное представление Tries (img src: Hackerearth)