我怎样才能使下面的代码更快?输入是二进制字符串,我正在将其转换为数字。可能我需要使用二进制字符串而不是数字?该算法只能从输入中除以 2 或减去 1。我尝试了下面的代码,但速度不够快。
我尝试了以下:
def steps_to_zero(n) :
n=int(n,2)
count = 0
while n > 0:
if n % 2 == 0:
n = n // 2
else:
n = n - 1
count += 1
return (count)
它必须比这个快两倍:
def steps_to_zero_v1(x):
x_int = int(x,2)
steps = 0
while x_int != 0:
if x_int % 2 == 0:
x_int = x_int // 2
else:
x_int = x_int - 1
steps += 1
return steps
最佳答案
您建议的代码与给定的代码完全相同。
您想要加快速度的主要事情是摆脱昂贵的 if n % 2 == 0
测试。
解决方案是您可以在位级别上推理这个问题,而无需进行任何强力计算。
对于简单的情况n=0
,我们得到count=0
。对于下一个更简单的情况 n=1
,我们只需减去 1 一次,得到 count=1
。
在所有其他情况下,我们正在处理一些更长的二进制数。如果该数字的最后一位是 0
,我们可以除以 2 使我们的二进制数字更短:
...x0 / 2 = ...x # 1 step for 1 digit shorter
否则我们必须先减 1 才能除以二。
...x1 - 1 = ...x0
...x0 / 2 = ...x # 2 steps for 1 digit shorter
换句话说:对于最左边的 1,我们需要 1 次操作,对于所有数字,如果是 0 则需要 1,如果是 1 则需要 2。
这意味着您可以简单地通过计算字符串中 1 的数量来计算:
def steps_to_zero(n):
n = n.lstrip('0') # remove leading zeroes if they occur
divisions = len(n) - 1 # don't have to divide for the left-most 1
subtractions = n.count('1') # each 1 needs a subtraction to become a 0
return divisions + subtractions
% 2
和 .count('1')
平均超过 0-10,000 的时间比较:
# % 2
$ python3 -m timeit -s "x=list(range(10000))" "[y%2 for y in x]"
1000 loops, best of 3: 277 usec per loop
# .count('1')
$ python3 -m timeit -s "x=[bin(i) for i in range(10000)]" "[y.count('1') for y in x]"
1000 loops, best of 3: 1.35 msec per loop
尽管每次执行 .count('1')
比 %2
慢 ~5 倍,.count('1')
只需执行一次,而 %2
必须执行 log2(n) 次。这使得 .count('1')
方法在 n > 2**5 (=32)
时更快。
关于python - 根据 python 中的给定条件最小化 n 的最快方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55868851/