Поиск по нескольким записям во время входа

Question

Мне нужно написать программу, которая создает адресную книгу, которая может обеспечить поиск по нескольким полям с большим количеством записей.Бинарный поиск - вариант, но сложная часть состоит в том, что пользователь может искать по любому из четырех полей (firstName, lastName, phoneNumber, City).Так что нет конкретного столбца, по которому я могу отсортировать список.Программа также должна возвращать результаты поиска в логарифмическом времени.Прямо сейчас я создал общий массив , который содержит все четыре поля.Кто-нибудь может подсказать, что было бы лучшим способом заставить поиск работать во время регистрации.

Answer 1

Один из подходов, требующих большого объема памяти, состоит в построении четырех параллельных двоичных деревьев поиска (или четырех Set с, компараторы которых сравнивают одно поле за раз). Таким образом, вы можете выполнить поиск по любому дереву, чтобы найти узел с конкретным полем за O (LG N) времени.

Answer 2

Используйте базу данных и определите нужные вам индексы.

Если вы не можете использовать БД, то сортируйте и ищите.Вы можете отсортировать время O (log n) по любому полю, которое вам нужно.Затем вы можете выполнить поиск за O (log n) по отсортированному полю.Не способ сделать это в производственной среде, но в качестве задания вы можете заявить: «Общая сложность времени: O (log n)».

Answer 3

Храните его, используя 4 дерева и массив.

4 дерева должны учитывать только индексы. Вам не нужно хранить всю каждую строку в дереве, достаточно только строки, чтобы отличить ее от остальных строк (т.е. хранить символы в узлах, и вы получите лист, когда у вас будет достаточно префикса определить строку (ы)). Вы можете быть немного умнее, аннотируя свое дерево узлами «пропустить n букв», чтобы не хранить внутренние узлы, когда все строки в этом поддереве равны следующим n буквам.

Затем архивист сохраняет записи.

На листьях деревьев вы просто храните указатель в массиве.

Если вы делаете это правильно, вы используете 350 000 * 2 * 4 (байты для целого числа) + X ~ = 3 МБ + X, где X - размер вашего файла, конечно, ваша система имеет столько же? Вы даже можете оставить данные в файле и индексировать в файл.