在字符串列表中搜索字符串的最有效方法？

问题描述：

我正在用C＃开发一个自定义电子邮件客户端。其中一个明显的要求是我不下载已经下载的消息。这是通过比较一个唯一的ID字符串和存储在我的数据库中的消息来完成的在字符串列表中搜索字符串的最有效方法？

数据库存储多个用户和多个帐户，以独特的ID不一定会在我的数据库中是唯一的电子邮件。

目前，我有这样的事情：

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订购的唯一ID，然后执行二进制搜索它们，或者存储在哈希表中的唯一ID？或者使用其他一些数据结构？

有谁知道已作出任何类似的性能比较？

答

我决定做一些性能测试，这些都是我得到的结果（从连接到邮件服务器验证的所有电子邮件3000已被下载）：

未排序= 418ms
排序清单= 329ms
有序set = 312ms
排序列表+二进制搜索= 310ms
的HashSet = 305ms

因此，似乎给我的数据至少是HashSets是在这样做，虽然很少有所有4种优化方法之间做出选择最快的。

答

我的建议是以下两种之一：

在数据库中包含所有列，它们一起组成一个唯一的ID索引的帮助下执行搜索。搜索然后是一个简单的选择。
使用散列图。

我不明白你的第一个建议 - 我无法在数据库中执行搜索，因为（至少在我的例子中），我将不得不执行搜索5000次，导致5000次SQL调用。 – cusimar9 2011-04-07 08:47:50

@ cusimar9：什么阻止您在存储过程中执行选择并将所有5000个ID传递到该存储过程？然后所有选择都将在数据库中运行，并且只有一个对数据库的调用。 – 2011-04-07 08:50:20

如果这是最快的方法，我可以这样做，但我不认为它会是 – cusimar9 2011-04-07 08:55:03

答

你可以存储在由它的UID索引的二进制树结构的消息。这样，如果最终尝试添加已存在的消息，则会遇到current_node.uid == new_node.uid的情况，并且可以将其作为副本丢弃。

这样，您系统经历较少的变化，你可以享受的B树的性能！ = d

这可能与使用Hashtable相同？ – cusimar9 2011-04-07 08:55:51

根据你的散列函数的复杂性，它可以有不同程度的更快，是的。但散列会导致冲突，在检查使用的uid时可能会产生误报，导致一些新的消息未被检查。对于这种情况，我会坚持可靠的，你的客户会感谢你。 – bryanegr 2011-04-07 09:00:50

答

我知道，下面的反应并没有明确回答你的问题（S）。但是，我相信它确实回应了您的问题的核心问题，该问题涉及在保持质量系统性能的同时不允许db表中的重复记录。

而是之前插入电子邮件检查重复的电子邮件，考虑/测试以下的逻辑：

上指定一个唯一键约束您的电子邮件数据库表
的try/catch你的INSERT语句独特的违反

这种方法不仅保证避免重复的电子邮件，而且也避免了线性变奏关心你提到的问题。

尽管与SELECT检查相比，此方法可能会产生轻微的性能下降，但只有在发现违规时才会这样做。所以，如果您认为重复电子邮件的机会非常低（一个真正的例外），那么您可能会发现，与SELECT检查相比，此方法是最有效的（并且十分安全）。

要备份我的观点，一定程度上，退房“课＃4”中的保罗尼尔森的名单“10 Lessons from 35k tps”

不幸的是，这对于这个应用程序完全是错误的方法。就像我说的那样，服务器上可能会有5001封电子邮件，我的系统上有5000封电子邮件......其中一封电子邮件是新的，其他电子邮件已经存在。为每个记录选择/插入将遭受巨大的性能影响。 – cusimar9 2011-04-09 08:15:15

在字符串列表中搜索字符串的最有效方法？

相关推荐