搜索字符串的列表從另一個列表中

任何子串鑑於數據的這3名列表和關鍵字列表：搜索字符串的列表從另一個列表中

good_data1 = ['hello, world', 'hey, world'] 
good_data2 = ['hey, man', 'whats up'] 
bad_data = ['hi, earth', 'sup, planet'] 
keywords = ['world', 'he']

我試圖寫一個簡單的函數來檢查是否有任何的關鍵字作爲數據列表中任何單詞的子字符串存在。它應該爲good_data列表返回True，併爲bad_data返回False。

我知道如何做到這一點的似乎是一種低效的方式：

def checkData(data): 
    for s in data: 
    for k in keywords: 
     if k in s: 
     return True 
    return False

來源

2009-04-14 Jason Coon

在你的例子中，有這麼少的項目，它並不重要。但是如果你有幾千個物品的清單，這可能會有所幫助。

由於您不關心列表中哪個元素包含關鍵字，因此您可以一次掃描整個列表（作爲一個字符串）而不是一次掃描一個項目。爲此，您需要一個您知道不會出現在關鍵字中的連接字符，以避免誤報。在這個例子中我使用了換行符。

def check_data(data): 
    s = "\n".join(data); 
    for k in keywords: 
     if k in s: 
      return True 

    return False

在我完全不科學的測試，我的版本檢查在約30秒的5000項10萬次的列表。我在3分鐘後停止了你的版本 - 厭倦了等待發布=）

來源

2009-04-14 21:23:41 gnud

您是否在尋找

any(k in s for k in keywords)

這是更緊湊，但可能是低效率的。

來源

2009-04-14 21:05:58

雖然它更緊湊，但它的可讀性要低得多。非常好的恕我直言。 – 2009-04-14 21:09:19

+13

+1，因爲它是標準的pythonista成語 – dwc 2009-04-14 21:13:43

+1這是非常pythonic和乾淨的關鍵字小列表 – 2009-04-14 23:25:02

我認爲這是非常高效和清晰的，雖然你可以使用map（）來避免許多巢。我同意羅斯關於更大列表的字典想法。

來源

2009-04-14 21:07:32

您可以通過將關鍵字列表構建爲正則表達式來改善問題。

這可能允許它們並行測試，但很大程度上取決於關鍵字是什麼（例如，某些工作可能會重複使用測試「hello」和「hell」，而不是從一開始就搜索每個短語對於

每個單詞你可以通過執行此操作：

import re 
keyword_re = re.compile("|".join(map(re.escape, keywords)))

然後：

>>> bool(keyword_re.search('hello, world')) 
True 
>>> bool(keyword_re.search('hi, earth')) 
False

（實際上，它將在找到返回匹配對象，無如果沒有找到 - 這可能是有用的，如果你需要知道哪個關鍵字匹配）

但是，多少（如果有的話），這取決於你的關鍵字。如果您只有一兩個，請保持目前的方法。如果你有一個大的列表，可能需要花時間和分析來看看哪個更好。

[編輯] 作爲參考，這裏的方法爲你的榜樣怎麼辦：

   good1 good2 good3 bad1 bad2 
original  : 0.206 0.233 0.229 0.390 63.879 
gnud (join) : 0.257 0.347 4.600 0.281 6.706 
regex  : 0.766 1.018 0.397 0.764 124.351 
regex (join) : 0.345 0.337 3.305 0.481 48.666

顯然，對於這種情況下，你的方法執行遠遠超過了正則表達式的好。這種情況是否會一直如此，取決於關鍵字的數量和複雜程度以及將要檢查的輸入數據。對於大量的關鍵字，冗長的列表或很少匹配的短語，正則表達式可能會更好，但做可以獲得計時信息，並且可能會嘗試更簡單的優化（如將最常見的詞移到關鍵字列表的前面）。有時候最簡單的方法確實是最好的。

[編輯]在應用正則表達式之前用gnud's solution和類似的方法更新了表格。我還添加了2個新的測試：

good_data3 = good_data2 * 500 # 1000 items, the first of which matches. 
bad_data2 = bad_data * 500  # 1000 items, none of which matches.

其中顯示了各種優勢和劣勢。如果立即找到匹配，聯接確實會變得更糟（因爲加入列表時始終支付預付費用 - 這對於線性搜索方法來說是最好的情況），但對於不匹配的列表，它會執行更好。很多更好，當list.case中有大量的項目時）。

來源

2009-04-14 21:13:10 Brian

如果你有很多關鍵字，你可能想嘗試一個後綴樹[1]。插入三個數據列表中的所有單詞，存儲每個單詞來自哪個列表的終止節點。然後你可以在樹上爲每個關鍵字執行查詢，真的很快。

警告：後綴樹的實現非常複雜！

[1] http://en.wikipedia.org/wiki/Suffix_tree

來源

2009-04-14 21:40:37 marcog

搜索字符串的列表從另一個列表中

回答

相關問題