Pythonのパレートフロントの高速計算

Question

私はパレートのフロンティアを見つける必要がある3D空間にポイントのセットを持っています。ここでは実行のスピードが非常に重要であり、テストにポイントを追加すると時間が非常に長くなります。

点の集合は次のようになります。今

[[0.3296170319979843, 0.0, 0.44472108843537406], [0.3296170319979843,0.0, 0.44472108843537406], [0.32920760896951373, 0.0, 0.4440408163265306], [0.32920760896951373, 0.0, 0.4440408163265306], [0.33815192743764166, 0.0, 0.44356462585034007]] 

、私は、このアルゴリズムを使用しています：

ここで見つける

def dominates(row, candidateRow): 
    return sum([row[x] >= candidateRow[x] for x in range(len(row))]) == len(row) 

def simple_cull(inputPoints, dominates): 
    paretoPoints = set() 
    candidateRowNr = 0 
    dominatedPoints = set() 
    while True: 
     candidateRow = inputPoints[candidateRowNr] 
     inputPoints.remove(candidateRow) 
     rowNr = 0 
     nonDominated = True 
     while len(inputPoints) != 0 and rowNr < len(inputPoints): 
      row = inputPoints[rowNr] 
      if dominates(candidateRow, row): 
       # If it is worse on all features remove the row from the array 
       inputPoints.remove(row) 
       dominatedPoints.add(tuple(row)) 
      elif dominates(row, candidateRow): 
       nonDominated = False 
       dominatedPoints.add(tuple(candidateRow)) 
       rowNr += 1 
      else: 
       rowNr += 1 

     if nonDominated: 
      # add the non-dominated point to the Pareto frontier 
      paretoPoints.add(tuple(candidateRow)) 

     if len(inputPoints) == 0: 
      break 
    return paretoPoints, dominatedPoints 

：http://code.activestate.com/recipes/578287-multidimensional-pareto-front/

見つけるための最速の方法は何アンサンブルのソリューションで非支配ソリューションのセット？つまり、要するに、Pythonはこのアルゴリズムより優れていますか？

Answer 1

あなたが実際の速度心配している場合、あなたは間違いなく（賢いアルゴリズムの微調整は、おそらく配列操作を使用してから持っていたことが利益よりも道少ない効果を持っているとして）numpyの使用したいです。ここには2つの解決策があります。 "ダム" ソリューションは、ほとんどの状況では遅いですが、コストの数が増加するにつれて速くなった：

import numpy as np 


def is_pareto_efficient_dumb(costs): 
    """ 
    :param costs: An (n_points, n_costs) array 
    :return: A (n_points,) boolean array, indicating whether each point is Pareto efficient 
    """ 
    is_efficient = np.ones(costs.shape[0], dtype = bool) 
    for i, c in enumerate(costs): 
     is_efficient[i] = np.all(np.any(costs>=c, axis=1)) 
    return is_efficient 


def is_pareto_efficient(costs): 
    """ 
    :param costs: An (n_points, n_costs) array 
    :return: A (n_points,) boolean array, indicating whether each point is Pareto efficient 
    """ 
    is_efficient = np.ones(costs.shape[0], dtype = bool) 
    for i, c in enumerate(costs): 
     if is_efficient[i]: 
      is_efficient[is_efficient] = np.any(costs[is_efficient]<=c, axis=1) # Remove dominated points 
    return is_efficient 

プロファイリングテスト：

10000でサンプルを、2コスト：5000

dumb: Elapsed time is 0.9168s 
smart: Elapsed time is 0.004274s 

サンプル、15コスト：

dumb: Elapsed time is 1.394s 
smart: Elapsed time is 1.982s 

Answer 2

私はいくつかの調整をして同じアルゴリズムを書き直した。あなたの問題のほとんどはinputPoints.remove(row)から来たと思います。これはポイントのリストを検索する必要があります。索引で削除する方がはるかに効率的です。 また、冗長な比較を避けるためにdominates関数を変更しました。これはより高い次元では便利かもしれません。

def dominates(row, rowCandidate): 
    return all(r >= rc for r, rc in zip(row, rowCandidate)) 

def cull(pts, dominates): 
    dominated = [] 
    cleared = [] 
    remaining = pts 
    while remaining: 
     candidate = remaining[0] 
     new_remaining = [] 
     for other in remaining[1:]: 
      [new_remaining, dominated][dominates(candidate, other)].append(other) 
     if not any(dominates(other, candidate) for other in new_remaining): 
      cleared.append(candidate) 
     else: 
      dominated.append(candidate) 
     remaining = new_remaining 
    return cleared, dominated 

Answer 3

dominatesの定義が間違っています。 AはすべてのディメンションでBよりも優れているか等しい場合にのみBを支配し、少なくとも1つのディメンションでは厳密に優れています。