Улучшение производительности для сопоставления строк

Question

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

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

name phonenum

---

hari 1234

abc 3873

....

Эта база данных имеет большое количество строк (около 1 миллиона).Когда пользователь открывает приложение, оно получает список телефонных номеров из телефонных контактов этого человека и сопоставляет его с базой данных.Мы возвращаем все телефонные номера, которые присутствуют в базе данных.Сейчас то, что мы делаем, очень и очень неэффективно.Мы отправляем номера телефонов из телефонных контактов по 20 штук. И сопоставляем их с базой данных.Это приведет к сложности числа телефонных контактов * O (n).

Я подумал о некоторых улучшениях, таких как сортировка строк базы данных по телефонным номерам, чтобы мы могли выполнять бинарный поиск.В дополнение к этому у нас может быть хеш-таблица, содержащая около 10 000 телефонных номеров в кэш-памяти, и мы можем искать по этой кэш-памяти изначально.Только в случае пропуска мы получим доступ к базе данных и осуществим поиск в базе данных со сложностью O (log n) с помощью бинарного поиска.

Также существует проблема отправки телефонных номеров для сопоставления.отправлять их как таковые или отправлять как хешированные значения?будет ли это иметь значение с точки зрения улучшения производительности?

Есть ли другой способ сделать это?

Я объяснил весь сценарий, чтобы вы могли лучше понять мои потребности

спасибо

Answer 1

Если у вас уже есть база данных SQL Server, пусть она позаботится об этом. Создайте индекс в столбце номера телефона (если у вас его еще нет). Отправьте все номера в списке контактов за один раз (не нужно делить их на 20) и сопоставьте их с базой данных. Сервер SQL, вероятно, использует намного лучшую индексацию, чем все, что вы могли бы придумать, так что это будет довольно быстро.

В качестве альтернативы, вы можете попытаться вставить числа во временную таблицу и выполнить запрос, но я не знаю, будет ли это быстрее.

Answer 2

Если вы можете представлять телефонные номера в виде числовых значений вместо строк, то вы можете поместить индекс в поле вашей базы данных, что сделает операции поиска очень быстрыми.Даже если вам нужно представить их как строки, индекс в поле базы данных сделает поиск значений достаточно быстрым, чтобы не создавать проблем в общей схеме вещей.

Ваша самая большая проблема с производительностью будетбыть со всеми туда и обратно между приложением и вашей базой данных.Это узкое место в производительности любой веб-программы.Если вы вряд ли достигнете высокого уровня успеха (возможно, 2% контактов пользователя находятся в вашей базе данных), вам, вероятно, будет лучше отправлять весь список телефонных номеров одновременно, поскольку вы будете просто получать данныеназад для нескольких из них.

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

Для успешной стратегии кэширования потребуется хорошее понимание того, как будут использоваться данные,Я не могу дать много указаний на основе предоставленной информации.Например, если на 90% телефонов, использующих ваше приложение, все телефонные номера будут сопоставлены в небольшой группе номеров в базе данных, то непременно поместите эту небольшую группу в Hashtable.Но если пользователи, скорее всего, будут иметь любые номера телефонов, которые не входят в эту небольшую группу, вам придется совершать обходы базы данных.Ключом будет создание запроса, который позволит базе данных вернуть все необходимые данные за одну поездку.

Answer 3

Я бы разделил телефонный номер на три части

пример 777.777.7777

Каждый раздел может быть сохранен в int и использоваться как хеш-тег.

Это будет означать, что ваше хранилище данных станет серией хеш-таблиц.

Или вы можете принудительно ввести целое число в целое число, а затем использовать его в качестве своего хеш-ключа.Но для быстрого результата вам понадобится больше ведер.

Cheers