JavaScript: Jak kontrolować przepływ za pomocą asynchronicznego drzewa rekurencyjnego?

Question

Potrzebuję rekurencji na drzewie, aby wykonywać operacje na określonych węzłach przy użyciu operacji asynchronicznych. Jak kontrolować przepływ, aby mieć dostęp do węzłów po zakończeniu?

Oto przykład sytuacja:

data = { 
    name: "deven", 
    children: [ 
    { name: "andrew" }, 
    { name: "donovan" }, 
    { name: "james", 
     children: [ 
     { name: "donatello" }, 
     { name: "dan" } 
     ] 
    }, 
    { name: "jimmy", 
     children: [ 
     { name: "mike" }, 
     { name: "dank" } 
     ] 
    } 
    ] 
}; 

Mam funkcję, kto jest celem jest iterację drzewa i wykorzystać wszystkie nazwy, które zaczynają się od „d”. Następnie chcę przekazać drzewa do innej funkcji, aby zrobić trochę więcej pracy (ewentualnie usunąć wszystkie węzły, które mają nazwę, która zaczyna się od „A”), ale tylko po początkowym przetwarzanie zostało zrobione:

function capitalize_d(node) { 
    if(node.name === "d") { 
     node.name = node.name.toUpperCase(); 
    } 

    if(node.children != null) { 
     for(var i = 0; i < node.children.length; i++) { 
      capitalize_d(node.children[i]); 
     } 
    } 
} 

function remove_a(node) { 
} 

capitalize_d(data); 

// Should only get called after all the d's have been capitalized. 
remove_a(data); 

Powyższy kod działa poprawnie, ponieważ capitalize_d jest blokowany. Jeśli capitalize_d powtarza się asynchronicznie, w jaki sposób możemy zagwarantować, że remove_a zostanie wywołany po zakończeniu? Uwaga: wywołanie setTimeout wywołanie w wywołanie w .

function capitalize_d(node) { 
    setTimeout(function() { 

     if(node.name === "d") { 
      node.name = node.name.toUpperCase(); 
     } 

     if(node.children != null) { 
      for(var i = 0; i < node.children.length; i++) { 
       capitalize_d(node.children[i]); 
      } 
     } 

    }, 1); 
} 

function remove_a(node) { 
} 

capitalize_d(data); 

// Should only get called after all the d's have been capitalized. 
remove_a(data); 

Problem polega mamy przetwarzania dla różnych gałęzi drzewa wszystko wyrzucenie off w tym samym czasie, a nie da się powiedzieć, kiedy to wreszcie zrobić obróbki drzewa.

Jak mogę to rozwiązać?

Answer 1

Pozwól mi podsumować to, co zrozumiałem z twoich wymagań:

• masz drzewo danych, gdzie każdy pojedynczy węzeł może być zmieniony asynchronicznie przez zbiór operacji (capitalize_d i remove_a w swoim przykładzie),
• chcesz upewnić się, że każdy węzeł został poddany danej operacji przed zezwoleniem na następny.

Spędziłem 10 lat lub więcej projektowaniu czasie rzeczywistym oprogramowania wbudowanego, a wierzcie mi, wymagania w tym zakresie są meaner i scarrier niż cokolwiek większość programistów sieciowych będzie doświadczać w całym swoim życiu. To sprawia, że ​​ostrzegam cię, że wydajesz się kierować poważnie złą drogą.

Jak mogę sobie wyobrazić, twoim problemem jest uporządkowanie zbioru pojedynczych danych w jakiejś znaczącej strukturze. W niektórych procesach zbierane są losowe bity informacji (tak zwane "węzły" w twoim przykładzie) iw pewnym momencie chcesz umieścić wszystkie te węzły w spójnej, monolitycznej strukturze danych (hierarchiczne drzewo w twoim przykładzie).

Innymi słowy, masz trzy zadania pod ręką:

• procesu pozyskiwania danych, które będą zbierać węzły asynchronicznie
• procesu produkcyjnego danych, który przedstawi spójny, wyrafinowane drzewa danych
• proces kontrolera, który synchronizuje pozyskiwanie i produkcję danych (ewentualnie bezpośrednio interfejs użytkownika, jeśli dwa powyższe procesy są wystarczająco inteligentne, ale nie licz na to zbyt wiele).

