更有效地计算每个家属的传递闭包,同时逐步建立有向图

Question

我需要回答这个问题:给定一个依赖图中的节点,通过它们自己的传递依赖对其依赖者进行分组,这些依赖会受特定的起始节点的影响.

换句话说,给定依赖图中的节点,找到直接依赖的集合的集合,其直接依赖于从该特定起始节点导出的公共依赖.

例如,给出伪代码:

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起始节点,我们可以看到a两者的依赖性,c并且d具有依赖性g.并且f有依赖e和a.

请注意,a根本没有任何影响b,因此在决定如何对依赖者进行分组时不应将其考虑在内a.

使用a作为起始节点,我们想要获得这些分组的依赖集:

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

c并且d具有直接或传递的下游关系,并且e也f在一起.但是,例如,e与f不具有依赖性的(下游)的关系在所有c或d直接或间接地(及物动词).而且b不是a直接或间接衍生出来的,因此不应对决定我们的分组产生任何影响.

另请注意,为简单起见,此图表很小.传递依赖性可能发生在子图中比这个例子恰好发生的更多.

---

我做了大量的纸研究,确实有很多解决方案,但是它们没有我正在寻找的性能特征.随着时间的推移逐步创建图形,并且在每个阶段我都需要能够回答这个问题,因此每次遍历整个图形都是一个交易破坏者.

我认为我有一个主要的优点,我没有在我能找到的各种方法中引用:我完全控制图的创建,并且依赖项以反向拓扑顺序添加,因此图正确排序.考虑到这一点,我考虑了逐步计算答案的明显解决方案(动态编程).

我认为一个位掩码将是一种快速存储和查找给定节点依赖的方式.当一个依赖项添加到一个节点时,我会更新该节点的掩码以包含该依赖的位(它本身包括它的依赖项等)

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

最后a有一个掩码01111101,每个位代表它的每个下游传递依赖.请注意,倒数第二位不会被翻转,这是b根本不依赖的位a.

如果我们看一下a.dependents我们看到的结果值:

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

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

这是一个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!

这排除了使用任意精度整数(或类似的自定义数据结构)的任何平台开销.

在我的用例中,通常有10k +,事实上在某些情况下可能有100k +(625 MB !!!)并且使用无限量的内存也可以无限期地创建新节点,因此这个解决方案是不实际的,因为没有简单的方法来"垃圾收集"不再使用从图表中删除的节点的掩码位 - 这当然是可能的,但这是我想要尽可能避免的传统GC问题.

旁注:根据图表的大小和深度,这可能实际上也不会很好.尽管按位运算本身相对较快,但对于图形顶部的每个节点,在100,000It的BigInt上进行操作却不是.所以完全重新思考我的方法也是受欢迎的.

---

最终交易CPU的内存是通常的给予和接受,但我想知道是否可能我错过了另一种方法来实现更好的平衡或需要更少的内存？

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

上学我!

Answer 1

将每个节点的“可到达”节点存储为位掩码并执行按位“与”操作，听起来在计算上确实很难击败。如果主要问题是内存使用率高，那么这可能会被视为内存压缩问题。

如果位掩码非常稀疏（很多零），则它们有可能会压缩到更小的大小。

我想您会想要找到一个可以将位掩码解压缩为流的压缩库。这样您就可以在解压缩时执行按位与操作 - 允许您避免存储完全解压缩的位掩码。