aszinchron - Javascript: Hogyan irányítható a folyamat async rekurzív fa bejárással?

Szükségem van arra, hogy rekurzívan bejárjak egy fát, hogy műveleteket hajtsak végre bizonyos csomópontokon aszinkron műveletek segítségével. Hogyan tudom irányítani a folyamatot, hogy hozzáférjek a csomópontokhoz, amikor kész?

Íme egy példaszituáció:

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

Van egy függvényem, aminek az a célja, hogy bejárja a fát, és nagybetűssé tegye az összes olyan nevet, amely 'd'-vel kezdődik. Ezután szeretném átadni a fát egy másik függvénynek, hogy további munkát végezzen (esetleg törölje az összes csomópontot, amelynek neve 'a'-val kezdődik), de csak az elsődleges feldolgozás elvégzése után:

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);

A fenti kód rendben működik, mert a capitalize_d blokkoló. Ha a capitalize_d aszinkron módon rekurzív, hogyan garantálhatjuk, hogy a remove_a hívása csak akkor történjen meg, amikor az befejeződött? Vegyük észre a setTimeout hívást a capitalize_d-ben.

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);

A probléma az, hogy a fa különböző ágainak feldolgozása mind egyszerre indul el, és lehetetlen megmondani, mikor fejeződik be végül a fa feldolgozása.

Hogyan tudom ezt megoldani?

Válasz #1

Engedje meg, hogy összefoglaljam, amit az igényeiről megértettem:

• van egy adatfa, ahol minden egyes csomópontot aszinkron módon lehet módosítani egy műveletsorozattal (a példádban capitalize_d és remove_a)
• Biztosítani akarod, hogy minden egyes csomóponton végrehajtásra kerüljön egy adott művelet, mielőtt engedélyeznéd a következőt.

Több mint 10 évet töltöttem valós idejű beágyazott szoftverek tervezésével, és hidd el, a követelmények ezen a területen kegyetlenebbek és félelmetesebbek, mint bármi, amivel a legtöbb hálózati programozó élete során találkozik. Ez arra késztet, hogy figyelmeztesselek: úgy tűnik, komolyan rossz irányba tartasz itt.

Ahogy el tudom képzelni, a problémád az, hogy egy sor egyéni adatot valamilyen értelmes struktúrába rendezz. Valamilyen folyamat véletlenszerű információdarabokat gyűjt (amit te a példádban 'csomópontoknak' hívsz), és egy ponton szeretnéd az összes ilyen csomópontot egy következetes, monolitikus adatszerkezetbe helyezni (a példádban egy hierarchikus fába).

Más szóval, három feladat áll előtted:

• egy adatgyűjtési folyamat, amely aszinkron módon gyűjti az csomópontokat
• egy adat előállítási folyamat, amely következetes, finomított adatfát fog bemutatni
• egy vezérlő folyamat, amely szinkronizálni fogja az adatok gyűjtését és előállítását (esetleg közvetlenül a felhasználói felületet, ha a fenti két folyamat elég intelligens, de ne számíts rá túl sokat).

A tanácsom: ne próbáld egyszerre elsajátítani és előállítani.

Csak hogy elképzelést adjak arról a rémálomról, aminek elébe nézel:

• attól függően, hogy az műveletek hogyan vannak kiváltva, fennáll a lehetőség, hogy a fát egy adott művelet soha nem dolgozza fel teljesen. Tegyük fel, hogy a vezérlő szoftver elfelejti meghívni a capitalize_d-t néhány csomóponton, a remove_a egyszerűen soha nem kapja meg a zöld jelzést

• Ezzel szemben, ha véletlenszerűen lősz a fára, nagyon valószínű, hogy néhány csomópont többször is feldolgozásra kerül, hacsak nem követed nyomon a művelet lefedettségét, hogy megakadályozd, hogy ugyanazt a transzformációt kétszer alkalmazd egy adott csomópontra.

• ha azt akarod, hogy a remove_a feldolgozás valaha elinduljon, lehet, hogy meg kell akadályoznod, hogy a vezérlő szoftver további capitalize_d kéréseket küldjön, különben a lámpa örökre piros maradhat. Végül valahogy irányítanod kell a kéréseidet (vagy még rosszabb: egyáltalán nem fogod, és a rendszered valószínűleg lefagy, ha az operációs folyamat elkalandozik a véletlenül elért optimális pontról).

