MaxProductOfThree 类(class):https://app.codility.com/programmers/lessons/6-sorting/max_product_of_three/
为了解决这个 Codility 类(class),我编写了这个函数,如下所示;
import itertools
def solution(A):
combs=[]
for pivot_element in A:
to_comb=A[A.index(pivot_element):]
for comb in itertools.combinations(to_comb, 3):
mul_comb= comb[0] * comb[1] * comb[2]
combs.append(mul_comb)
return max(combs)
我的结果是,
result_of_algorithm={
"correctness":100,
"performance":0,
"overall":44,
"time complexity": "O(N^3)"
}
如何将其性能提高到 O(n) 时间复杂度?你能解释一下吗?
最佳答案
O(n) 版本的 schwobaseggl 的解决方案,也得到了 100%:
from heapq import nsmallest, nlargest
def solution(A):
a, b = nsmallest(2, A)
z, y, x = nlargest(3, A)
return max(a*b*z, x*y*z)
具有最大允许大小写的基准(从 -1000 到 1000 的 100,000 个值):
204 ms 206 ms 208 ms 210 ms 212 ms sort
76 ms 77 ms 78 ms 79 ms 81 ms heapq
134 ms 135 ms 135 ms 135 ms 136 ms oneloop
144 ms 146 ms 147 ms 149 ms 151 ms twoloops
3 ms 3 ms 3 ms 3 ms 4 ms baseline
基准代码(Try it online!):
from timeit import repeat
from random import choices
from heapq import nsmallest, nlargest
import sys
def sort(A):
A.sort()
p1 = A[0] * A[1] * A[-1]
p2 = A[-3] * A[-2] * A[-1]
return max(p1, p2)
def heapq(A):
a, b = nsmallest(2, A)
z, y, x = nlargest(3, A)
return max(a*b*z, x*y*z)
def oneloop(A):
min1 = sys.maxsize * 2
min2 = sys.maxsize * 2
max1 = -sys.maxsize * 2
max2 = -sys.maxsize * 2
max3 = -sys.maxsize * 2
for Ai in A:
if Ai <= min1:
min2 = min1
min1 = Ai
elif Ai <= min2:
min2 = Ai
if Ai >= max1:
max3 = max2
max2 = max1
max1 = Ai
elif Ai >= max2:
max3 = max2
max2 = Ai
elif Ai >= max3:
max3 = Ai
return max([min1 * min2 * max1, max1 * max2 * max3])
def twoloops(A):
min1 = sys.maxsize * 2
min2 = sys.maxsize * 2
max1 = -sys.maxsize * 2
max2 = -sys.maxsize * 2
max3 = -sys.maxsize * 2
for Ai in A:
if Ai <= min1:
min2 = min1
min1 = Ai
elif Ai <= min2:
min2 = Ai
for Ai in A:
if Ai >= max1:
max3 = max2
max2 = max1
max1 = Ai
elif Ai >= max2:
max3 = max2
max2 = Ai
elif Ai >= max3:
max3 = Ai
return max([min1 * min2 * max1, max1 * max2 * max3])
def baseline(A):
pass
funcs = sort, heapq, oneloop, twoloops, baseline
for _ in range(3):
A = choices(range(-1000, 1001), k=100_000)
for func in funcs:
times = sorted(repeat(lambda: func(A[:]), number=10))
print(*('%3d ms ' % (t * 1e3) for t in times), func.__name__)
print()
https://stackoverflow.com/questions/68994984/