447 Python不同的实现，时间差别很大的原因？

Question

447 回旋镖的数量。我自己写的代码如下，时间1100ms左右。

def numberOfBoomerangs(self, points: List[List[int]]) -> int:
	from collections import defaultdict
	rlt = 0
	for p1 in points:
	    dic = defaultdict(int)
	    for p2 in points:
	        d = (p1[0] - p2[0])**2 + (p1[1] - p2[1])**2
	        dic[d] += 1
	    for v in dic.values():
	        if v > 1:
	            rlt += v * (v - 1)   
	return rlt

下面的代码是用时排名中，最快的示例，时间350ms左右。

def numberOfBoomerangs(self, points: List[List[int]]) -> int:
    rlt = 0
    for x1, y1 in points:
        dic = {}
        for x2, y2 in points:
            dx = x1 - x2
            dy = y1 - y2
            d = dx*dx + dy*dy
            if d in dic:
                rlt += dic[d]
                dic[d] += 1
            else:
                dic[d] = 1
    return rlt*2

本来我以为区别在最后对dic.values()多循环遍历了一次，改完后发现并没有太多区别，只提高了一点点，930ms左右（这里提高的时间，我觉得应该是来自于下面第(2)问）

（1）经过我反复实验，最后发现，关键点在d的计算上，时间上：d = (p1[0] - p2[0])**2 + (p1[1] - p2[1])**2 远大于 d = (p1[0] - p2[0])×(p1[0] - p2[0]) + (p1[1] - p2[1])×(p1[1] - p2[1]) 大于 d = dxdx + dydy(已分别计算出dx,dy)。这是什么原因呢？
另外，使用defaultdict，dict()，dic={}没有太大区别。

（2）在使用defaultdict下，最后的代码可以简写为如下形式。我发现简写后的代码，比引号内的代码慢150-200ms左右。

    """
    if d in dic:
        rlt += dic[d]
        dic[d] += 1
    else:
        dic[d] = 1
    """
    # 简写之后
    if d in dic:
        rlt += dic[d]
    dic[d] += 1

Answer 1

liuyubobobo 2021-09-12 03:07:38

我不是 python 专家，但是几个点随便说一下：

1）

for x1, y1 in points:

这种遍历中解包要比 for p1: points 之后调用 p1[0], p1[1] 快。

2）

if d in dic:
    rlt += dic[d]
dic[d] += 1

只是代码看似更简洁了。但是 dic[d] += 1 是比 dic[d] = 1 慢的，这是因为 dic[d] += 1 本质是 dic[d] = dic[d] + 1，需要先找到 dic[d]，再 +1，再将结果赋回给 dic[d]。而 dic[d] = 1 直接将 1 给 dic[d]，是更快的。在只需要赋值的时候，只做一步 dic[d] = 1 是更快的。

3）

我测试 Leetcode 的 Python 3 编译器，性能非常不稳。你给出的 350 ms 的代码，我这里提交也有 900 ms 的时候；

4）

另外，非常重要的，这两个代码，使用 Python 3 编译器确实有你说的差距，但是我尝试使用 Leetcode 的 Python 编译器，他们之间的差距没有那么大。我不确定 Leetcode 的 Python3 编译器的设置是否有可以优化的地方。（比如之前 Leetcode 的 C++ 编译就不开 -o2 优化，导致 C++ 比 Java 还慢，后来改掉了。）不过对于这一点，我不是 Python 专家，没有研究过 Python 编译器的设置。

5）

对于为什么 x**2 + y**2 会显著慢于 x*x + y*y，我也不了解。但鉴于 3),4)，我建议你先在本地调试，使用不同的编译器设置测试一下，看是否有这个结论？

如果还有这个结论，使用 C++ 或者 Java 调试这种性能问题的一个思路是看他们生成的汇编码或者字节码是否有显著的 区别，道理上 Python 也会有类似的工具或者方式，但是依然是，我不是 Python 专家，对此不很了解。

6）

最后吐槽一句，这就是我一直说的，不建议使用解析型语言做强性能相关的任务的原因，因为其性能对解析器的依赖巨大，一点点写法上的改变，而非算法上的改变，就会引来巨大的性能差异。这也是为什么人工智能这类领域 Python 主要是做模型探索，真要 deliver 的话，近乎一水儿的 C++。numpy, sklearn, tf 这类库或者框架底层也是大量的 C/C++ 代码，Python 更多地是充当包装的角色。

不是说 C++ 或者 Java 没有这样的问题，但是这样的问题小太多太多。

另外。理论上，Python 社区里对这样的问题是有解决方案的，比如我听说的，使用 pypy 就对此改善巨大。不过 Leetcode 不支持 pypy，codeforces 就支持。

但不管怎样，更深入的对这个问题的分析，需要在 Python 社区讨论了。我不是 Python 专家。

继续加油！：） 

• 提问者 慕的地7544270 #1

  谢谢老师回答！
  对于(5): 我用本地的pycharm，按照题目规定的取值范围，随机生成了含有32个测试用例的数组。
  用这个数组测试上述几种写法。发现 x**2 + y**2 还是显著慢于 x*x + y*y的代码：
  上述350ms代码在本地平均用时1s左右，该代码仅改动d的计算为 d = (x1-x2)**2 + (y1-y2)**2，我发现稳定性变差很多，平均时间也变为1.9s左右。上述1100ms的代码在本地2.6s左右。
  其他的解释器和调试工具，我没有研究过，先去了解一下，再来试试这个问题。