哪种方法更快，为什么？

Question

我正在解决寻找最大数的问题。我知道这个问题的解决方案，但我无法理解连接两个数字的不同方法是否会在运行时间内产生任何差异。我正在使用 python 3.7.

Method 1

将两个数字转换为字符串并将它们连接起来，然后将它们转换回整数。

def concatenate(num1, num2):
    num1 = str(num1)
    num2 = str(num2)
    num1 += num2
    return int(num1)

Method 2

计算其中一个数字的位数并在另一个数字中添加相同数量的零。

def concatenate(num1, num2):
    digits = len(str(num2))
    num1 = num1 * (10**digits)
    num1 += num2
    return num1

技术上的差异有什么区别吗？转换字符串或算术运算（乘法）中的数字哪个更快，为什么？更改为另一种语言会有什么不同，例如基于编译器的语言 (C++)？

编辑：

Method 1 - Execution time 6.604194641113281e-05 seconds

Method 2 - Execution time 5.245208740234375e-06 seconds

数据类型转换花费的时间更多，但为什么会这样，是否仅适用于像 python 这样的解释型语言而不适用于像 C++ 这样的基于编译器的语言？

Answer 1

当然会有不同！自己看看很容易：

import timeit

def concatenate1(num1, num2):
    num1 = str(num1)
    num2 = str(num2)
    num1 += num2
    return int(num1)

def concatenate2(num1, num2):
    digits = len(str(num2))
    num1 = num1 * (10**digits)
    num1 += num2
    return num1


num1 = int("1"*10000)
num2 = int("2"*10000)

t1 = timeit.timeit('concatenate1(num1, num2)', 'from __main__ import concatenate1, num1, num2', number=100)
t2 = timeit.timeit('concatenate2(num1, num2)', 'from __main__ import concatenate2, num1, num2', number=100)

print("t1=", t1, "; t2=", t2)
# Output:
# t1= 0.772663099996862 ; t2= 0.30340000000433065

显然，t1 是 t2 的约 2 倍。也许大量的时间消耗正在将数字字符串化？让我们尝试另一个使用 math.log10 计算位数的实现：

import math
def concatenate3(num1, num2):
    l = math.log10(num2)
    digits = int(l) + 1
    num1 = num1 * (10**digits)
    num1 += num2
    return num1

将此函数与其他两个函数结合使用可得到：

t1= 0.8134238999919035 ; t2= 0.32444419999956153 ; t3= 0.11973479999869596

这似乎支持将整数转换为字符串需要花费大量时间的论点。

为什么会这样？因为将整数转换为字符串需要使用十进制数字解释存储中的二进制值，然后为每个数字分配字符。将两个数字相加时，您只需将它们的二进制数字相加即可。

您将在编译的和解释语言中看到这种行为。然而，不同的语言将有不同程度的减速与不同的方法相关，这取决于它们的内部工作方式。

Answer 2

虽然@pranav-hosangadi 提供的答案很棒，但我赞同他的说法，即会有不同。

我想指出的是，针对一组输入的“best/fastest”解决方案可能并非对所有输入都是最佳解决方案。在寻找更好/更快的解决方案时，了解您的输入数据“看起来”很重要。

对于@pranav-hosangadi 选择的输入（非常大的数字串），他的 concatenate3() 显然是最快的。他们的输入选择似乎非常合理，因为问题是关于确定“大”数字的事情。

但是，如果问题是定义最多十位数的大数（在某些情况下仍然很大），那么他们的 concatenate3() 方法实际上比前两种方法和第四种方法慢:

def concatenate4(num1, num2):
    return int(f"{num1}{num2}")

比所有三个都快（至少在我的笔记本电脑上）。

同样重要的是，这个新的 concatenate4() 并不是普遍更快，并且对于 @pranav-hosangadi 使用的范围内的输入，它的表现“很差”。而他们的 concatenate3() 压倒了其他人。

import timeit
import math

def concatenate1(num1, num2):
    num1 = str(num1)
    num2 = str(num2)
    num1 += num2
    return int(num1)

def concatenate2(num1, num2):
    digits = len(str(num2))
    num1 = num1 * (10**digits)
    num1 += num2
    return num1

def concatenate3(num1, num2):
    l = math.log10(num2)
    digits = int(l) + 1
    num1 = num1 * (10**digits)
    num1 += num2
    return num1

def concatenate4(num1, num2):
    return int(f"{num1}{num2}")

num1 = int("1"*10)
num2 = int("2"*10)

t1 = timeit.timeit('concatenate1(num1, num2)', 'from __main__ import concatenate1, num1, num2', number=1000)
t2 = timeit.timeit('concatenate2(num1, num2)', 'from __main__ import concatenate2, num1, num2', number=1000)
t3 = timeit.timeit('concatenate3(num1, num2)', 'from __main__ import concatenate3, num1, num2', number=1000)
t4 = timeit.timeit('concatenate4(num1, num2)', 'from __main__ import concatenate4, num1, num2', number=1000)

print("t1=", 100_000*t1, "; t2=", 100_000*t2, "; t3=", 100_000*t3, "; t4=", 100_000*t4)

结果：

t1= 63.25999999999971 ; t2= 58.6299999999998 ; t3= 64.32999999999994 ; t4= 40.889999999999674

在我的笔记本电脑上，concatinate3() 只有在组合每个数字超过 35 位的数字时才会变得最快。

让我们试着回答为什么：

让我们来看看 concatenate3() 和 concatenate4() 各个步骤的粗略时间安排。请注意，各个步骤的真实成本被函数调用开销所掩盖，因此是粗略的近似值，但它们仍然基于实际时序测试并说明了一个有趣的点。

对于超过 1000 次运行的 10 位数字 concatenate3():

def concatenate3(num1, num2):  # 59 time units (accurate)
    l = math.log10(num2)       # 18 time units
    digits = int(l) + 1        # 14 time units
    num1 = num1 * (10**digits) # 12 time units
    num1 += num2               #  7 time units
    return num1

对于超过 1000 次运行的 10 位数字 concatenate4():

def concatenate4(num1, num2):  # 45 time units (accurate)
    tmp = f"{num1}{num2}"      # 30 time units
    tmp = int(tmp)             # 20 time units
    return tmp

对于超过 1000 次运行的 1000 位数字 concatenate3():

def concatenate3(num1, num2):  # 1400 time units (accurate)
    l = math.log10(num2)       #   23 time units
    digits = int(l) + 1        #   15 time units
    num1 = num1 * (10**digits) # 1341 time units
    num1 += num2               # 2119 time units
    return num1

对于超过 1000 次运行的 1000 位数字 concatenate4():

def concatenate4(num1, num2):  # 5700 time units (accurate)
    tmp = f"{num1}{num2}"      # 3500 time units
    tmp = int(tmp)             # 3100 time units
    return tmp

那么，我们能看到什么？首先，乘法和加法本质上比连接和转换更快。这应该不足为奇。

有趣的是，虽然计算 digits 的成本与输入的大小无关，并且随着输入的增加而消失在舍入误差中，而对于较小的输入，该成本成为总成本的重要组成部分。

哪种方法更快，为什么？

Which method is faster and why?

string

algorithm

concatenation

type-conversion

python-3.x