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

。

有什么办法可以让这个过程更快吗？

更新

• 该列表是静态的，每月更新一次，或多或少有 5'000 行。
• 服务器上的每个请求都会调用该函数（例如每秒 5 次）。
• 该列表仅在服务器服务启动时加载。

Answer 1

加快速度的一种方法是对列表进行排序，以便可以使用二分搜索 O(log n) 执行搜索，而不是使用线性搜索 O(n)。

如果列表是静态的，那么最好的办法是在程序之外对列表进行排序，以便您可以精确地对其进行一次排序。

如果列表更加动态，那么您将必须对其进行排序，并保持所有修改的顺序。在这种情况下，只有当您进行的搜索数量足以克服排序和维护顺序的额外成本时，对列表进行排序才会带来好处。

另一种方法是使用包含您的项目的字典。通常，这将涉及对每个字符串进行哈希处理。虽然查找复杂度为 O(n)，但散列的成本可能会很高。

另一种加快速度的方法是将 IP 地址字符串转换为 32 位整数。事实上，这肯定会产生巨大的性能优势，并且无论有任何其他问题，您都应该这样做。使用 32 位整数总是比使用 IP 地址的字符串表示形式更快、更清晰。

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

虽然您可能只是在寻找一些代码来解决您的问题，但我认为这个问题更多的是算法问题而不是基于代码的问题。在选择算法之前，您需要更好地了解需求、数据大小限制等。一旦您决定了一种算法，或者将选择范围缩小到一个较小的数字进行比较，实施就应该很简单。

---

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

• 我的计算机可以使用线性搜索每秒搜索这样的列表 2,000 次。
• 一旦你对列表进行排序并切换到二分搜索，那么它每秒可以管理 1,000,000 次搜索。
• 切换到存储有序整数数组，每秒可实现超过 10,000,000 次搜索。
• 使用基于哈希的整数字典，性能再次提高两倍。

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

Answer 2

function IsIPinList(const IPAddress : string): Boolean;
var dummy : integer 
begin
   Result := FIpAddressList.Find(IPAddress,dummy);
end;