Более эффективно вычислять транзитивные замыкания для каждого иждивенца, постепенно наращивая ориентированный граф - PullRequest
Новая
       68

Более эффективно вычислять транзитивные замыкания для каждого иждивенца, постепенно наращивая ориентированный граф

0 голосов
/ 17 ноября 2018

Мне нужно ответить на вопрос: учитывая узел в графе зависимостей, сгруппируйте его иждивенцев по их собственным переходным иждивенцам, на которые будет влиять конкретный начальный узел.

Другими словами, учитывая узел в графе зависимостей, найдите набор множеств прямых зависимостей, которые транзитивно имеют общих зависимостей, производных от этого конкретного начального узла.

например. учитывая псевдокод: 

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

Вы можете вычислить этот график:

Graph diagram

Если мы использовали 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) - это массив, он же список, но он используется как набор для простоты.

Вот JSBin: https://jsbin.com/jexofip/edit?js,console

Это работает, и для процессора это приемлемо, потому что мне очень часто нужно знать сгруппированные иждивенцы, но они меняются гораздо реже.

В приведенном выше примере для простоты демонстрации используется 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 МБ !!!) и также возможно создание новых узлов на неопределенный срок, используя бесконечный объем памяти, поэтому это решение не практично, поскольку нет простого способа «собрать мусор», который больше не использует биты маски из узловэто исключает график - это, конечно, возможно, но это традиционная проблема GC, которую я бы хотел избежать, если это возможно.

Примечание: в зависимости от размера и глубины графика, это может быть не совсемвыступать хорошо тоже.Несмотря на то что сами побитовые операции выполняются относительно быстро, выполнение этого для BigInt в 100 000 битов для каждого узла в верхней части графа не выполняется.Так что полностью переосмыслить мой подход также приветствуется.

В конечном счете, торговля памятью для процессора - это обычное взаимное преимущество, но мне интересно, возможно, мне не хватает другого подхода, который обеспечивает лучший баланс или требуетзначительно меньше памяти?

Могут быть и другие уникальные соображения, о которых я даже не думал, что они могут быть использованы.

Обучи меня!

Ответы [ 3 ]

0 голосов
/ 19 ноября 2018

Отношение, которое вы хотите сгруппировать, не является отношением эквивалентности . Например, рассмотрим этот график зависимости:

imagebcd, bc->e, cd->f">

Здесь b и c имеют общего иждивенца, как и c и d , но общего зависимого не существует между b и d . В этом случае вы, вероятно, захотите иметь b , c и d в одной группе. Однако в этом случае становится сложнее:

imagebd, bc->e, cd->f">

Здесь a не зависит от c , поэтому вы можете захотеть иметь b и d в отдельных группах, теперь вам не нужно заботиться о c . Тем не менее, существует класс алгоритмов, которые группируют b и d в этом случае: алгоритмы, которые поддерживают группировку всех узлов и используют это как основа для группировки прямых потомков нового узла.

Один из таких алгоритмов использует структуру с дизъюнкт-множеством , чтобы эффективно отслеживать, какие узлы подключены. В моем примере перед обработкой a алгоритм будет иметь узлы b , c , d , e и f все в одном наборе, поэтому они будут сгруппированы вместе.

Вот реализация: 

function find(node) {
  return node.parent == null ? node : (node.parent = find(node.parent));
}

function merge(a, b) {
  a = find(a);
  b = find(b);
  if (a.rank < b.rank) {
    a.parent = b;
  } else {
    b.parent = a;
    if (a.rank == b.rank) {
      ++a.rank;
    }
  }
}

class Node {
  constructor(name, dependents) {
    this.name = name;
    this.parent = null;
    this.rank = 0;
    let depMap = new Map();
    for (let d of dependents) {
      let dset = find(d);
      if (!depMap.has(dset)) {
        depMap.set(dset, []);
      }
      depMap.get(dset).push(d);
    }
    output += name + ': ' + Array.from(depMap.values()).map(a => '{' + a.join(', ') + '}').join(', ') + '\n';
    for (let d of depMap.keys()) {
    // or: for (let d of dependents) {
      merge(this, d);
    }
  }

  toString() {
    return this.name;
  }
}

let output = '';
const f = new Node('f', []);
const e = new Node('e', [f]);
const d = new Node('d', []);
const c = new Node('c', [d]);
const b = new Node('b', [d]);
const a = new Node('a', [b, c, e, f]);
document.getElementById('output').textContent = output;
0 голосов
/ 28 ноября 2018

Сохранение «достижимых» узлов для каждого узла в виде битовой маски и выполнение побитового И, безусловно, сложно вычислить.Если основной проблемой при этом является высокое использование памяти, то, возможно, это можно рассматривать как проблему сжатия памяти.

Если битовые маски очень редки (много нулей), есть вероятность, что они будут сжаты догораздо меньший размер.

Я представляю, что вам нужно найти библиотеку сжатия, которая может распаковывать битовые маски в виде потока.Таким образом, вы можете делать побитовое И при его распаковке, что позволит вам избежать сохранения полностью распакованной битовой маски.

0 голосов
/ 17 ноября 2018

Если это ориентированный ациклический граф, вы можете выполнить топологическую сортировку узлов, и это кажется хорошей основой для последующих шагов. Сама топосортировка может быть выполнена эффективно. Существуют реализации в библиотеках, основанных на FRP, таких как моя crosslink или paldepind's flyd

Также, проверьте этот ответ .

...