Moja rada: nie próbuj robić zakupu i produkcji w tym samym czasie.

Wystarczy dać wyobrażenie o koszmarze jesteś udaliśmy się do:

• w zależności od sposobu działania są wyzwalane, istnieje możliwość, że drzewo nigdy nie będzie całkowicie przetwarzane przez danego działania . Powiedzmy, że oprogramowanie sterujące zapomina zadzwonić capitalize_d na kilku węzłach, remove_a po prostu nie dostać zielone światło

• odwrotnie, jeśli ogień na drzewie w sposób losowy, to jest bardzo prawdopodobne, że niektóre węzły dostanie przetwarzane wielokrotnie , chyba śledzić zasięgu działania, aby zapobiec stosowaniu samej transformacji dwukrotnie na danym węźle

• jeśli chcesz remove_a przetwarzanie kiedykolwiek zacząć, może trzeba zapobiec oprogramowania sterującego wysyłać żadnych więcej capitalize_d żądania, lub w przeciwnym razie światło może pozostać czerwone na zawsze. W ten sposób skończysz kontrolować przepływ swoich żądań (albo gorzej: nie zrobisz żadnego, a twój system może zamarznąć na śmierć, jeśli operacja wypłynie z miejsca, w którym trafiłeś przypadkowo).

• jeśli operacja zmienia strukturę drzewa (oczywiście, jak to robi remove_a), należy zapobiegać równoczesnemu dostępowi. Co najmniej należy zablokować poddrzewo, zaczynając od węzła, nad którym pracuje remove_a, lub zezwolić na przetwarzanie poddrzewa, które może zostać asynchronicznie zmienione i/lub zniszczone.

Cóż, jest to możliwe. Widziałem dobrych ludzi zarabiających duże pieniądze, robiących wariacje na ten temat. Zwykle co tydzień spędzali kilka wieczorów, jedząc pizze na oczach swoich komputerów, ale hej, w ten sposób można odróżnić hakerów hard-hard od tłumu zjadaczy quiche, prawda? ...

Zakładam, że publikujesz Pytanie tutaj oznacza, że ​​tak naprawdę nie chcesz tego robić. Teraz, jeśli szef ma, cóż, cytując słynnego androida, nie mogę cię okłamywać o twoich szansach, ale ... masz moje sympatie.

Poważnie ludzie. W ten sposób rozwiązam ten problem.

1) wykonanie zrzutu danych w danym momencie

można pozbyć się surowych danych przy użyciu tak wielu kryteriów, jak można (ostatnia akwizycja danych zbyt stary, niewłaściwego wejścia, co pozwala budować najmniejsze możliwe drzewo).

2) zbuduj drzewo wraz z migawką, a następnie zastosuj kolejne operacje capitalize_d, remove_a i camelize_z na tej migawce, kolejno.

Jednocześnie proces zbierania danych będzie nadal zbierać nowe węzły lub aktualizować istniejące, gotowe do wykonania następnej migawki.

Poza tym możesz przesunąć część przetwarzania do przodu. Oczywiście capitalize_d nie wykorzystuje żadnej przewagi struktury drzewa, więc można zastosować capitalize_d do każdego węzła w migawce, zanim drzewo zostanie nawet zbudowane. Możesz nawet zastosować niektóre transformacje wcześniej, tj. Na każdej zebranej próbce. Może to zaoszczędzić wiele czasu przetwarzania i złożoności kodu.

Aby zakończyć z odrobiną teoretyczna bełkot,

• Twoje podejście jest rozważenie drzewo dane wspólny obiekt, który powinien wspierać jednoczesnych acces z procesów akwizycji danych i produkcyjnych danych
• moje podejście jest aby proces rejestracji danych służą (asynchronicznie) zgodne zestawy danych do procesu produkcji danych, która może wtedy obsługiwać kolejno wspomnianego zestawu danych.

