Самый эффективный способ поиска строки в списке строк?

Question

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

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

В настоящее время у меня есть что-то вроде этого:

List<String> DownloadedUIDs = BLL.EmailsDataSource.ViewEmailUIDs(AccountNo);     
foreach (string uid in serveruids) {
   if (DownloadedUIDs.Contains(uid)) continue; // don't download messages we already have  
   ...
}

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

Могу ли я увидеть более высокую производительность, когда SQL Server заказываетуникальные идентификаторы, а затем выполнить бинарный поиск по ним, или сохранить уникальные идентификаторы в хэш-таблице?Или используя какую-то другую структуру данных?

Кто-нибудь знает о каких-либо аналогичных сравнениях производительности, которые были сделаны?

Answer 1

Я решил провести тестирование производительности, и вот результаты, которые я получил (от подключения к почтовому серверу до проверки того, что все 3000 электронных писем были загружены):

1. Несортированный список = 418мс
2. Сортированный список = 329мс
3. Sorted Set = 312ms
4. Список сортировки + бинарный поиск = 310 мс
5. HashSet = 305мс

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

Answer 2

Вы можете хранить сообщения в структуре двоичного дерева, которая индексируется по его uid.Таким образом, если вы попытаетесь добавить сообщение, которое уже существует, вы попадете в регистр current_node.uid == new_node.uid, и его можно будет отбросить как дубликат.

Таким образом, ваша система претерпит меньше изменений,и вы получите удовольствие от исполнения b-деревьев!= D

Answer 3

Мне известно, что следующий ответ не дает четкого ответа на ваш вопрос (ы).Тем не менее, я считаю, что он отвечает на суть вашего вопроса, который касается запрета дублирования записей в таблице БД при сохранении качества работы системы.

Вместо проверки на наличие дубликатов электронных писем перед вставкой электронного письма, рассмотрите /протестируйте следующую логику:

1. Укажите ограничение уникального ключа для вашей таблицы базы данных электронной почты
2. попробуйте / поймайте оператор INSERT для уникального нарушения

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

Хотя этот метод может вызвать незначительное снижение производительности по сравнению с проверкой SELECT, он будет делать это только в случае обнаружения нарушения.Итак, если вы считаете, что вероятность дублирования электронных писем очень мала (истинное исключение), то вы можете обнаружить, что этот метод является наиболее эффективным (и надежным) по сравнению с проверкой SELECT.

Чтобы подкрепить мою точку зрения, посмотрите «Урок № 4» из списка Пола Нильсена « 10 уроков из 35 тыс. Ур. / С * »

Answer 4

Мое предложение одно из двух следующих:

1. Выполните поиск в базе данных с помощью индекса, который содержит все столбцы, которые вместе составляют уникальный идентификатор.Поиск тогда просто выбрать.
2. Использовать Hashmap.