Python'daki Pareto önünün hızlı hesaplanması

Question

Pareto sınırını bulmam gereken bir 3B boşluğa sahip bir dizi noktam var. Burada icra etme hızı çok önemlidir ve test etmek için puan ekledikçe zaman çok hızlı artar.

noktaları kümesi aşağıdaki gibidir:

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 

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

ulaşmanın en kısa yolu nedir, bu algoritmayı kullanıyorum Şu anda

[[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]] 

Bir çözüm grubu içinde dominant olmayan çözümler kümesi? Ya da kısaca Python bu algoritmadan daha iyisini yapabilir mi?

Answer 1

gerçek hızı hakkında endişeleniyorsanız, kesinlikle (zeki algoritmik ince ayarlar muhtemelen dizi işlemlerini kullanmaktan vardı edilecek kazanımlar çok daha az etkiye sahip gibi) numpy kullanmak istiyorum. İşte iki çözüm. "Aptal" çözüm çoğu durumda yavaştır ama maliyetler sayısı arttıkça daha hızlı olur:

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 

profil oluşturma testler:

10000 ile numuneler, 2 maliyetleri: 5000 ile

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

numuneler, 15 maliyeti:

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

Answer 2

Aynı algoritmayı bir çift tweaks ile yeniden yazmak için bir çekim yaptım. Sorunlarınızın çoğunun inputPoints.remove(row)'dan geldiğini düşünüyorum. Bu, puan listesinden arama yapılmasını gerektirir; endeksle kaldırmak çok daha verimli olacaktır. Bazı yedekli karşılaştırmaları önlemek için dominates işlevini de değiştirdim. Bu daha yüksek bir boyutta kullanışlı olabilir.

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 tanımı yanlıştır. A, eğer sadece tüm boyutlarda B'ye eşit ya da eşitse ve en az bir boyutta kesinlikle daha iyi olursa B'ye egemen olur.