Структура данных типа очереди, позволяющая быстро определить позицию элемента. Есть? Положим есть у меня большой список элементов (уникальных строк).
В него элементы могут добавляться в конец, перемещаться внутри этого списка (не обмениваться), и удаляться из начала.
Может знаете такую структуру данных, которая позволит мне быстро (без перебора всего списка) по элементу определить номер его позиции в таком списке, такая структура ДОЛЖНА позволять быстро перемещать элементы (с обсчетом измененых позиций других элементов).
Кол-во элементов порядка 5 млн.
Идеальный вариант когда:
Время добавления в хвост: O(1)
Время получения из головы: O(1)
Время определения позиции: O(1) или O(log n)
Время перемещения одного элемента из конца в начало: O(log n) или O(1)
Приветствую любые ссылки. Спасибо.
Структура данных типа очереди, позволяющая быстро определить позицию элемента. Есть? Положим есть у меня большой список элементов (уникальных строк).
В него элементы могут добавляться в конец, перемещаться внутри этого списка (не обмениваться), и удаляться из начала.
Может знаете такую структуру данных, которая позволит мне быстро (без перебора всего списка) по элементу определить номер его позиции в таком списке, такая структура ДОЛЖНА позволять быстро перемещать элементы (с обсчетом измененых позиций других элементов).
Кол-во элементов порядка 5 млн.
Идеальный вариант когда:
Время добавления в хвост: O(1)
Время получения из головы: O(1)
Время определения позиции: O(1) или O(log n)
Время перемещения одного элемента из конца в начало: O(log n) или O(1)
Приветствую любые ссылки. Спасибо.
В него элементы могут добавляться в конец, перемещаться внутри этого списка (не обмениваться), и удаляться из начала.
Может знаете такую структуру данных, которая позволит мне быстро (без перебора всего списка) по элементу определить номер его позиции в таком списке, такая структура ДОЛЖНА позволять быстро перемещать элементы (с обсчетом измененых позиций других элементов).
Кол-во элементов порядка 5 млн.
Идеальный вариант когда:
Время добавления в хвост: O(1)
Время получения из головы: O(1)
Время определения позиции: O(1) или O(log n)
Время перемещения одного элемента из конца в начало: O(log n) или O(1)
Приветствую любые ссылки. Спасибо.
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Интересные статьи из справочника
Поможем написать учебную работу
Отвечай на вопросы, зарабатывай баллы и трать их на призы.
Подробнее
Подробнее
Для решения вашей задачи подойдет структура данных под названием "Linked List with Indexing". Это является комбинацией двух структур данных - связанного списка и индексированного массива. В этой структуре данных каждый элемент списка содержит ссылку на следующий элемент и индекс элемента в индексированном массиве.
Такая структура данных позволяет добавлять элементы в конец списка за O(1), получать элементы из начала списка за O(1), определять позицию элемента в списке за O(1) или O(log n) с использованием индексированного массива, и перемещать элементы из конца в начало списка за O(log n) или O(1).
Для большого списка уникальных элементов, такой подход может быть эффективным и быстрым. Однако, необходимо учитывать, что операции перемещения элементов могут потребовать пересчета индексов других элементов, что может занять дополнительное время.
Более подробную информацию и реализацию данной структуры данных можно найти в литературе или на специализированных ресурсах по алгоритмам и структурам данных.