Какая самая простая и эффективная структура данных для построения ациклических зависимостей?
Я пытаюсь построить последовательность, которая определяет порядок уничтожения объектов. Можно предположить, что циклов нет. Если объект A использует объект B во время его (A) строительства, то объект B должен быть доступен во время уничтожения объекта A. Таким образом, желаемый порядок уничтожения - это A, B. Если другой объект C использует объект B также во время своего (C) -строения, то желаемый порядок - это A, C, B. В общем, пока объект X уничтожен только после всех других объектов, которые использовали этот объект во время их строительства, уничтожение является безопасным.
Если наш порядок уничтожения до сих пор - AECDBF, и теперь мы получаем X (мы никогда не знаем заранее, в каком порядке изначально будет происходить построение, оно обнаружено на лету), которое использует C и F во время своего построения, тогда мы можем получить новый безопасный порядок, поставив X перед тем, что в данный момент находится ранее в списке, C или F (случается, C). Таким образом, новый порядок будет ABX CDEF.
В контексте примера X связанный список кажется неподходящим, потому что для определения более раннего C или F. потребуется много линейного сканирования, а массив будет означать медленные вставки, что станет одной из наиболее распространенных операций. Очередь приоритетов на самом деле не имеет подходящего интерфейса, нет "Вставить этот элемент раньше, какой из этих элементов самый ранний" (мы не знаем правильный приоритет перед рукой, чтобы убедиться, что он вставлен перед элементом с более низким приоритетом и не мешая другим записям).
Все объекты построены, желаемый порядок вычислен, и последовательность будет повторена один раз и разрушена по порядку. Никаких других операций выполнять не нужно (фактически, после использования любой структуры данных для определения порядка, она может быть скопирована в плоский массив и отброшена).
Изменить: просто чтобы уточнить, первый раз, когда объект используется, когда он построен. Таким образом, если A использует B, то E использует B, когда E пытается использовать B, оно уже было создано. Это означает, что стек не даст желаемый порядок. AB станет ABE, когда мы хотим AEB.
Edit2: я пытаюсь построить порядок "как я иду", чтобы сохранить алгоритм на месте. Я бы предпочел не создавать большую промежуточную структуру, а затем преобразовывать ее в окончательную структуру.
Edit3: я сделал это слишком сложным, р
7 ответов
Поскольку зависимости всегда инициализируются перед объектами, которые от них зависят, и остаются доступными до тех пор, пока такие объекты не будут уничтожены, всегда должно быть безопасно уничтожать объекты в строго обратном порядке инициализации. Поэтому все, что вам нужно, - это связанный список, к которому вы добавляете объекты по мере их инициализации и проходите уничтожение, а каждый объект запрашивает инициализацию всех его зависимостей, которые еще не были инициализированы до его инициализации.
Итак, для инициализации каждого объекта:
- инициализировать себя, инициализируя неинициализированные зависимости, как мы идем
- добавить себя в начало списка уничтожения (или поместить себя в стек, если вы используете стек)
а для уничтожения просто идите по связанному списку вперед (или вытаскивайте предметы из стека, пока они не опустеют), уничтожая по мере продвижения. Пример в вашем первом абзаце, инициализированный в порядке B, A, C, таким образом, будет уничтожен в порядке C, A, B - что безопасно; пример в вашем редактировании будет инициализирован в порядке B, A, E (не A, B, E, поскольку A зависит от B), и, следовательно, будет уничтожен в порядке E, A, B, что также безопасно.
Храните его как дерево
- есть узел для каждого ресурса
- пусть каждый ресурс хранит связанный список указателей на ресурсы, которые зависят от этого ресурса
- каждый ресурс должен вести подсчет количества ресурсов, от которых он зависит
- ведите связанный список ресурсов, которые не имеют зависимостей
Чтобы сгенерировать заказ, пройдите свой список связанного верхнего уровня
- для каждого обработанного ресурса добавьте его в заказ
- затем уменьшить количество каждого ресурса, который зависит от него на один
- если какое-либо число достигает нуля, поместите этот ресурс в список верхнего уровня.
Когда список верхнего уровня пуст, вы создали полный заказ.
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с ResourceInfos.
Похоже, вы должны попытаться построить ориентированный, ациклический граф с шаблоном, как вы описали. Представление списка смежности (вектор связанных списков, вероятно, видя, как вы получаете новые узлы на лету) должно это сделать.
Одна вещь, в которой я не уверен: вам нужны вычисления в случайное время или после того, как вы получили всю информацию? Я предполагаю последнее, что вы можете подождать, пока ваш график не будет завершен. Если это так, то ваш вопрос является именно топологической сортировкой, для которой существует реализация по времени, линейному по краям и вершинам. Это относительно простой алгоритм. Я немного переворачиваюсь из-за вашего описания (обеденный перерыв заставляет меня спать медленно и сонно, извините), но на самом деле вам может понадобиться "обратный" топологический тип, но принципы идентичны. Я не буду пытаться объяснить, как именно работает алгоритм (см.: медленно и сонный), но я думаю, что приложение должно быть ясным. Если только я полностью не прав, в таком случае, неважно?
Подводя итог: В некотором смысле, вы строите структуру данных, график примерно за такое эффективное время, на которое вы можете надеяться (это зависит от того, как вы вставляете). График отражает, какие объекты нужно ждать, а какие другие. Затем, когда вы закончите его создание, вы запустите топологическую сортировку, и это отражает их зависимости.
Редактировать: Прошло много времени с тех пор, как я смешал "ты" и "ты".:(
Мне кажется, что у вас есть ориентированный ациклический граф, а топологическая сортировка даст вам порядок уничтожения объектов. Вероятно, вам также потребуется специальная обработка случая, когда граф имеет циклы (циклические зависимости).
Представьте это так: граф с ребром от A до B, если деструктор A должен быть запущен после B. Вставка X теперь означает добавление двух ребер, и это O(n log n)), если вы сохраняете отсортированный индекс узлов. Чтобы прочитать порядок уничтожения: выберите любой узел, следуйте по краям, пока вы не можете больше. Деструктор этого узла можно безопасно вызвать. Затем выберите один из оставшихся узлов (например, предыдущий пройденный вами узел) и повторите попытку.
Из того, что вы говорите, вставки происходят часто, но последовательность уничтожается только один раз для уничтожения: тогда эта структура данных должна быть подходящей, поскольку она имеет быстрые вставки за счет более медленных поисков. Может быть, кто-то еще может предложить более быстрый способ поиска в этой структуре данных.
Вас больше интересует уничтожение первоклассных объектов C++ в правильном порядке, чтобы избежать зависимостей, или моделирование некоторого внешнего, реального поведения, когда вас больше интересуют алгоритм и повторяемость?
В первом случае вы можете использовать умные указатели подсчета ссылок (ищите shared_ptr(доступно в Boost и будущем стандарте C++) для отслеживания ваших объектов, возможно, с помощью заводской функции. Когда объект A инициализируется и хочет использовать объект B, он вызывает фабричную функцию B и получает умный указатель на B, увеличивая счетчик ссылок B. Если C также ссылается на B, счетчик ссылок B снова увеличивается. A и C могут быть освобождены в любом порядке, а B должен быть освобожден последним. Если вы храните shared_ptrдля всех ваших объектов в неупорядоченной структуре данных, когда вы закончите работу, вы освободите список всех объектов, и shared_ptr позаботится об остальном, в правильном порядке. (В этом примере на A и C ссылается только список всех объектов, поэтому их счетчики ссылок равны 1, а на B ссылаются все A и C и список всех объектов, поэтому его счетчик ссылок равен 3. Когда список всех объектов освобождает свою ссылку на объекты, счетчики ссылок A и C. равны 0, поэтому они могут быть освобождены в любом порядке. Счетчик ссылок B не равен 0 до тех пор, пока A и C не будут освобождены, поэтому продолжать жить, пока все ссылки на него не будут освобождены.)
Если вас больше интересует алгоритм, вы можете смоделировать подсчет ссылок в своих собственных структурах данных, что может закончиться тем, что вы увидите что-то вроде ориентированного ациклического графа, когда закончите.