python - 使用列表理解来标记两个列表共有的数据

Question

我有两个列表，A 和 B。我想生成第三个列表，如果 A 中的相应条目在字符串末尾的列表 B 中有一个条目，则为 1，否则为 0。

A = ['Mary Sue', 'John Doe', 'Alice Stella', 'James May', 'Susie May']
B = ['Smith', 'Stirling', 'Doe']

我想要一个能给出结果的列表理解

[0, 1, 0, 0, 0]

请记住，这是一个更普遍问题的特例。 A 中的元素可以有任意空白，并且可以包含任意数量的单词。同样，B 中的元素可以有任意数量的单词。例如

A = ['  Tom Barry Stirling Adam', 'Maddox Smith', 'George Washington Howard Smith']
B = ['Washington Howard Smith', 'Stirling Adam']

应该返回

[1, 0, 1]

到目前为止，我有以下内容

[1 if y.endswith(x) else 0 for x in B for y in A]

但是返回列表的长度不是我想要的维度，因为它为 A[i]、B[j] 元素的每个组合给出 0 或 1。我对使用 for 循环的解决方案不感兴趣，我需要一个列表理解来提高速度。

Answer 1

一种更快的方法是将元组传递给endswith:

In [8]: A = ['Mary Sue', 'John Doe', 'Alice Stella', 'James May', 'Susie May']

In [9]: B = ['Smith', 'Stirling', 'Doe']            

In [10]: A *= 1000

In [11]: %%timeit                                                          
t = tuple(B)
[int(s.endswith(t)) for s in A]
   ....: 
100 loops, best of 3: 5.02 ms per loop

In [12]: timeit [int(any(full.endswith(last) for last in B)) for full in A]
100 loops, best of 3: 21.3 ms per loop

您对 A 中的每个元素进行一个函数调用，而不是为 A 中的每个元素对 B 中的每个元素进行一次函数调用，并且没有与 any 一起使用的生成器的开销。

您可以看到使用更大的单词集速度有多快，尤其是在匹配稀疏的情况下:

In [2]: from random import sample

In [6]: A = [s.strip() for s in open("/usr/share/dict/american-english")][:20000]

In [7]: B = sample([s.strip() for s in open("/usr/share/dict/british-english")], 2000)

In [8]: %%timeit                                                                      
t = tuple(B)
[int(s.endswith(t)) for s in A]
   ...: 

1 loop, best of 3: 2.16 s per loop
In [9]: timeit [int(any(full.endswith(last) for last in B)) for full in A]              
1 loop, best of 3: 26.6 s per loop

你说你不想要循环，但随着列表的增长排序可能是更好的选择，然后平分以找到任何匹配的字符串，log n 搜索反转逻辑:

from  bisect import bisect_left


def compress(l1, l2):
    srt1 = sorted(s[::-1] for s in l2)
    hi = len(l2)
    for ele in l1:
        rev = ele[::-1]
        ind = bisect_left(srt1, rev, hi=hi)
print(list(compress(A, B)))

与检查每个子字符串的二次方法相反，运行时间为 O(N log N)。