Python difflib的比率，quick_ratio和real_quick_ratio

Question

我一直在使用difflib的SequenceMatcher，

而且我发现该ratio功能太慢了。通过阅读文档，我发现quick_ratio和real_quick_ratio那应该是更快（顾名思义），并作为上限。

但是，文档缺少对它们所做的假设或所提供的加速的描述。

我什么时候应该使用任何一个版本，我应该牺牲什么？

Answer 1

看一看

从辅助方法开始 _calculate_ratio

def _calculate_ratio(matches, length):
    if length:
        return 2.0 * matches / length
    return 1.0

比率

ratio 查找匹配项，并将其除以两个字符串的总长度乘以 2：

    return _calculate_ratio(matches, len(self.a) + len(self.b))

速动比率

这实际上是源评论所说的：

    # viewing a and b as multisets, set matches to the cardinality
    # of their intersection; this counts the number of matches
    # without regard to order, so is clearly an upper bound

进而

    return _calculate_ratio(matches, len(self.a) + len(self.b))

real_quick_ratio

real_quick_ratio 找到最短的字符串，除以字符串的总长度乘以 2：

    la, lb = len(self.a), len(self.b)
    # can't have more matches than the number of elements in the
    # shorter sequence
    return _calculate_ratio(min(la, lb), la + lb)

这是真正的上限。

结论

real_quick_ratio 不查看字符串以查看是否有任何匹配项，它仅根据字符串长度计算上限。

现在，我不是算法专家，但如果您认为ratio完成工作太慢，我建议使用quick_ratio，因为它可以充分处理问题。

效率注意事项

从文档字符串

    .ratio() is expensive to compute if you haven't already computed
    .get_matching_blocks() or .get_opcodes(), in which case you may
    want to try .quick_ratio() or .real_quick_ratio() first to get an
    upper bound.