#algorithm #data-structures
#алгоритм #структуры данных
Вопрос:
У меня есть массив произвольных объектов
- Каждый объект имеет уникальный идентификатор
- Новые объекты добавляются в конце очереди (хвост)
- Объекты удаляются сверху для обработки (FIFO)
- Объекты, ожидающие обработки, могут быть удалены, если требуется.
Проблема заключается в том, чтобы найти текущее положение объекта в очереди из хвоста с учетом идентификатора.
Какой самый быстрый способ это сделать? Просто для ясности, мне не нужен объект из идентификатора, поэтому просто хэш-карта не является решением. Что мне действительно нужно, так это позиция.
Мы подумали о двух способах:
- Перебор, поиск в цикле
- добавьте новое поле в Object, в котором хранится глобальный индекс, который увеличивается для каждого объекта, добавленного в очередь. Затем мы можем быстро получить позицию, проверив глобальный индекс, сохраненный в последнем элементе и этом элементе. Однако единственная сложность заключается в том, что если один из объектов удален, необходимо обновить глобальный индекс всех приведенных ниже элементов.
Есть идеи получше? Пожалуйста, предложите.
Комментарии:
1. Рассматриваете ли вы вариант с амортизированной временной сложностью? Вкратце, мы будем использовать неглубокое удаление из массива (ненастоящее, просто отметьте, что этот объект должен быть удален). Затем, когда у нас возникает ситуация, когда более 30% емкости занято отмеченными объектами, мы выполняем повторный расчет.
2. Возможно, # 2, но поддерживать глобальные индексы в кодированной форме с длиной выполнения, т. е. глобальный идентификатор и количество последовательных значений идентификатора. Вы можете быстро найти свой идентификатор, суммируя пропущенные прогоны, а затем вычисляя окончательное смещение. Для удаления вы разделяете длину выполнения на две, или сокращаете ее, или удаляете по мере необходимости.
Ответ №1:
Самый простой способ сделать это — представить FIFO в виде двусвязного списка. Этот список может состоять либо из Object s (это означает, что если бы у вас был идентификатор, вам также понадобилось бы сопоставление, либо хэш-сопоставление, либо какой-либо другой подход, от идентификатора к объекту), либо из автономных узлов FIFO (в этом случае у вас было бы сопоставление от идентификатора к адресу узла).
Ответ №2:
Я полагаю, что у меня есть log(n) временное решение. Создайте хэш-таблицу, которая сопоставляет каждый элемент ID с его узлом в нашей другой структуре данных — самобалансирующемся двоичном дереве поиска (красно-черное, AVL, что угодно). В этом дереве узел должен быть упорядочен по его относительному приоритету / порядку в вашей очереди. Он также должен хранить указатель на своего родителя в дереве и размер поддерева, имеющего корни в нем самом. Исходя из этого, мы можем запросить количество элементов с более низким приоритетом / порядком за логарифмическое время.