在逐步构建有向图的同时,更有效地计算每个依赖项的传递闭包

换句话说,给定依赖关系图中的一个节点,找到一组直接依赖项,这些直接依赖项具有从特定起始节点派生的公共依赖项,可传递地具有这些公共依赖项。

例如,给定伪代码:

设B=2
设c= a+b
设d=a+b
让E = A
设f=a+e
设G=C+D
< /代码> 

你可以计算这个图表:



如果我们使用a作为开始节点,我们可以看到a、bothc和d的从属节点的从属节点have a dependent ofg。和fhas a dependent ofeanda。


请注意,a对b根本没有影响,因此在决定如何对a的从属项进行分组时,不应考虑到这一点。


使用a作为开始节点,我们希望获得这组从属项:

groups=c,d,e,f
< /代码> 

canddhave direct or transitive downstream relations,andeandftogether as well.但是,例如,eandfhave no dependent(downstream)relation at all withcordeither directly or indicately(transitively).并且bdoes not derived fromadirectly or indicately,so it should not have any impact on decising our grouping.


还要记住,为了简单起见,这个图很小。可能是子图下面的传递依赖项比本例所具有的要远得多。




我做了大量的论文研究,确实有很多解决方案,但是它们没有我想要的性能特征。随着时间的推移,图形会逐步创建,在每个阶段,我都需要能够回答这个问题,因此每次遍历整个图形都是一种释放机制。


我认为我有一个主要的优势,在我能找到的各种方法中没有被引用:我完全控制了图的创建,并且依赖项是以逆拓扑顺序添加的,所以图是正确排序的。考虑到这一点,我考虑了递增计算答案的显而易见的解决方案(动态编程)。

我认为位掩码是存储和查找给定节点所依赖项的快速方法。将依赖项添加到节点时,我将更新该节点的掩码以包括该依赖项的位(它本身包括其依赖项等)。

let maskcounter=0;

类节点{
施工单位(名称){
this.name=名称;
this.dependents=[];
this.mask=1<<maskCounter;
幻灯片计数器+;
}

添加依赖项(依赖项){
//现在我们的掩码包含表示所有
//它的直接和可传递依赖项
this.mask=this.mask_dependent.mask;

//需要查看此依赖项是否具有可传递的
//依赖于存在于其中一个组中的自身
for(此.dependents的const组){
const result=group.mask&dependent.mask;

如果(结果){
group.mask=从属.mask;
group.values.push(依赖);
返回;
}
}

//如果达到,则此依赖项没有可传递的依赖项
//与此节点的任何其他从属节点一起使用。
很困惑,嗯?
这个。家属。推({
mask:dependent.mask,
值:【依赖】
(});
}
}
< /代码> 

然而,依赖项将需要按与图形相反的顺序添加,以便图形正确排序,并且图形顶部包含其所有依赖项的遮罩。


const a=new node('a');
const b=新节点(“b”);
const c=新节点(“c”);
const d=新节点(“d”);
const e=新节点(“e”);
const f=新节点(“f”);
const g=新节点(“g”);

b.附加依赖项(c);
b.附加依赖项(d);
c.加依赖(g);
d.加依赖(g);
e.添加依赖项(f);
a.附加依赖项(c);
a.添加依赖项(d);
a.附加依赖项(e);
a.添加依赖项(f);
< /代码> 

位掩码将递增如下所示:

b=b 000000 10_c 00000100
B=B 00000110_D 000001000
C=C 00000100 G 01000000
D=D 00001000_G 01000000






这是可行的,CPU方面是可以接受的,因为我经常需要知道分组的从属项,但从属项更改的频率要少得多。


上面的示例使用javascript简化演示,它使用32位有符号整数进行位操作,因此我们只能创建31个唯一的节点。我们可以使用一个任意精度整数(例如bigint)来创建“unlimited”数量的节点,但是问题是内存使用。。


因为每个节点都需要自己独特的翻转位,所以ithinkmemory usage is:。


n*(n+1)/2=bits(其中n=number of nodes)

例如,10000个节点约为6.25兆字节!
< /代码> 

这不包括任何使用任意精度整数(或类似的自定义数据结构)的平台开销。

在我的用例中,通常会有10000+的内存,事实上,在某些情况下,100K+是可能的(625 MB!)!!)而且,使用无限量的内存也可以无限期地创建新节点,因此该解决方案不实用,因为“垃圾收集”不再使用节点的屏蔽位,而这些屏蔽位会从图形中删除——这当然是可能的,但这是我希望避免的传统GC问题(如果可能)。


旁注:根据图表的大小和深度,这实际上也可能表现不好。即使按位运算本身速度相对较快,但对图顶部的每个节点执行100000位的bigint操作也不是很快。因此,完全重新考虑我的方法也是受欢迎的。




最终,将内存换成CPU是一种常见的权宜之计,但我想知道,我是否缺少另一种平衡更好的方法,或者需要更少的内存?

可能还有其他一些我没有想到的独特考虑因素可以使用。


教训我![答:]会受到特定开始节点的影响。

换句话说,给定依赖关系图中的一个节点,找到一组直接依赖项,这些直接依赖项具有从特定起始节点派生的公共依赖项。

例如,给出了伪代码:

