Генерация DAG из набора с использованием строго функционального программирования - PullRequest
13 голосов
/ 12 января 2012

Вот моя проблема: у меня есть последовательность S из (непустых, но, возможно, не отличных) наборов s_i, и для каждого s_i нужно знать, сколько наборов s_j в S (i ≠ j) являются подмножествами s_i.

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

Выполнение всего этого с использованием чисто функционального кода будетбыть огромным плюсом (я кодирую в Scala).

Поскольку включение множеств является частичным упорядочением, я подумал, что лучшим способом решения моей проблемы будет создание DAG, которая будет представлять диаграмму Хассе множеств,с ребрами, представляющими включение, и присоединяют целочисленное значение к каждому узлу, представляющему размер подэтапа ниже узла плюс 1. Однако я застрял на несколько дней, пытаясь разработать алгоритм, который строит диаграмму Хассе из частичного упорядочения(давайте не будем говорить о приросте!), хотя я думал, что это будет какой-то стандартный материал для студентов.

Вот моя структура данных:

case class HNode[A] (
  val v: A,
  val child: List[HNode[A]]) {
  val rank = 1 + child.map(_.rank).sum
}

Мой DAG определяется спискомкорни и некоторые частичные упорядочения:

class Hasse[A](val po: PartialOrdering[A], val roots: List[HNode[A]]) {
  def +(v: A): Hasse[A] = new Hasse[A](po, add(v, roots))

  private def collect(v: A, roots: List[HNode[A]], collected: List[HNode[A]]): List[HNode[A]] =
    if (roots == Nil) collected
    else {
      val (subsets, remaining) = roots.partition(r => po.lteq(r.v, v))
      collect(v, remaining.map(_.child).flatten, subsets.filter(r => !collected.exists(c => po.lteq(r.v, c.v))) ::: collected)
    }
}

Я застрял здесь.Последнее, что я пришел, чтобы добавить новое значение v в группу обеспечения доступности баз данных:

  1. найти все «корневые подмножества» rs_i для v в группе обеспечения доступности баз данных, т. Е. Подмножества v такие, что ни один из подмножеств rs_i не являетсяподмножество v. Это можно сделать довольно легко, выполнив поиск (BFS или DFS) на графике (функция collect, возможно, неоптимальная или даже ошибочная).
  2. сборка нового узла n_v,потомки которого являются ранее найденными rs_i.
  3. Теперь давайте выясним, где должен быть прикреплен n_v: для заданного списка корней выясняем надмножества v. Если ничего не найдено, добавьте n_v к корнями удалить подмножества n_v из корней.Иначе, выполните шаг 3 рекурсивно на дочерних объектах суперсетей.

Я еще не полностью реализовал этот алгоритм, но он кажется излишне сложным и неоптимальным для моей, казалось бы, простой задачи.Есть ли какой-нибудь более простой алгоритм (Google не знал об этом)?

Ответы [ 2 ]

2 голосов
/ 19 января 2012

После некоторой работы я наконец-то решил свою проблему, следуя своей первоначальной интуиции. Метод сбора и оценки ранга были ошибочными, я переписал их с хвостовой рекурсией в качестве бонуса. Вот код, который я получил:

final case class HNode[A](
  val v: A,
  val child: List[HNode[A]]) {
  val rank: Int = 1 + count(child, Set.empty)

  @tailrec
  private def count(stack: List[HNode[A]], c: Set[HNode[A]]): Int =
    if (stack == Nil) c.size
    else {
      val head :: rem = stack
      if (c(head)) count(rem, c)
      else count(head.child ::: rem, c + head)
    }
}

// ...

  private def add(v: A, roots: List[HNode[A]]): List[HNode[A]] = {
    val newNode = HNode(v, collect(v, roots, Nil))
    attach(newNode, roots)
  }

  private def attach(n: HNode[A], roots: List[HNode[A]]): List[HNode[A]] =
    if (roots.contains(n)) roots
    else {
      val (supersets, remaining) = roots.partition { r =>
        // Strict superset to avoid creating cycles in case of equal elements
        po.tryCompare(n.v, r.v) == Some(-1)
      }
      if (supersets.isEmpty) n :: remaining.filter(r => !po.lteq(r.v, n.v))
      else {
        supersets.map(s => HNode(s.v, attach(n, s.child))) ::: remaining
      }
    }

  @tailrec
  private def collect(v: A, stack: List[HNode[A]], collected: List[HNode[A]]): List[HNode[A]] =
    if (stack == Nil) collected
    else {
      val head :: tail = stack

      if (collected.exists(c => po.lteq(head.v, c.v))) collect(v, tail, collected)
      else if (po.lteq(head.v, v)) collect(v, tail, head :: (collected.filter(c => !po.lteq(c.v, head.v))))
      else collect(v, head.child ::: tail, collected)
    }

Теперь я должен проверить некоторую оптимизацию: - обрезать ветви с совершенно разными наборами при сборе подмножеств (как предложил Рекс Керр) - посмотрите, улучшает ли процесс сортировка наборов по размеру (как предложил Митчус)

Следующая проблема состоит в том, чтобы решить (в худшем случае) сложность операции add (). С n числом наборов и d размером самого большого набора, сложность, вероятно, будет O (n²d), но я надеюсь, что это можно уточнить. Вот мое рассуждение: если все наборы различны, DAG будет сокращен до последовательности корней / листьев. Таким образом, каждый раз, когда я пытаюсь добавить узел в структуру данных, мне все равно приходится проверять включение с каждым уже присутствующим узлом (как в процедурах сбора, так и присоединения). Это приводит к проверкам включения 1 + 2 +… + n = n (n + 1) / 2 ∈ O (n²).

Каждый тест на включение в набор равен O (d), отсюда и результат.

0 голосов
/ 17 января 2012

Предположим, что ваша DAG G содержит узел v для каждого набора с атрибутами v.s (набор) и v.count (количество экземпляров набора), включая узел G.root с G.root.s = union of all sets (где G.root.count=0, если этот набор никогда не встречается в вашей коллекции).

Затем, чтобы подсчитать количество различных подмножеств s, вы могли бы сделать следующее (в подделке смеси Scala, Python и псевдокода):

sum(apply(lambda x: x.count, get_subsets(s, G.root)))

, где

get_subsets(s, v) :
   if(v.s is not a subset of s, {}, 
      union({v} :: apply(v.children, lambda x: get_subsets(s, x))))

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

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