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;

它有效......但是速度很慢TStringList.

有没有办法让这个过程更快？

UPDATE

Answer 1

使这更快的一种方法是安排对列表进行排序,以便可以使用二进制搜索O(log n)而不是线性搜索O(n)来执行搜索.

如果列表是静态的,那么最好的办法是在程序外部对列表进行排序,以便您可以对其进行一次排序.

如果列表更具动态性,那么您必须对其进行排序,并保持所有修改顺序.在这种情况下,如果您进行的搜索次数足以克服排序和维护订单的额外成本,则对列表进行排序只会带来好处.

另一种方法是使用包含您的项目的字典.通常,这将涉及散列每个字符串.虽然查找复杂度为O(n),但散列的成本可能很高.

另一种加快速度的方法是将IP地址字符串转换为32位整数.事实上,这肯定会带来巨大的性能优势,无论出于何种其他问题,您都应该这样做.使用32位整数比使用IP地址的字符串表示更快更清晰.

这些只是一些可能的方法,还有更多.选择哪一项在很大程度上取决于使用权衡.

虽然您可能只是在寻找一些代码来解决您的问题,但我认为这个问题比基于代码的算法更具算法性.在选择算法之前,您需要更好地理解要求,数据大小限制等.一旦确定了算法,或将选择范围缩小到较小的数字进行比较,实现应该是直截了当的.

另一种可能是你误诊了你的问题.即使对作为字符串存储的5000个IP地址列表进行线性搜索,也应该比报告的更快:

因此,您的搜索性能可以轻松提高20,000倍,我仍然不认为您的性能问题低于您的信念.我想知道你每次搜索时是否正在从磁盘读取文件的真正问题.