python - 使用Python检查列表元素是否是另一个列表中元素的子元素

Question

鉴于以下数据:

a = ["onee", "two", "three"]
b = ["one", "four"]

我想要进行一些测试，如下所示:

[True if x in a else False for x in b]

返回

[True, False]

而不是

[False, False]

因此，对于列表 b 中的每个元素，我想查看它是否是列表 a 中任何元素的子字符串。

实现此目的的一种方法如下:

test = []
for elb in b:
    included = False
    for ela in a:
        if elb in ela:
            included = True
        break
    test.append(included)

不过，我觉得这不是一个很好的方法，也许有一种理解可以改进它？

以下方法也有效:

[True if any(elb in ela for ela in a) else False for elb in b]

我只是认为可能有更好的方法。

Answer 1

首先，这个

True if True else False

是多余的。所以在你的第一个比较中。你可以只拥有:[x in a for x in b] ，类似地，[any(elb in ela for ela in a) for elb in b] .

我认为就字符而言，这篇文章很短，您会明白的。

但是，从效率角度来看，您可以从 a 中的所有字符串预先生成所有可能的子字符串。 ，将它们存储在 set 中.

这意味着复杂性将从 O(n*m*p) 降低。 ，其中n的长度是b , m的长度是a ，和n是 a 的平均子串长度，简单地O(n) 。这是因为，一旦创建了子字符串查找集，就会检查 b 中的特定元素。是 O(1)操作，因为您正在检查是否包含在集合中，而不是 O(m*p)您必须检查 a 中每个元素的每个子字符串。 .

要生成此子字符串查找集，您可以使用集合理解:

a_substrings = {s[i:j] for s in a for i in range(len(s)) for j in range(i+1, len(s)+1)}

然后你可以检查in这个:

[s in a_substrings for s in b]

给出了预期的[True, False]供您输入。

---

这真的更快吗？

对于小尺寸a和b列表中，创建查找集的开销将超过能够检查 b 中每个元素的优势。 。此外，对于一个长得过分的a列表，包含长 strings ，甚至是中等大小的b ，花时间遍历 a 的所有子字符串可能会再次变慢。并创建查找集，特别是如果 b 中的大多数元素将在 a 的前几个字符串内匹配.

但是，在两个列表都很长的情况下，最重要的是当 b 时很长，您的方法将不断生成和检查 a 的相同元素一遍又一遍地对 b 的每个元素进行分析。显然这比预先计算子集要慢。我想这本质上是搜索引擎的一个关键优化——当有人提出查询时，他们不会每次都从白纸开始搜索网站，而是不断地重新评估所有已知的网站，当然是按照受欢迎程度的顺序，这样当查询到来时它们就“准备好了”。