Какая самая простая и эффективная структура данных для построения ациклических зависимостей?

Question

Я пытаюсь построить последовательность, которая определяет порядок уничтожения объектов. Можно предположить, что циклов нет. Если объект A использует объект B во время его (A) строительства, то объект B все еще должен быть доступен во время уничтожения объекта A. Таким образом, желаемый порядок уничтожения - это A, B. Если другой объект C использует объект B также во время своего (C) -строения, то желаемый порядок - это A, C, B. В общем, пока объект X уничтожен только после всех других объектов, которые использовали этот объект во время их строительства, уничтожение является безопасным.

Если наш порядок уничтожения до сих пор AECDBF, и теперь мы получаем X (мы никогда не знаем заранее, в каком порядке изначально будет происходить построение, оно обнаружено на лету), которое использует C и F во время своего построения, затем мы можем получить новый безопасный порядок, поставив X перед тем, что в данный момент находится ранее в списке, C или F (случается, C). Таким образом, новый порядок будет AB X CDEF.

В контексте примера X связанный список кажется неподходящим, потому что для определения более раннего варианта, C или F, потребовалось бы много линейного сканирования. Массив будет означать медленные вставки, которые будут одним из общие операции. Очередь приоритетов на самом деле не имеет подходящего интерфейса, нет «Вставить этот элемент раньше, какой из этих элементов самый ранний» (мы не знаем правильный приоритет перед рукой, чтобы убедиться, что он вставлен перед элементом с более низким приоритетом и не мешая другим записям).

Все объекты построены, желаемый порядок вычислен, и последовательность будет повторена один раз и разрушена по порядку. Никаких других операций выполнять не нужно (фактически, после использования любой структуры данных для определения порядка ее можно скопировать в плоский массив и отбросить).

Редактировать: Просто чтобы прояснить, первый раз, когда объект используется, когда он построен. Таким образом, если A использует B, то E использует B, когда E пытается использовать B, оно уже было создано. Это означает, что стек не даст желаемый порядок. AB станет ABE, когда мы хотим AEB.

Edit2: я пытаюсь построить порядок «по ходу», чтобы сохранить алгоритм на месте. Я бы предпочел не создавать большую промежуточную структуру, а затем преобразовывать ее в окончательную структуру.

Edit3: я сделал это слишком сложным; p

Answer 1

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

Итак, для инициализации каждого объекта:

• инициализируем себя, инициализируем неинициализированные зависимости по ходу
• добавить себя в начало списка уничтожения (или поместить себя в стек, если вы используете стек)

и для уничтожения, просто пройдитесь по связанному списку с фронта вперед (или выбросьте предметы из стека до пустого места), уничтожая по мере продвижения. Пример в вашем первом абзаце, инициализированный в порядке B, A, C, таким образом, будет уничтожен в порядке C, A, B - что безопасно; пример в вашем редактировании будет инициализирован в порядке B, A, E (не A, B, E, поскольку A зависит от B), и, следовательно, будет уничтожен в порядке E, A, B, что также безопасно.

Answer 2

Хранить как дерево

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

Чтобы сгенерировать заказ, пройдите в свой связанный список верхнего уровня

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

Если список верхнего уровня пуст, значит, вы создали полный заказ.

typedef struct _dependent Dependent;
typedef struct _resource_info ResourceInfo;

struct _dependent 
{
  Dependent * next;
  ResourceInfo * rinfo;
}
struct _resource_info
{
  Resource * resource; // whatever user-defined type you're using
  size_t num_dependencies;
  Dependent * dependents;
}

