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

我正在用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？或者使用其他一些數據結構？

有誰知道已作出任何類似的性能比較？

來源

2011-04-07 cusimar9

我決定做一些性能測試，這些都是我得到的結果（從連接到郵件服務器驗證的所有電子郵件3000已被下載）：

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

因此，似乎給我的數據至少是HashSets是在這樣做，雖然很少有所有4種優化方法之間做出選擇最快的。

來源

2012-02-21 07:26:50 cusimar9

我的建議是以下兩種之一：

在數據庫中包含所有列，它們一起組成一個唯一的ID索引的幫助下執行搜索。搜索然後是一個簡單的選擇。
使用散列圖。

來源

2011-04-07 08:41:04

我不明白你的第一個建議 - 我無法在數據庫中執行搜索，因爲（至少在我的例子中），我將不得不執行搜索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

來源

2011-04-07 08:53:05 bryanegr

這可能與使用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」

來源

2011-04-08 18:26:11 Jed

不幸的是，這對於這個應用程序完全是錯誤的方法。就像我說的那樣，服務器上可能會有5001封電子郵件，我的系統上有5000封電子郵件......其中一封電子郵件是新的，其他電子郵件已經存在。爲每個記錄選擇/插入將遭受巨大的性能影響。 – cusimar9 2011-04-09 08:15:15

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

回答

相關問題