我在一家正在构建 iPhone 应用程序的初创公司工作。我想问几个问题来改进我们用于字符串匹配的算法。
我们有一个数据库，其中包含大量电话号码以及拥有该电话号码的用户的姓名。假设数据库看起来像这样
姓名电话号码
哈里1234
abc 3873
....
此数据库有大量行(大约 100 万行)。当用户打开应用程序时，应用程序会从该人的电话联系人中获取电话号码列表，并将其与数据库进行匹配。我们返回数据库中存在的所有电话号码。现在，我们所做的事情效率非常低。我们以 20 个为一组发送来自电话联系人的电话号码。我们将其与数据库进行匹配。这将导致 num of phone contacts * O(n) 的复杂性。
我想到了一些改进，比如让数据库行按电话号码排序，这样我们就可以进行二进制搜索。除此之外，我们可以在缓存内存中有一个包含大约 10,000 个电话号码的哈希表，我们可以最初搜索这个缓存内存。仅当未命中时，我们才会访问数据库并使用二分查找复杂度为 O(log n) 的数据库进行搜索。
此外，还有发送电话号码进行匹配的问题。我是按原样发送还是将它们作为散列值发送？这对提高性能有影响吗？
还有其他方法吗？
我解释了整个场景，以便您可以更好地了解我的需求
谢谢
最佳答案
如果您已经有一个 SQL Server 数据库，那就让它来处理吧。在电话号码列上创建一个索引(如果您还没有的话)。一次性发送联系人列表中的所有号码(无需除以 20)并与数据库匹配。 SQL 服务器使用的索引可能比您能想出的任何东西都好得多，所以它会非常快。
或者，您可以尝试将数字插入临时表并对其进行查询，但我不知道那样会不会更快。
关于database - 提高字符串匹配的性能，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6963479/