Ответ 1
Это зависит от количества предметов, которые вы ищете. Если это относительно небольшой список, вы можете сделать проверку string.contains на все. Поэтому, когда пользователь вводит "A", вы просматриваете весь список:
for each contact in contacts
if contact.Name.Contains("A")
Add contact to results
Затем пользователь вводит "T", и вы последовательно просматриваете предыдущие возвращенные результаты:
for each contact in results
if contact.Name.Contains("AT")
Add contact to new search results
Все становится интереснее, если список контактов огромен, но для количества контактов, которые вы обычно имели в телефоне (тысячи было бы много!), это будет работать очень хорошо.
Если интервьюер сказал: "Используйте результаты предыдущего поиска для нового поиска", то я подозреваю, что это тот ответ, который он искал. Для создания нового дерева суффиксов потребуется больше времени, чем просто выполнить поиск по предыдущему набору результатов.
Это можно немного оптимизировать, сохранив позицию подстроки вместе с контактом, чтобы все, что вам нужно сделать в следующий раз, - проверить, соответствует ли следующий символ ожидаемому, но это усложняет алгоритм немного (вы должны рассматривать первый поиск как особый случай, и вам нужно явно проверять длины строк и т.д.), и вряд ли это принесет большую пользу после первых нескольких символов, потому что размер просматриваемого списка будет быть довольно маленьким. Чистый последовательный поиск с проверкой contains будет довольно быстрым. Пользователи не заметили бы несколько микросекунд, которые вы сохранили бы с этой оптимизацией.
Обновление после редактирования вопроса
Если вы хотите сделать это с помощью миллиона контактов, последовательный поиск может быть не лучшим способом для начала. Хотя я все равно попытаюсь. "Скорее всего, для миллионов контактов" возникает вопрос о том, что именно означает "достаточно быстро". Сколько времени требуется, чтобы найти миллион контактов за существование одной буквы? Как долго пользователь хочет ждать? Помните также, что вам нужно показывать только одну страницу контактов до того, как пользователь предпримет другое действие. И вы почти наверняка можете это сделать до того, как пользователь нажмет второй ключ. Особенно, если у вас есть фоновый поток, выполняющий поиск, в то время как поток переднего плана обрабатывает ввод и записывает первую страницу сопоставленных строк на дисплей.
В любом случае, вы можете ускорить первоначальный поиск, создав индекс bigram. То есть для каждого биграмма (последовательность из двух символов) создайте список имен, которые содержат этот bigram. Вы также захотите создать список строк для каждого отдельного символа. Итак, учитывая ваш список имен, у вас будет:
r - ram
a - ram, feat, eat, a
m - ram
h - hello, hi
...
ra - ram
am - ram
...
at - feat, eat, at
...
etc.
Я думаю, вы поняли.
Этот индекс bigram сохраняется в словаре или хэш-карте. Есть только 325 возможных биграмм на английском языке и, конечно, 26 букв, поэтому ваш словарь будет иметь максимум 351 записей.
Итак, вы почти мгновенно просматриваете 1- и 2-символьные имена. Как это вам поможет?
Анализ текста проекта Gutenberg показывает, что наиболее распространенный биграмм на английском языке встречается только в 3,8% случаев. Я понимаю, что имена не будут делиться именно этим распределением, но это довольно хороший примерный номер. Итак, после ввода первых двух символов вы, вероятно, будете работать с менее чем 5% от общего количества имен в вашем списке. Пять процентов миллиона - 50 000. Имея всего 50 000 имен, вы можете начать использовать алгоритм последовательного поиска, который я описал первоначально.
Стоимость этой новой структуры не так уж плоха, хотя она достаточно дорогая, поэтому я бы, конечно же, попробовал простой последовательный поиск. Это будет стоить вам дополнительных 2 миллионов ссылок на имена, в худшем случае. Вы могли бы уменьшить это до миллиона дополнительных ссылок, если вы создадите двухуровневый trie, а не словарь. Это займет немного больше времени для поиска и отображения результатов поиска с одним символом, но недостаточно для того, чтобы быть заметным для пользователя.
Эта структура также очень легко обновляется. Чтобы добавить имя, просто просмотрите строку и введите записи для соответствующих символов и биграмм. Чтобы удалить имя, перейдите к имени, извлечению битрамов, и удалите имя из соответствующих списков в индексе bigram.