python - MaxProductOfThree 如何提高性能

Question

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) 时间复杂度？你能解释一下吗？

Answer 1

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()