загрузка двойного связанного списка из базы данных sql

Question

так вот что я получил ...

QueueList

{Id,Queue_Instance_ID, Parent_Queue_Instance_ID, Child_Queue_Instance_ID}

каков будет самый эффективный способ вставить это в LinkedList<QueueList>? ты думаешь, что я могу опускаться ниже o(n^2)?

спасибо.

Answer 1

O (n) лучше, чем O (n ^ 2), верно? ;)

Я предполагаю, что родительский и дочерний идентификаторы фактически являются предыдущим и следующим идентификатором в списке.

Сначала поместите элементы в словарь, чтобы вы могли легко найти их на QueueInstanceId. В этом цикле вы также найдете первый элемент. Затем вы просто добавляете элементы в связанный список и используете словарь, чтобы получить следующий элемент. Пример в C #:

Dictionary<int, QueueList> lookup = new Dictionary<int, QueueList>();
QueueList first = null;
foreach (QueueList item in source) {
    lookup.Add(item.QueueInstanceId, item);
    if (item.ParentQueueInstanceId == -1) {
        first = item;
    }
}
LinkedList<QueueList> list = new LinkedList<QueueList>();
do {
    list.AddLast(first);
} while (lookup.TryGetValue(first.ChildQueueInstanceId, out first));

Добавление элементов в словарь и получение их по ключу - это операции O (1), а каждый цикл - это длина списка источников, поэтому это все операция O (n).

Answer 2

Немного подумав, вы можете сделать это за O (n) время, хотя это потребует некоторых дополнительных вещей, которые добавят некоторые накладные расходы. (Все еще O (n)).

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

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

Для этого требуется один проход, который равен O (n), а для хеш-таблицы требуется O (n) для инициализации, а для вставок - O (1).

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

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

Я не знаю или думаю, что существует решение на основе SQL-запросов, но мои знания SQL очень ограничены.

Надеюсь, это поможет!