如何更快地制作以下代码?输入是二进制字符串,我将其转换为数字。可能我需要使用二进制字符串而不是数字?算法只能从输入中除以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才能除以2。
...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)
接近更快。
不是将字符串转换为数字并执行昂贵的除法和模运算,而是简单地一点一点地处理它。对于除最左边一个之外的每个1
位,你需要两个步骤(减法和除法),并且对于每个0
位,你需要一步(除法):
def steps_to_zero(n):
count = 0
for x in n.lstrip('0'):
if x == '1':
count += 2
else:
count += 1
return count - 1
或者,如果您更喜欢单行:
def steps_to_zero(n):
return sum((x == '1') + 1 for x in n.lstrip('0')) - 1