proces produkcji danych może być uruchamiany na żądanie (np. Gdy użytkownik końcowy kliknie przycisk "pokaż mi coś"), w którym to przypadku reaktywność byłaby raczej słaba: użytkownik utknąłby oglądając klepsydrę lub cokolwiek Web2.0 sexy kołowrotek do czasu potrzebnego do budowy i przetwarzania drewna (pozwala powiedzmy 7-8 sekund).

lub można aktywować proces produkcyjny danych okresowo (nakarmić ją nową migawkę co 10 sekund, okres bezpiecznie powyżej czas przetwarzania średniego zestawu danych). „Pokaż mi coś” przycisk będzie wówczas tylko zaprezentować ostatni zestaw ukończonych danych. Natychmiastowa odpowiedź, ale z danych, które mogą być starsze niż 10 sekund ostatnich otrzymaliśmy próbek.

rzadko widziałem przypadków, w których nie uznano za dopuszczalne, zwłaszcza gdy można produkować kilka złożonych danych operator potrzebuje kilkadziesiąt sekund do strawienia.

Teoretycznie moje podejście straci pewną reaktywność, ponieważ przetwarzane dane będą nieco przestarzałe, ale podejście do równoczesnego dostępu prawdopodobnie spowoduje jeszcze wolniejsze działanie oprogramowania (a na pewno 5-10 razy większe i większe).

Answer 2

Znam ten post jest stary, ale wpadł w wynikach wyszukiwania, a samotny odpowiedź nie daje przykład działa, więc tutaj jest zmodyfikowaną wersją czegoś Niedawno robiłam ...

function processTree(rootNode, onComplete) { 

    // Count of outstanding requests. 
    // Upon a return of any request, 
    // if this count is zero, we know we're done. 
    var outstandingRequests = 0; 

    // A list of processed nodes, 
    // which is used to handle artifacts 
    // of non-tree graphs (cycles, etc). 
    // Technically, since we're processing a "tree", 
    // this logic isn't needed, and could be 
    // completely removed. 
    // 
    // ... but this also gives us something to inspect 
    // in the sample test code. :) 
    var processedNodes = []; 

    function markRequestStart() { 
     outstandingRequests++; 
    } 

    function markRequestComplete() { 
     outstandingRequests--; 
     // We're done, let's execute the overall callback 
     if (outstandingRequests < 1) { onComplete(processedNodes); } 
    } 

    function processNode(node) { 
     // Kickoff request for this node 
     markRequestStart(); 
     // (We use a regular HTTP GET request as a 
     // stand-in for any asynchronous action) 
     jQuery.get("/?uid="+node.uid, function(data) { 
      processedNodes[node.uid] = data; 
     }).fail(function() { 
      console.log("Request failed!"); 
     }).always(function() { 
      // When the request returns: 
      // 1) Mark it as complete in the ref count 
      // 2) Execute the overall callback if the ref count hits zero 
      markRequestComplete(); 
     }); 

     // Recursively process all child nodes (kicking off requests for each) 
     node.children.forEach(function (childNode) { 
      // Only process nodes not already processed 
      // (only happens for non-tree graphs, 
      // which could include cycles or multi-parent nodes) 
      if (processedNodes.indexOf(childNode.uid) < 0) { 
       processNode(childNode); 
      } 
     }); 

    } 

    processNode(rootNode); 
} 

A oto przykład użycia przy użyciu QUnit:

QUnit.test("async-example", function(assert) { 
    var done = assert.async(); 

    var root = { 
     uid: "Root", 
     children: [{ 
      uid: "Node A", 
      children: [{ 
       uid: "Node A.A", 
       children: [] 
      }] 
     },{ 
      uid: "Node B", 
      children: [] 
     }] 
    }; 

    processTree(root, function(processedNodes) { 
     assert.equal(Object.keys(processedNodes).length, 4); 
     assert.ok(processedNodes['Root']); 
     assert.ok(processedNodes['Node A']); 
     assert.ok(processedNodes['Node A.A']); 
     assert.ok(processedNodes['Node B']); 
     done(); 
    }); 
});