• ha egy művelet megváltoztatja a fa szerkezetét (ahogy azt a remove_a nyilvánvalóan teszi), meg kell akadályozni a párhuzamos hozzáféréseket. Legalább annyit kell tenned, hogy zárolod azt az alkérintet, amelyen a remove_a dolgozik, különben lehetővé tennéd egy olyan alkérint feldolgozását, amely várhatóan aszinkron módon változik és/vagy megsemmisül.

Nos, ez megvalósítható. Láttam már fiatal férfiakat, akik nagy pénzt kerestek ennek a témának különböző változataival. Általában hetente pár estét pizzát fogyasztva töltöttek a számítógépük előtt, de hát, így lehet megkülönböztetni a keményfejű hackereket a quiche-t evő tömegtől, igaz?...

Feltételezem, hogy az, hogy itt teszed fel ezt a kérdést, azt jelenti, hogy valójában nem akarod ezt megtenni. Ha pedig a főnököd akarja, nos, egy híres androidot idézve, nem tudok hazudni neked az esélyeidről, de... együttérzek veled.

Na most komolyan, emberek.. Így közelíteném meg a problémát.

1) készítsen pillanatképet az adatairól egy adott időpontban

A nyers adatokat annyi kritérium szerint szűrheted, amennyit csak tudsz (túl régi az utolsó adatgyűjtés, helytelen bevitel, bármi, ami lehetővé teszi a lehető legkisebb fa felépítését).

2) Építsd fel a fát a pillanatképből, majd alkalmazd a capitalize_d, remove_a és camelize_z műveleteket egymás után a megadott pillanatképen.

Párhuzamosan az adatgyűjtési folyamat folytatja az új csomópontok gyűjtését vagy a meglévők frissítését, készen arra, hogy elkészítse a következő pillanatképet.

Ezenkívül előrébb is viheted a feldolgozás egy részét. Nyilvánvalóan a capitalize_d nem használja ki a fa szerkezetét, ezért alkalmazhatod a capitalize_d-t minden csomóponton a pillanatfelvételben, még mielőtt a fa egyáltalán felépülne. Lehet, hogy néhány transzformációt akár korábban is alkalmazhatsz, azaz minden begyűjtött mintán. Ez sok feldolgozási időt és kód összetettséget takaríthat meg.

Ahhoz, hogy egy kicsit elméleti zagyvalékkal fejezzem be,

• A megközelítésed az, hogy a adatfát közös objektumként kezeld, amelynek támogatnia kell a párhuzamos hozzáférést az adatgyűjtési és adattermelési folyamatok részéről.
• A megközelítésem az, hogy az adatszerzési folyamat (aszinkron módon) konzisztens adatkészleteket szolgáltasson egy adatfeldolgozó folyamat számára, amely ezután sorban tudja kezelni az említett adatkészletet.

az adatgyártási folyamat igény szerint indítható (például amikor a végfelhasználó rákattint a „mutass valamit” gombra), ebben az esetben a reakciókészség meglehetősen rossz lenne: a felhasználó órát vagy bármilyen Web2.0 menő forgó kereket nézne azon az időtartamon keresztül, ami a fa felépítéséhez és feldolgozásához szükséges (mondjuk 7-8 másodperc).

vagy időszakosan is aktiválhatnád az adatelőállítási folyamatot (tápláld egy új pillanatképpel minden 10. másodpercben, ami biztonságosan a dataset átlags feldolgozási ideje felett van). A „mutass valamit” gomb ekkor csak a legutóbbi elkészült adatkészletet jelenítené meg. Azonnali válasz, de az adatok akár 10 másodperccel régebbiek lehetnek az utoljára fogadott mintáknál.

Ritkán láttam olyan eseteket, amikor ezt nem tartották elfogadhatónak, különösen akkor, amikor egy csomó összetett adatot állítasz elő, amit egy operátornak néhány tucat másodpercbe telik feldolgozni.

Elméletileg az én megközelítésem valamennyit veszíteni fog a reakciókészségből, mivel a feldolgozott adatok kissé elavultak lesznek, de a párhuzamos hozzáférési megközelítés valószínűleg még lassabb szoftvert eredményezne (és biztosan 5-10-szer nagyobb és hibásabb lenne).

Válasz #2

Tudom, hogy ez a bejegyzés régi, de előjött a keresési eredmények között, és az egyetlen válasz nem nyújt működő példát, szóval itt van egy módosított változat valamiről, amit nemrég csináltam...

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);
}

Íme egy példa a QUnit használatára:

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();
    });
});