这是一个创建于 648 天前的主题，其中的信息可能已经有所发展或是发生改变。
做了 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 占用都不高但是运行的很慢，
迷思
- 如何提高本地运行速度
- leetcode 后台时如何实现 这种比较大的 loop test 的
5 条回复 • 2023-01-30 20:05:25 +08:00
 |
1
lixiang2017 2023-01-30 19:36:31 +08:00 via Android
每一题下面都是有数据规模的。
每一题能通过的算法复杂度都在 10^6 以内。复杂度再高的，无法通过。 时间上，按我经验，没有 6s 以上的。超过这个时间未返回结果，就 LTE 了 |
 |
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 应该没写错。 |
 |
3
hsfzxjy 2023-01-30 19:43:23 +08:00 via Android
1. 你需要优化掉重复的计算，比如在这个例子里每次循环_div_sum(i)跑了两次，但实际上只要一次就行了。另外_div_sum 中的循环只需从 2 到 sqrt(n)就能算出因子和。这些都是显而易见的优化。
2. 超时就杀掉。 |
 |
4
arischow 2023-01-30 19:56:22 +08:00
这跟「迷思」其实没什么关系
|
 |
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 ... 结合多线程等等 |
Select Language