Проблема
Я ищу эффективную структуру данных для выполнения массового реверсирования , массового обмена и произвольного доступа .Количество элементов является постоянным.
Чтобы лучше объяснить, что я ищу, я введу сделанную на заказ задачу:
У нас есть K сосудов, обозначенных 1, 2,.., K. Дается начальная перестановка этих сосудов, и требуется выполнить некоторые изменения этой перестановки, то есть: набор ( блок ) судов может быть заменен другим блоком, наборомможет быть перевернут, и в любой момент должна быть возможность ответить на вопрос о том, какое судно находится в положении i.
Лучшее объяснение можно дать на примерах:
Начальная перестановка: (3 41 2 7 6 5)
Поменяйте местами блок (4 1) с (2 7): (3 2 7 4 1 6 5)
Переверните блок (7 4 1): (3 2 1 4 7 6 5)
Получить судно в положении (на основе 1) 3: 1
Обратите внимание, что все это должно быть круглым, например:
Поменяйте местами блок (5 3) с (2 1): (1 5 3 4 7 6 2)
Хотя в приведенных мною примерах блок идентифицируется по его меткепожалуйстаМы считаем, что каждый блок фактически идентифицируется начальной и конечной позициями:
Учитывая перестановку (1 5 3 4 7 6 2), блок (3 4 7) идентифицируется индексами(На основе 1) {3, 5}.
Я использовал ярлыки в надежде на более четкое понимание типа ходов.
Я не буду давать никаких предположенийили ограничения на количество судов и операций, но есть две основные ситуации, с которыми можно столкнуться:
- Требуется много произвольного доступа, только один каждый набор обращений, массовый обмен и массовый реверс
- Много случайного доступа и, возможно, массовый обмен и реверсирование каждого доступа
Некоторые идеи
Идея решения этой проблемы может заключаться в использовании трепавыполнить log (n) swap, ленивое обратное обращение и распространение.Конечно, есть некоторые проблемы, чтобы сохранить сбалансированное дерево, но они могут быть решены.
Другой подход может заключаться в использовании двойного связанного списка для выполнения постоянного свопа и постоянной обратной операции, но возможно ли это?
В предположении, что все запросы находятся в последовательных расположениях или что можно использовать дополнительную память для хранения указателей или аналогичных элементов для обеспечения произвольного доступа также в структурах данных в виде списков, в некотором роде возможнообеспечить постоянный обмен времени и постоянный возврат времени?
С надеждой найти лучшие специальные решения:
Предположим, что каждый ход имеет следующую структуру:
- Возьмите два интервала (смежные, например, из (1 2 3 4 5), возьмите (1 2) и (3 4))
- В конце концовпоменяйте местами два
- В конечном итоге поменяйте местами один или оба, но без перекрытия!(например, своп (1 2), но не (2 3) или (5 1), который не является одним из выбранных интервалов)
- Повтор 1
Возможноеходы:
- Поменяйте местами два интервала
- Поменяйте местами два интервала без замены
- Поменяйте местами два интервала и поменяйте местами только один