列表中所有字符串的长度：最快的方法

Question

我正在努力：

python3 -m timeit -c 'len("".join([str(x) for x in range(0, 999999)]))'
10 loops, best of 3: 330 msec per loop

python3 -m timeit -c 'sum((len(y) for y in [str(x) for x in range(0, 999999)]))
10 loops, best of 3: 439 msec per loop

为什么会出现这种情况？有没有更快的方法？

附注假设会预先有一个字符串列表。

Answer 1

暂时忽略这个相当小的时间差异，实际上您的两种方式在记忆中有很大的差异。

sum((len(y) for y in [str(x) for x in range(0, 999999)]))

这将为每个数字创建一个字符串并将其存储在列表中。然后，您使用生成器表达式循环该列表并对长度求和。因此，实际上每个数字都有一个字符串，一个存储所有字符串的列表，以及一个要添加到长度的数字。

len(''.join([str(x) for x in range(0, 999999)]))

这将再次为每个数字创建一个字符串并将其存储在列表中。然后你创建一个包含所有数字的巨大字符串。然后你调用 length on in （这就是一个 O(1) 调用）。因此，您没有添加到的数字（同时将长度相加），但您确实有另一个长字符串，它再次组合了所有其他字符串。

因此，即使速度更快，您也会丢弃大量内存，这也可能会对以后的性能产生影响。

为了改善这一切，你应该考虑永久创建尽可能少的东西。不要使用列表推导式，因为这实际上会创建列表；不要使用

str.join

，因为这需要一个列表并迭代两次。

sum(len(str(x)) for x in range(0, 999999)))

现在，这仍然比

len(''.join(…))

方法慢，但不会有那么多内存开销。事实上，它一次只会创建一个字符串对象，获取其长度并将其添加到总和中。然后可以立即收集该字符串。

这仍然很慢的原因是，

len

和

str

都需要在生成器内部的每次迭代中查找。要加快速度，请使用

map

仅查找两次。 wim 在评论中提出了非常好的建议：

sum(map(len, map(str, range(999999))))

这实际上比我的

len(''.join(…))

方式执行得更快。我的时间安排结果按照我的答案中提到的顺序排列：

62.36836282166257
50.54277449168785
58.24419845897603
40.3403849521618

Answer 2

IPython 的更好基准显示情况比您想象的更糟糕：

>>> lst = [str(x) for x in range(0, 999999)]
>>> %timeit len("".join(lst))
100 loops, best of 3: 9.94 ms per loop
>>> %timeit sum(len(x) for x in lst)
10 loops, best of 3: 62.2 ms per loop

您在这里看到两个效果，Python 中函数调用的开销和迭代的开销。

"".join

两者都没有，因为它是在 C 中执行循环的单个方法调用。可以从

map

获得具有较少内存使用的中等性能：

>>> %timeit sum(map(len, lst))
10 loops, best of 3: 29.4 ms per loop

Answer 3

第一个（更快）版本有 1 次对

len

函数的调用，1 次对

join

的调用以及 100k 次对

str

的调用。查看第二行，您可以看到

len

和

str

都被调用了 100k 次，这使得第二种情况下函数调用总数大约是后者的两倍。

Answer 4

我们可以确定一种模式来计算从 0 到 n 的数字长度之和。

以999999为例

1位数字的个数=10（包括0）

2位数字的个数 = 90 = 99 - 10 + 1 （99是最大的2位数，10是最小的）

3位数的个数 = 900 = 999 - 100 + 1 ...

同样，我们可以计算特定位数的数字的个数。

使用它，我们可以将位数乘以具有这些位数的数字的数量，以获得它们的长度之和。

对于最后一种情况，上限可能不等于同位数的最大数。为了解决这个问题，我们可以单独添加它。

所以现在我们把问题简化为计算数字的数量。

n = 999999 # This could be any number

# Calculate the number of digits in n
d = len(str(n))

# Looping from 1 to d - 1 as all numbers will have to be included before 10^d
c = sum((i * 9 * 10 ** (i - 1) for i in range(1, d))) + 1

# Adding lengths of all d-digits number smaller than n (excluding)
c += (n - 10 ** (d - 1)) * d
print(c)

我们在 2.455611594719812e-06 秒内得到输出 5888884

对于 n = 123456789，我们在 3.338770055794157e-06 秒内得到输出 999999991