V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
srivendare
V2EX  ›  问与答

一个非科班程序猿,关于 Python 提速的迷思

  •  
  •   srivendare · 2023-01-30 18:54:38 +08:00 · 877 次点击
    这是一个创建于 663 天前的主题,其中的信息可能已经有所发展或是发生改变。

    做了 2 年程序员,目前在刷 leetcode, 发现了一个问题 例如

    
    def solution(num):
    numFriends = 0
       for i in range(1,num):
           divSum = self._div_sum(i)
           if (i%50000 == 0): print(i)
           if self._are_equivalent(i):
             if i < divSum:
             	numFriends+=1
       return numFriends
         
     def _are_equivalent(n):
        return (n == self._div_sum(_div_sum(n)))
    
     def _div_sum(n):
       divisors = [1]
       for i in range(2, n):
           if (n % i)==0:
               divisors.append(i)
       return sum(divisors)
    

    当测试答案输入 num 为 10000 时代码运行 8s 出结果,而 20000 时 34s ;当输入为 100w 的时候虽然电脑的内存和 cpu 占用都不高但是运行的很慢,

    迷思

    1. 如何提高本地运行速度
    2. leetcode 后台时如何实现 这种比较大的 loop test 的
    5 条回复    2023-01-30 20:05:25 +08:00
    lixiang2017
        1
    lixiang2017  
       2023-01-30 19:36:31 +08:00 via Android
    每一题下面都是有数据规模的。
    每一题能通过的算法复杂度都在 10^6 以内。复杂度再高的,无法通过。
    时间上,按我经验,没有 6s 以上的。超过这个时间未返回结果,就 LTE 了
    hertzry
        2
    hertzry  
       2023-01-30 19:41:58 +08:00
    _div_sum()函数只需循环到 n**0.5 + 1 即可。

    import time
    start = time.time()
    def _div_sum(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
    if (n % i)==0:
    divisors.append(i)
    divisors.append(n/i)
    return sum(divisors)-n

    for i in range(1, 10000):
    _div_sum(i)

    end = time.time()
    print(end - start)
    # 0.06

    start = time.time()

    def _div_sum(n):
    divisors = [1]
    for i in range(2, n):
    if (n % i)==0:
    divisors.append(i)
    return sum(divisors)
    for i in range(1, 10000):
    _div_sum(i)

    end = time.time()
    print(end - start)
    # 3.23

    应该没写错。
    hsfzxjy
        3
    hsfzxjy  
       2023-01-30 19:43:23 +08:00 via Android
    1. 你需要优化掉重复的计算,比如在这个例子里每次循环_div_sum(i)跑了两次,但实际上只要一次就行了。另外_div_sum 中的循环只需从 2 到 sqrt(n)就能算出因子和。这些都是显而易见的优化。

    2. 超时就杀掉。
    arischow
        4
    arischow  
       2023-01-30 19:56:22 +08:00
    这跟「迷思」其实没什么关系
    NoOneNoBody
        5
    NoOneNoBody  
       2023-01-30 20:05:25 +08:00
    1.没必要不要在循环内 print
    2.没必要不要累加,循环后一次 sum
    3.简单的 for 改成循环表达式
    4.这个_div_sum(i)跑了多少次?用 funtools.cache 或者只算一次,存入字典,后面读取就是
    ...
    自然数列,规律性强,很适合各种并发的工具,例如 pandas+dask, bisect, itertools ... 结合多线程等等
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1045 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 20ms · UTC 23:20 · PVG 07:20 · LAX 15:20 · JFK 18:20
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.