python - 检查列表A是否包含列表B中项目的前缀

Question

我有两个列表，我们可以称之为 A和B 。我需要检查列表 A 中的项目并查看 B 中是否有项目从 A 中的一项开始然后停止检查。

A中的内容示例:

https://some/path
http://another/path
http://another.some/path

B中的内容示例:

http://another/path
http://this/wont/match/anything

目前我正在这样做:

def check_comps(self, comps):
   for a in self.A:
      for b in comps:
         if b.startswith(a):
            return a

有更好的方法吗？

Answer 1

您的解决方案在最坏情况下的时间复杂度为 O(nm)，即，如果 n ~ m，则为 O(n^2)。您可以轻松地将其减少到 O(n log(n)) 甚至 O(log(n))。方法如下。

考虑一个单词列表(您的 comps 属性)和一个目标(您的 b)

words = ['abdc', 'abd', 'acb', 'abcabc', 'abc']
target = "abcd"

观察一下，通过按字典顺序对单词列表进行排序，您可以获得前缀列表

prefixes = ['abc', 'abcabc', 'abd', 'abdc', 'acb']

它是退化的，因为 prefixes[0] 是 prefixes[1] 的前缀，因此以 prefixes[1] 开头的所有内容> 也以 prefixes[0] 开头。这有点问题。让我们看看为什么。让我们使用快速(二进制)搜索来查找目标在 prefix 列表中的正确位置。

import bisect


bisect.bisect(prefixes, target)  #  -> 2

这是因为 target 和 prefixes[1] 共享一个前缀，但 target[3] > prefixes[1][3]，因此按字典顺序它应该排在后面。因此，如果prefixes中有target的前缀，它应该位于索引2的左侧。显然，target 不是以 prefixes[1] 开头，因此在最坏的情况下，我们必须一直向左搜索以查找是否有前缀。现在观察，如果我们将这些前缀转换为非简并列表，目标的唯一可能的前缀将始终位于bisect.bisect返回的位置的左侧。让我们减少前缀列表并编写一个辅助函数来检查是否存在目标的前缀。

from functools import reduce


def minimize_prefixes(prefixes):
    """
    Note! `prefixes` must be sorted lexicographically !
    """
    def accum_prefs(prefixes, prefix):
        if not prefix.startswith(prefixes[-1]):
            return prefixes.append(prefix) or prefixes
        return prefixes
    prefs_iter = iter(prefixes)
    return reduce(accum_prefs, prefs_iter, [next(prefs_iter)]) if prefixes else []


def hasprefix(minimized_prefixes, target):
    position = bisect.bisect(minimized_prefixes, target)
    return target.startswith(minimized_prefixes[position-1]) if position else False

现在让我们看看

min_prefixes = minimize_prefixes(prefixes)
print(min_prefixes)  # -> ['abc', 'abd', 'acb']
hasprefix(min_prefixes, target)  # -> True

让我们进行一个必须失败的测试:

min_prefs_fail = ["abcde"]
hasprefix(min_prefs_fail, target)  # -> False

这样你就可以得到 O(n log(n)) 搜索，这比你的 O(n^2) 解决方案渐近更快。笔记!您可以(而且您确实应该)将 minimize_prefixes(sorted(comps)) 前缀集存储为对象中的属性，使任何前缀搜索 O(log (n))，这甚至更快比你现在拥有的。