复杂的列表推导式比直接循环慢。

Question

复杂的列表推导式比直接循环慢。

3

我在leetcode上看到了一个有趣的编程练习解决方案。这甚至与问题/解决方案本身无关，因此如果您愿意，可以在提供的链接上阅读它。然而，一个高票的解决方案是这个一行代码:

片段 1

def fizzBuzz2(n):
    return  ["Fizz" * (not i%3) + "Buzz" * (not i%5) or str(i) for i in range(1, n+1)]

片段 2

def fizzBuzz(n):
    out = []
    for i in range(1, n+1):
        if i % 3 == 0 and i % 5 == 0:
            out.append("FizzBuzz")
        elif i % 3 == 0:
            out.append("Fizz")
        elif i % 5 == 0:
            out.append("Buzz")
        else:
            out.append(str(i))
            
    return out

然而，我预期列表推导式会比普通循环更快，但是当我计时时并不是这样。即使使用dis模块，Snippet 2 也有更多的指令。

是什么让 Snippet 1 变慢了？

- user1767754

1

我的测试表明片段2比较慢。顺便提一下，它里面有一个多余的“self”。 - Jean-François Fabre

1

字符串拼接与字面量字符串，但代码片段2执行了两倍于必要的%操作。 - Ry-

我目前无法自行检查，但是列表推导式是否可能检查所有语句，而if elif结构仅检查直到一个条件为真？ - mmensing

谢谢你的回复，你使用了一个很大的数字n吗？比如1000000？ - user1767754

我曾经对比较列表推导式和显式循环（3个数组生成器比1个for循环更快）进行过一些分析。你可能会发现它有用。 - Moinuddin Quadri

4个回答

2

很多人已经回答了你的问题，但我想补充一点，还有更快的解决方案。对我来说，在事后测试数字似乎是错误的，尽管你已经知道“Fizz”、“Buzz”和“FizzBuzz”出现的位置。请尝试以下方法：

def fizz_buzz(n):
    result = []
    for i in range(1, n + 1, 15):
        result += [str(i), str(i + 1), 'Fizz',
                   str(i + 3), 'Buzz', 'Fizz',
                   str(i + 6), str(i + 7), 'Fizz', 'Buzz',
                   str(i + 10), 'Fizz', str(i + 12), str(i + 13),
                   'FizzBuzz']
    return result[:n - len(result)]

start_time = time()
for i in range(10000):
    fizz_buzz(1000)
print("fizz_buzz:", time() - start_time)

与之前的答案相比：

your comp: 3.3942723274230957
my listcomp: 2.586350202560425
classical: 3.879168748855591
fizz_buzz: 1.6374053955078125

- seenorth

1

顺便提一下，您可以使用列表推导式和itertools.chain.from_iterable结合使用来加快速度：

result = list(itertools.chain.from_iterable([str(i), str(i + 1), 'Fizz', str(i + 3), 'Buzz', 'Fizz', str(i + 6), str(i + 7), 'Fizz', 'Buzz', str(i + 10), 'Fizz', str(i + 12), str(i + 13), 'FizzBuzz'] for i in range(1, n + 1, 15))) return result[:n - len(result)]

- Jean-François Fabre

1

[:n - len(result)] 不就是 [:n] 吗？ - Ry-

@Jean-FrançoisFabre 你确定吗？我已经用你的结果行替换了它，但是完成的时间要长得多。 - user1767754

1

是的，我已经测试过了，在我的机器上速度更快（哦，希望你已经移除了循环！！） - Jean-François Fabre

1

是的，因为在理解中，每次循环都会评估所有指令。

而在代码段2中，最多只评估1个if分支。因此，减少了计算量，使其成为更快的替代方案。

- xssChauhan

1

在我们探索实现的同时，这里有一个有趣的切片方法比单个列表推导式更快，但不如@seenorth的解决方案快：

from math import ceil


def fizz_buzz(n):
    result = list(range(n))
    result[::3] = ["Fizz"] * ceil(n / 3)
    result[::5] = ["Buzz"] * ceil(n / 5)
    result[::15] = ["FizzBuzz"] * ceil(n / 15)

    return list(map(str, result))

- Ry-

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jean-François Fabre · Accepted Answer

your snippet

def fizzBuzz2(n):
    return  ["Fizz" * (not i%3) + "Buzz" * (not i%5) or str(i) for i in range(1, n+1)]

该代码执行了大量字符串拼接操作（即使是空字符串）。我将其替换为额外的模运算，这样可以避免拼接操作并且速度更快。

def fizzBuzz3(n):
    return  ["FizzBuzz" if not i%15 else "Fizz" if not i%3 else "Buzz" if not i%5 else str(i) for i in range(1, n+1)]

顺便说一句，在我的机器上，这两种推导方式都比“传统”方法更快，所以我得到了不同于你所陈述的结果:

your comp: 4.927702903747559
my listcomp: 4.343341112136841
classical: 6.015967845916748

因此，我的优化列表推导式获胜了（并且在您的机器上似乎也是如此），即使我对列表推导控制流引入的额外模运算不满意。

我的测试协议使用n = 1000执行操作10000次：

import time
start_time = time.time()
for i in range(10000):
    fizzBuzz2(1000)
print("your comp:",time.time()-start_time)
start_time = time.time()
for i in range(10000):
    fizzBuzz3(1000)
print("my listcomp:",time.time()-start_time)
start_time = time.time()
for i in range(10000):
    fizzBuzz(1000)
print("classical:",time.time()-start_time)

请注意，即使使用“传统”方法预先计算模数，时间也会降至 5.375272035598755 秒（这很好），但仍然比列表推导式更差，因为存在大量指令（通过调用方法来保存模数计算也会降低列表推导式的速度）。我想在这种情况下 Python 不是获得最快速度的合适语言。