let a = 1
let b = 2
let c = a + b
let d = a + b
let e = a
let f = a + e
let g = c + d


你可以计算这个图表:



如果我们使用a作为起始节点,我们可以看到一,两者c和d依赖于g. 和f依赖于e和一.

注意到一对…没有影响b因此,在决定如何对其家属进行分组时,不应考虑一.

使用一作为开始节点,我们希望得到这些分组的从属项集:

groups = {{c, d}, {e, f}}


C和D具有直接或可传递的下游关系,以及e和f一起。但是,例如,e和f与…完全没有依赖关系C或D直接或间接(传递)。和B不是从一直接或间接地,所以它不应该对决定我们的分组有任何影响。

还要记住,为了简单起见,这个图很小。它可能是可传递依赖项在子图中发生得比本例发生得更远。



我做了大量的论文研究,确实有很多解决方案,但是它们没有我想要的性能特征。这个图是随着时间的推移逐步创建的,在每个阶段,我都需要能够回答这个问题,所以每次遍历整个图都是一个释放器。

我认为我有一个主要的优势,在我能找到的各种方法中没有被引用:我完全控制了图的创建,并且依赖项是以逆拓扑顺序添加的,所以图是正确排序的。考虑到这一点,我考虑了递增计算答案的显而易见的解决方案(动态编程)。

我认为位掩码是存储和查找给定节点所依赖项的快速方法。将依赖项添加到节点时,我将更新该节点的掩码以包括该依赖项的位(它本身包括其依赖项等)

let maskCounter = 0;

class Node {
  constructor(name) {
    this.name = name;
    this.dependents = [];
    this.mask = 1 << maskCounter;
    maskCounter++;
  }

  addDependent(dependent) {
    // Now our mask contains the bits representing all of
    // its direct and transitive dependents
    this.mask = this.mask | dependent.mask;

    // Need to see if this dependent has a transitive
    // dependent of its own that exists in one of the groups
    for (const group of this.dependents) {
      const result = group.mask & dependent.mask;

      if (result) {
        group.mask |= dependent.mask;
        group.values.push(dependent);
        return;
      }
    }

    // If reached, this dependent has no transitive dependents
    // of its own with any of this node's other dependents.
    // That's confusing, huh?
    this.dependents.push({
      mask: dependent.mask,
      values: [dependent]
    });
  }
}


然而,依赖项将需要按与图形相反的顺序添加,以便图形正确排序,并且图形顶部包含其所有依赖项的遮罩。

const a = new Node('a');
const b = new Node('b');
const c = new Node('c');
const d = new Node('d');
const e = new Node('e');
const f = new Node('f');
const g = new Node('g');

b.addDependent(c);
b.addDependent(d);
c.addDependent(g);
d.addDependent(g);
e.addDependent(f);
a.addDependent(c);
a.addDependent(d);
a.addDependent(e);
a.addDependent(f);


位掩码将逐渐如下所示:

b = b 00000010 | c 00000100
b = b 00000110 | d 00001000
c = c 00000100 | g 01000000
d = d 00001000 | g 01000000
e = e 00010000 | f 00100000
a = a 00000001 | c 01000100
a = a 01000101 | d 01001000
a = a 01001101 | e 00110000
a = a 01111101 | f 00100000
===========================
a = 01111101


最后一有面具01111101,每个位表示其下游传递依赖项。注意,第二个到最后一个位没有翻转,这是位乙不依赖于一完全。

如果我们看看a.dependents我们看到:

[
  { values: [c, d], mask: 0b00110000 },
  { values: [e, f], mask: 0b01001100 }
]


它提供了我们正在寻找的答案,最终是一组集合。a.dependents.map(group => group.values)--这是一个数组,也叫列表,但为了简单起见,它被用作一个集合。

这里有一个JSBin:https://jsbin.com/jexofip/edit?js,console

这是可行的,CPU方面是可以接受的,因为我经常需要知道分组的依赖项,但依赖项更改的频率要少得多。

上面的示例使用javascript简化演示,它使用32位有符号整数进行位操作,因此我们只能创建31个唯一的节点。我们可以使用任意精度整数(例如BigInt)创建“无限”数量的节点,但是问题是内存使用。

因为每个节点都需要自己独特的翻转位,认为内存使用量为:

N * (N + 1) / 2 = bits      (where N = number of nodes)

e.g. 10,000 nodes is about 6.25 megabytes!


这不包括使用任意精度整数(或类似的自定义数据结构)的任何平台开销。

在我的用例中,通常会有10000+的内存,事实上,在某些情况下,100K+是可能的(625 MB!)!!!)而且,使用无限量的内存也可以无限期地创建新节点,所以这个解决方案是不实际的,因为“垃圾收集”不再是简单的方法,不再使用从图中删除的节点的屏蔽位——这当然是可能的,但这是我希望尽可能避免的传统GC问题。

旁注:根据图表的大小和深度,这实际上也可能表现不好。即使按位运算本身速度相对较快,但对图顶部的每个节点执行100000位的bigint操作也不是很快。因此,完全重新考虑我的方法也是受欢迎的。



最终,将内存换成CPU是一种常见的权宜之计,但我想知道,我是否缺少另一种平衡更好的方法,或者需要更少的内存?

可能还有其他一些我没有想到的独特的考虑可以使用。

学我吧!