Delphi: строка поиска в TStringList

Question

У меня есть большой TXT (ipaddress.txt) с большим количеством строк, каждая строка представляет собой IP-адрес, например .:

44.XXX.XXX.XXX 
45.XXX.XXX.XXX 
46.XXX.XXX.XXX 
47.XXX.XXX.XXX 
48.XXX.XXX.XXX 

я загрузить этот список в TStringList , например .:

FIpAddressList := TStringList.Create(); 
FIpAddressList.Sorted := true; 
FIpAddressList.LoadFromFile('ipaddress.txt'); 

и я хочу проверить, если IP-адрес находится в списке, например .:

function IsIPinList(const IPAddress : string): Boolean; 
begin 
    Result := (FIpAddressList.IndexOf(IPAddress) <> -1); 
end; 

это работает ... но медленно с объятиями e TStringList.

Есть ли способ ускорить этот процесс?

UPDATE

• Список статично с ежемесячным обновлением, с меньшим или более 5'000 линий.
• Функция вызывается при каждом запросе на сервере (например, 5 раз в секунду).
• Список загружается только при запуске службы сервера.

Answer 1

Один из способов сделать это быстрее, чтобы организовать список, чтобы быть отсортированы так, что поиск может быть выполнен с использованием бинарного поиска, O (журнал N), а не линейный поиск, O (п).

Если список статичен, то лучше всего отсортировать список вне вашей программы, чтобы вы могли сортировать его ровно один раз.

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

Другой подход - использовать словарь, содержащий ваши предметы. Обычно это будет включать хеширование каждой строки. Хотя сложность поиска равна O (n), стоимость хэширования может быть значительной.

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

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

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

---

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

• Мой компьютер может выполнять поиск такого списка 2 000 раз в секунду с помощью линейного поиска.
• Как только вы отсортируете список и переключитесь на двоичный поиск, он сможет управлять 1,000,000 поисков в секунду.
• Переключитесь на сохранение упорядоченного массива целых чисел, и он достигает более 10 000 000 поисковых запросов в секунду.
• С помощью хеш-словаря из целых чисел производительность снова в два раза быстрее.

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