在Python中高效搜索字符串列表以获取字符串列表

我有一个列表字符串列表和一个字符串列表。例如：在Python中高效搜索字符串列表以获取字符串列表

L1=[["cat","dog","apple"],["orange","green","red"]] 
L2=["cat","red"]

如果L1 [I]包含从L2我需要把对（用于在一个图中边）等，在我的例子，我需要对任何项("cat","dog"),("cat,apple"),("red,orange"),("red","green")

我应该用什么方法来使其效率最高。（我的列表L1是巨大的）

来源

2012-02-16 Nihar Sarangi

你试过它直接（也许效率较低）？ – alex 2012-02-16 18:35:44

假设你可能在你的L1子表不止一个“控制”项目。

我使用set()和itertools.product()做到这一点：

from itertools import product 

def generate_edges(iterable, control): 
    edges = [] 
    control_set = set(control) 
    for e in iterable: 
     e_set = set(e) 
     common = e_set & control_set 
     to_pair = e_set - common 
     edges.extend(product(to_pair, common)) 
    return edges

例子：

>>> L1 = [["cat","dog","apple"], 
...  ["orange","green","red"], 
...  ["hand","cat","red"]] 
>>> L2 = ["cat","red"] 
>>> generate_edges(L1, L2) 
[('apple', 'cat'), 
('dog', 'cat'), 
('orange', 'red'), 
('green', 'red'), 
('hand', 'red'), 
('hand', 'cat')]

来源

2012-02-16 19:16:47

我建议将它们全部转换为set s并使用set操作（交集）来找出L2中哪些项在每个L1项中。然后，您可以使用设置减法来获取您需要配对的项目列表。

edges = [] 
L2set = set(L2) 
for L1item in L1: 
    L1set = set(L1item) 
    items_in_L1item = L1set & L2set 
    for item in items_in_L1item: 
     items_to_pair = L1set - set([item]) 
     edges.extend((item, i) for i in items_to_pair)

来源

2012-02-16 18:36:24 Amber

为了使这个代码优化即使L1和L2是巨大的，使用izip产生发电机，而不是创造了巨大的元组的列表。如果你在Python3中工作，只需使用zip。

from itertools import izip 

pairs = [] 
for my_list, elem in izip(L1, L2): 
    if elem in my_list: 
     pairs += [(elem, e) for e in my_list if e!=elem] 
print pairs

该代码是非常容易理解的，它几乎是纯英文！首先，你循环遍历每个列表及其相应的元素，然后询问元素是否在列表中，如果是，则打印除对（x，x）以外的所有对。

输出：

[('cat', 'dog'), ('cat', 'apple'), ('red', 'orange'), ('red', 'green')]

来源

2012-02-16 18:37:14 juliomalegria

您的代码不适用于OP正在寻找的一般情况。 – Amber 2012-02-16 18:41:22

@Amber为什么呢？ – juliomalegria 2012-02-16 18:45:34

由于L2中的任何元素都可以位于L1中的任何列表中，因此L2中的元素数量可能与L2中的元素数量不同。 – Amber 2012-02-17 04:51:04

如果L1是非常大的，你可能要考虑使用开张。它要求你首先对L1进行扁平化和排序。你可以做这样的事情：

from bisect import bisect_left, bisect_right 
from itertools import chain 

L1=[["cat","dog","apple"],["orange","green","red","apple"]] 
L2=["apple", "cat","red"] 

M1 = [[i]*len(j) for i, j in enumerate(L1)] 
M1 = list(chain(*M1)) 
L1flat = list(chain(*L1)) 
I = sorted(range(len(L1flat)), key=L1flat.__getitem__) 
L1flat = [L1flat[i] for i in I] 
M1 = [M1[i] for i in I] 

for item in L2: 
    s = bisect_left(L1flat, item) 
    e = bisect_right(L1flat, item) 
    print item, M1[s:e] 

#apple [0, 1] 
#cat [0] 
#red [1]

来源

2012-02-16 20:08:21

在Python中高效搜索字符串列表以获取字符串列表

回答

相关问题