在Python中优化Pareto前端过滤

Question

我正在尝试(再次尝试：Fast calculation of Pareto front in Python)过滤列表列表，以便只保留非支配集。

我整理了一个最终对我有效的脚本：

import operator
import copy
import time
import random

def select_dominated(a,b):
    ge = all(map(operator.ge, a, b))
    le = all(map(operator.le, a, b))
    # return dominated
    return b if ge else a if le else 'indifferent'

def paretoFront(a):
    b = copy.deepcopy(a)
    if len(a) > 1:
        for i in range(len(a)):
            for j in range(i,len(a)):
                if i != j:
                    try:
                        b.remove(select_dominated(a[i],a[j]))
                    except:
                        ""
    return b

set = []
for i in range(1000):
    set.append([random.random(),random.random(),random.random()])

t0 = time.time()
print len(set),"->",len(paretoFront(set)),"in",time.time()-t0,"seconds"

预计，对于大型列表，它相当慢(3秒。以过滤1000个3d点)。我听说“移除”相当慢。我该如何优化这段代码呢？

Answer 1

(免责声明:我不太了解什么是Pareto前端，所以我根据您提供的内容推断出代码是什么。)

因为这是纯Python语言(即不使用外部库)，所以大部分时间将花费在迭代上(您的for循环)。

我有两个建议。

首先，看看你的代码是否可矢量化。例如，您可能希望将数据表示为numpy数组。不知羞耻地从here复制代码，您可能想要这样做：

def pareto_frontier_multi(myArray):
    # Sort on first dimension
    myArray = myArray[myArray[:,0].argsort()]
    # Add first row to pareto_frontier
    pareto_frontier = myArray[0:1,:]
    # Test next row against the last row in pareto_frontier
    for row in myArray[1:,:]:
        if sum([row[x] >= pareto_frontier[-1][x]
                for x in range(len(row))]) == len(row):
            # If it is better on all features add the row to pareto_frontier
            pareto_frontier = np.concatenate((pareto_frontier, [row]))
    return pareto_frontier

my_array = np.random.random((3, 1000))
pareto_frontier_multi(my_array)

numpy使用矢量化来提供加速。

其次，如果您想坚持使用纯Python，那么可以尝试PyPy。下载PyPy可执行二进制文件，让bash终端识别它们的位置(通过编辑bash shell PATH变量)，然后在PyPy下执行代码。我已经写了一个blog post，它可以向你展示PyPy的加速效果。本质上，没有每次迭代类型检查的开销，您的循环将运行得更快。这几乎就像是矢量化，尽管它们是不同的。