Python 是子集性能与在集合中查找元素相比

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((，我会得到 36ms 的运行时间，这超过了所有提交的 94.87%。

3(所以我想，嗯，这件作品有什么区别？根据我在这个主题上找到的一个问题 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)

Answer 2

我已经测试了以下方法：

import random
import string
def checkWord1(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
def checkWord2(word):
    r1 = 'qwertyuiop'
    r2 = 'asdfghjkl'
    r3 = 'zxcvbnm'
    return set(word).issubset(r1) or set(word).issubset(r2) or set(word).issubset(r3)
def checkWord3(word):
    r1 = 'qwertyuiop'
    r2 = 'asdfghjkl'
    r3 = 'zxcvbnm'
    r = set(word)
    return r.issubset(r1) or r.issubset(r2) or r.issubset(r3)
def checkWord4(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

并测量执行时间：

word = ''.join(random.choice(string.ascii_lowercase) for _ in range(random.randint(0, 9)))
print("One:")
%timeit -n 10000 checkWord1(word)
print("Two:")
%timeit -n 10000 checkWord2(word)
print("Three:")
%timeit -n 10000 checkWord3(word)
print("Four:")
%timeit -n 10000 checkWord4(word)

获取结果：

One:
475 ns ± 88.1 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
Two:
708 ns ± 117 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
Three:
552 ns ± 19.6 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
Four:
1.19 µs ± 10.8 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

尽管使用不同的随机生成的字符串，但结果是相似的。

一个最快，三个比两个更快更稳定，四个最差。

我认为为什么一个人是最快的原因是

1. issubset(object)实际上隐式地将object转换为set。这是昂贵的。

2. 这种比较是不公平的。假设我们有一个词"qsdfwe"，在方法一中，它将检查是否在r1中，在下面的循环中，如果发现它不是r1的子集，它也不可能是其他的子集。

所以我实现了一个更快的方法，我认为我们可以只关注由第一个字符决定的一行，因为这三行是排他性的，所以我们不再检查其他行。

def checkWord5(word):
    r = ['qwertyuiop', 'asdfghjkl', 'zxcvbnm']
    first_char = word[0]
    row = r[0] if first_char in r[0] else r[1] if first_char in r[1] else r[2]
    for ch in word[1:]:
        if ch not in row:
            return False
    return True

获取结果：

One:
728 ns ± 236 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
Two:
2.08 µs ± 55.8 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
Three:
1.43 µs ± 60 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
Four:
1.45 µs ± 7.74 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
Five:
374 ns ± 7.01 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)