Python

Question

'da özel bir çok işlem kuyruğu gerçekleştirme Düzey 0'daki A, B, C, D, E, F düğümlerini içeren ters çevrilmiş bir ikili ağacı hayal edin. Düğüm G, H, I düzey 1, düğüm 2 Düzey 2, 3. seviyede ve düğümü K'dır

Seviye 1: G = işlev (A, B), H = işlev (C, D), J = işlev (E, F)

Seviye 2: J = işlev (G, H)

Seviye 3: K = func (J, I).

Düzey 0'daki her düğüm çifti sırayla işlenmelidir, 1. Seviyedeki her düğüm çifti herhangi bir sıraya göre işlenebilir, ancak sonuç sonraki seviyenin gösterildiği gibi işlenmeli ve sona erene kadar devam etmelidir Nihai sonuçla birlikte, K.

Asıl sorun, bir dizi katı maddenin birbirine kaynaştırıldığı bir hesaplama geometrisi problemidir. A, B'ye bitişik olan B'ye bitişiktir ve bu şekilde devam eder. Elde edilen A ve B (G) sigortası, C ve D (H) 'nin kaynağına bitişiktir. Elde edilen J ve I (K) sigortası son sonuçtur. Böylece, bitişik olmadıkları için G ve ben'i kaynaşamazsınız. Bir seviyedeki düğüm sayısı 2'nin gücü değilse, bir seviye ileride işlenmesi gereken sarkan bir varlıkla sonuçlanırsınız.

Sigorta işlemi hesaplama açısından pahalıdır ve bellek yoğun ama çok paralel olduğundan, Python çoklu işlem paketini ve bir sıra formunu kullanmak isterim. G = func (A, B) hesaplandıktan sonra, sonraki J = func (G, H) hesaplaması için G sonucunu sıraya itmek istiyorum. Sıra boş olduğunda, son sonuç son sonuçtur. Unutmayın ki mp.queue, FIFO sonucunu doğurmayacaktır çünkü I = func (E, F), H = func (C, D) 'dan önce bitirebilir. Birkaç (kötü) çözüm buldum. ama eminim ki kavrayışımın ötesinde zarif bir çözüm var. Öneriler?

Answer 1

Kuyrukta bir akıllı tasarımla gelemedim, ancak kuyruğu bir başka işlemle kolayca değiştirebilirsiniz, örneğimde WorkerManager. Bu işlem, tüm Worker işlemlerinin sonuçlarını toplar ve yalnızca işlenmeyi bekleyen iki bitişik veri paketi varsa yeni çalışanlar başlatır. Bu şekilde, hiçbir zaman bitişik olmayan sonuçlara katılmaya çalışamazsınız, böylece "seviyeleri" göz ardı edemezsiniz ve hazır olur olmaz bir sonraki çiftin hesaplamasını ateşleyebilirsiniz. Benim Örneğin

from multiprocessing import Process, Queue 

class Result(object): 
    '''Result from start to end.''' 
    def __init__(self, start, end, data): 
     self.start = start 
     self.end = end 
     self.data = data 


class Worker(Process): 
    '''Joins two results into one result.''' 
    def __init__(self, result_queue, pair): 
     self.result_queue = result_queue 
     self.pair = pair 
     super(Worker, self).__init__() 

    def run(self): 
     left, right = self.pair 
     result = Result(left.start, right.end, 
         '(%s, %s)' % (left.data, right.data)) 
     self.result_queue.put(result) 


class WorkerManager(Process): 
    ''' 
    Takes results from result_queue, pairs them 
    and assigns workers to process them. 
    Returns final result into final_queue. 
    ''' 
    def __init__(self, result_queue, final_queue, start, end): 
     self._result_queue = result_queue 
     self._final_queue = final_queue 
     self._start = start 
     self._end = end 
     self._results = [] 
     super(WorkerManager, self).__init__() 

    def run(self): 
     while True: 
      result = self._result_queue.get() 
      self._add_result(result) 
      if self._has_final_result(): 
       self._final_queue.put(self._get_final_result()) 
       return 
      pair = self._find_adjacent_pair() 
      if pair: 
       self._start_worker(pair) 

    def _add_result(self, result): 
     self._results.append(result) 
     self._results.sort(key=lambda result: result.start) 

    def _has_final_result(self): 
     return (len(self._results) == 1 
       and self._results[0].start == self._start 
       and self._results[0].end == self._end) 

    def _get_final_result(self): 
     return self._results[0] 

    def _find_adjacent_pair(self): 
     for i in xrange(len(self._results) - 1): 
      left, right = self._results[i], self._results[i + 1] 
      if left.end == right.start: 
       self._results = self._results[:i] + self._results[i + 2:] 
       return left, right 

    def _start_worker(self, pair): 
     worker = Worker(self._result_queue, pair) 
     worker.start() 

if __name__ == '__main__': 
    DATA = [Result(i, i + 1, str(i)) for i in xrange(6)] 
    result_queue = Queue() 
    final_queue = Queue() 
    start = 0 
    end = len(DATA) 
    man = WorkerManager(result_queue, final_queue, start, end) 
    man.start() 
    for res in DATA: 
     result_queue.put(res) 
    final = final_queue.get() 
    print final.start 
    # 0 
    print final.end 
    # 6 
    print final.data 
    # For example: 
    # (((0, 1), (2, 3)), (4, 5)) 

, ben bir virgülle ayırarak parantez içinde verilen verileri döndürür basit Worker kullanılan, ama orada herhangi hesaplama koyabilirsiniz. Benim durumumda, son sonuçidi ve bu da algoritmanın ((0, 1), (2, 3)) hesaplanmadan önce (0, 1) ve (2, 3) hesaplandığını ve daha sonra sonucu (4, 5) ile birleştirdiğini gösterir. Umarım aradığın şey budur.