Comment éviter `shareReplay` en marchant dans une arborescence

Question

J'essaie de réécrire un gestionnaire de paquets en utilisant RxJS (le PM est pnpm et le PR est here).

Au cours de la réécriture, j'ai utilisé beaucoup de .shareReplay(Infinity), que je l'ai été dit est mauvais (je suis un débutant dans la programmation réactive)

Quelqu'un pourrait-il proposer une alternative comment réécrire le code comme suit, w/o en utilisant .shareReplay(Infinity):

'use strict' 
const Rx = require('@reactivex/rxjs') 

const nodes = [ 
    {id: 'a', children$: Rx.Observable.empty()}, 
    {id: 'b', children$: Rx.Observable.empty()}, 
    {id: 'c', children$: Rx.Observable.from(['a', 'b', 'd'])}, 
    {id: 'd', children$: Rx.Observable.empty()}, 
    {id: 'e', children$: Rx.Observable.empty()}, 
] 

// I want this stream to be executed once, that is why the .shareReplay 
const node$ = Rx.Observable.from(nodes).shareReplay(Infinity) 

const children$ = node$.mergeMap(node => node.children$.mergeMap(childId => node$.single(node => node.id === childId))) 

children$.subscribe(v => console.log(v)) 

Answer 1

L'opérateur groupBy devrait fonctionner ici. En regardant le PR cela pourrait être un simplification grossière, mais voilà:

'use strict' 
const Rx = require('@reactivex/rxjs') 

const nodes = [ 
    {id: 'a', children$: Rx.Observable.empty()}, 
    {id: 'b', children$: Rx.Observable.empty()}, 
    {id: 'c', children$: Rx.Observable.from(['a', 'b', 'd'])}, 
    {id: 'd', children$: Rx.Observable.empty()}, 
    {id: 'e', children$: Rx.Observable.empty()}, 
] 

Rx.Observable.from(nodes) 
// Group each of the nodes by its id 
.groupBy(node => node.id) 
// Flatten out each of the children by only forwarding children with the same id 
.flatMap(group$ => group$.single(childId => group$.key === childId)) 
.subscribe(v => console.log(v)); 

Edit: Plus difficile que je pensais

Ok, donc mon deuxième lecture par Je vois que cela nécessite plus de travail que je ne le pensais au départ, donc il ne peut pas être simplifié si facilement. Fondamentalement, vous allez devoir choisir entre la complexité de la mémoire et la complexité du temps, puisqu'il n'y a pas de solution miracle. Du point de vue de l'optimisation, si la source initiale est juste un tableau, vous pouvez supprimer le shareReplay et cela fonctionnera exactement de la même manière, car lorsque vous vous abonnez à ArrayObservable, le seul overhead va être itéré dans le tableau. , il n'y a pas vraiment de coût supplémentaire pour réexécuter la source.

Fondamentalement pour cela, je pense que vous pouvez penser à deux dimensions, le nombre de nœuds m et le nombre moyen d'enfants n. Dans la version optimisée pour la vitesse, vous devrez parcourir deux fois le m et vous devrez parcourir les "n" nœuds. Puisque vous avez des enfants, le pire serait que tous soient uniques. Ce qui signifie que vous devez faire (m + m*n) opérations qui simplifie à O(m*n) si je ne me trompe pas. L'inconvénient de cette approche est que vous devez avoir à la fois une carte de (nodeId -> Node) et une carte pour supprimer les dépendances en double. L'alternative est d'utiliser une approche similaire à la vôtre qui se concentre sur la réduction de la pression mémoire au détriment de la performance. Notez, comme je l'ai dit, que vous pouvez simplement supprimer shareReplay si votre source est un tableau, car tout ce qu'il fait quand il réévalue est ré-itérer le tableau. Cela supprime les frais généraux de la carte supplémentaire. Bien que je pense que vous auriez encore besoin de distinct pour supprimer les doublons. La complexité d'exécution la plus défavorable serait O(m^2*n) ou simplement O(m^2) si n est petite, car vous devrez parcourir tous les enfants et pour chaque enfant, vous devrez également parcourir à nouveau m pour trouver le nœud correspondant.

const node$ = Rx.Observable.from(nodes); 
node$ 
    // Flatten the children 
    .flatMap(node => node.children$) 
    // You may still need a distinct to do the de-duping 
    .flatMap(childId => node$.single(n => n.id === childId))); 

je dirais que la première option est préférable dans presque tous les cas, mais je laisse cela à vous de déterminer votre cas d'utilisation. Il se peut que vous établissiez une heuristique qui choisisse un algorithme plutôt que l'autre dans certaines circonstances.

Sidenote: Désolé ce n'était pas aussi facile, mais j'adore pnpm alors continuez votre bon travail!