//...
Resource ** generateOrdering( size_t const numResources, Dependent * freeableResources )
{
  Resource ** const ordering = malloc(numResources * sizeof(Resource *));
  Resource ** nextInOrder = ordering;

  if (ordering == NULL) return NULL;
  while (freeableResources != NULL)
  {
    Dependent * const current = freeableResources;
    Dependent * dependents = current->rinfo->dependents;

    // pop from the top of the list
    freeableResources = freeableResources->next;

    // record this as next in order
    *nextInOrder = current->rinfo->resource;
    nextInOrder++;
    free(current->rinfo);
    free(current);

    while (dependents != NULL)
    {
       Dependent * const later = dependents;

       // pop this from the list
       dependents = later->next;

       later->rinfo->num_dependencies--;
       if (later->rinfo->num_dependencies == 0)
       {
          // make eligible for freeing
          later->next = freeableResources;
          freeableResources = later;
       }
       else
       {
           free(later);
       }
    }
  }
  return ordering;
}

Чтобы помочь создать дерево, вам также может понадобиться таблица быстрого просмотра для сопоставления Resource с ResourceInfo с.

Answer 3

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

Answer 4

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

Одна вещь, по которой мне неясно: вам нужны вычисления в случайные моменты времени или после того, как вы получили всю информацию? Я предполагаю последнее, что вы можете подождать, пока ваш график не будет завершен. Если это так, ваш вопрос представляет собой топологическую сортировку , для которой существует реализация линейных по краям и вершинам времени. Это относительно простой алгоритм. Я немного перевернут из-за вашего описания (обеденный перерыв заставляет меня спать медленно и сонно, извините), но на самом деле вам может понадобиться «обратный» топологический тип, но принципы идентичны. Я не буду пытаться объяснить, как именно работает алгоритм (см .: медленно и сонный), но я думаю, что приложение должно быть ясным. Если только я полностью не прав, в таком случае, неважно?

Подведем итог: В некотором смысле, вы строите структуру данных, график, примерно за такое эффективное время, на которое вы можете надеяться (это зависит от того, как вы вставляете). График отражает, какие объекты нужно ждать, а какие другие. Затем, когда вы закончите его создание, вы запустите топологическую сортировку, и это отражает их зависимости.

Редактировать: Прошло много времени с тех пор, как я смешал слова "ты" и "ты". (

Answer 5

Вас больше интересует уничтожение первоклассных объектов C ++ в правильном порядке, чтобы избежать зависимостей, или моделирование некоторого внешнего, реального поведения, когда вас больше интересует алгоритм и повторяемость?

В первом случае вы можете использовать умные указатели подсчета ссылок (ищите shared_ptr, доступный в Boost и будущем стандарте C ++), чтобы отслеживать ваши объекты, возможно, с помощью заводской функции. Когда объект A инициализируется и хочет использовать объект B, он вызывает фабричную функцию B и получает умный указатель на B, увеличивая счетчик ссылок B. Если C также ссылается на B, счетчик ссылок B снова увеличивается. A и C могут быть освобождены в любом порядке, а B должен быть освобожден последним. Если вы храните shared_ptr s для всех ваших объектов в неупорядоченной структуре данных, когда вы закончите работу, вы освободите список всех объектов, а shared_ptr позаботится обо всем остальном в правильном порядке. (В этом примере на A и C ссылается только список всех объектов, поэтому их счетчики ссылок равны 1, а на B ссылаются все A и C и список всех объектов, поэтому его счетчик ссылок равен 3. Когда список всех объектов освобождает свою ссылку на объекты, счетчики ссылок A и C. переходят в 0, поэтому они могут быть освобождены в любом порядке. Счетчик ссылок B не возвращается в 0, пока A и C не будут освобождены, поэтому продолжать жить, пока все ссылки на него не будут освобождены.)

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

Answer 6

Звучит так, будто вы строите дерево из листьев.

Answer 7

Представьте это так: граф с ребром от А до В, если деструктор А должен быть запущен после В. Вставка X теперь означает добавление двух ребер, и это O (n log n)), если вы сохраняете отсортированный индекс узлов. Чтобы прочитать порядок уничтожения: выберите любой узел, следуйте по краям, пока вы не можете больше. Деструктор этого узла можно безопасно вызвать. Затем выберите один из оставшихся узлов (например, предыдущий пройденный вами узел) и повторите попытку.

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