Python issubset 与在集合中查找元素的性能比较

Question

我在 Leetcode(500 键盘行)上进行编程练习，并在讨论中遇到了 set.issubset()。与我自己的答案进行比较后，有一个有趣的发现:

1)

def checkWord(self, word):
    r1 = 'qwertyuiop'
    r2 = 'asdfghjkl'
    r3 = 'zxcvbnm'
    row = 0
    for idx, ch in enumerate(word):
        if idx == 0:
            row = 1 if ch in r1 else 2 if ch in r2 else 3
            continue
        coming_row = 1 if ch in r1 else 2 if ch in r2 else 3
        if row != coming_row:
            return False
    return True

如果我用这个提交，我会得到 40 毫秒的运行时间

2)

def checkWord(self, word):
    r1 = 'qwertyuiop'
    r2 = 'asdfghjkl'
    r3 = 'zxcvbnm'
    return set(word).issubset(r1) or set(word).issubset(r2) or set(word).issubset(r3)

如果我使用 issubset()，我得到的运行时间为 36 毫秒，超过了所有提交的 94.87%。

3)所以我想，嗯，这件作品有什么不同？根据我在这个主题上发现的一个问题The complextiy of Python issubset() ，方法2)的时间复杂度应该是O(len(word))，我相信这应该和这篇文章一样:

def checkWord(self, word):
    r1 = set('qwertyuiop')
    r2 = set('asdfghjkl')
    r3 = set('zxcvbnm')
    row = 0
    for idx, ch in enumerate(word):
        if idx == 0:
            row = 1 if ch in r1 else 2 if ch in r2 else 3
            continue
        coming_row = 1 if ch in r1 else 2 if ch in r2 else 3
        if row != coming_row:
            return False
    return True

然而，它的运行时间是 32 毫秒，比所有 py3 提交的 100% 都快……为什么 issubset() 比这个慢？谢谢!

Answer 1

请注意，您的 checkWord 函数的第一个版本不会检查 ch 值是否在 r3 集中，因此您可以避免一次检查。

此外，在 checkword 的第二个版本中，您使用 word 参数的字符三次创建一个集合。为什么不在使用“issubset”检查之前存储该集合？你的代码将是这样的:

def checkWord3(word):
    r1 = 'qwertyuiop'
    r2 = 'asdfghjkl'
    r3 = 'zxcvbnm'
    s1 = set(word)
    return s1.issubset(r1) or s1.issubset(r2) or s1.issubset(r3)

这是使用正则表达式的另一种解决方案:

r1 = re.compile("^[qwertyuiop]+$")
r2 = re.compile("^[asdfghjkl]+$")
r3 = re.compile("^[zxcvbnm]+$")

r1.match(word) or r2.match(word) or r3.match(word)