C從列表中查找字符串的子集

Question

我有一個1M條目的列表，我想排除這些條目中的20,000個子集（這兩個列表按照不同的順序具有相同的鍵（字符串））。任何人都可以在C中提出一個快速搜索算法來做到這一點？

我不想讀取每個20K ID，並每次查看1M的列表。任何建議將是最有幫助的。

謝謝。

Answer 1

首先對兩個列表排序。然後，您可以將它們一起遍歷，將指針推到另一個指針後面的列表中。

你必須使用C嗎？這聽起來像是Perl的工作。

Answer 2

你想使用的是一個散列集。散列集是一個散列表的特例，它基本上記錄了一個元素是否存在於集合中，或者不是恆定時間。所以，你要做的是將你的20k ID插入散列集合，然後遍歷100萬個字符串並查看它們是否存在於散列集合中。

供您參考，下面是用設定的散列的實現：https://github.com/avsej/hashset.c

你的運行時間是O（n）的，因爲對於每個檢查爲1M的字符串，這將是恆定的時間。

Answer 3

在您開始搜索列表之前，請將20,000個密鑰包含在hash table中。然後，對於列表中的每個項目的關鍵字，如果在哈希表中找到該關鍵字，則從列表中排除該項目。