Эффективный обход списка изменений

Question

У меня есть список изменений в списке — добавление и удаление.Список может быть огромным — скажем, 10 000 позиций.

Я хочу знать состояние списка после изменения 9000.

Я мог бы пройтись по списку от начала до конца, чтобы поменять 9000.Мне это кажется немного затянутым.

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

Но обозначение Big O говорит о том, что уменьшение размера проблемы вдвое не повышает эффективность (если я правильно понял).

Я мог бы кэшировать состояние списка при каждом сотом или тысячном изменении...но опять же, большая буква О говорит, что деление количества элементов на «n» не делает работу более эффективной.

Так каков же эффективный способ сделать это?Есть ли эффективный способ сделать это?

Более подробная информация:В частности, я отслеживаю выделение/освобождение памяти в специальном распределителе.Каждое выделение/освобождение является событием в списке.Каждое распределение имеет уникальный идентификатор.Я хотел бы знать, что в настоящее время выделяется после (например) 9000 событий.

Моя первая идея заключалась в том, чтобы сохранить для каждого идентификатора событие, когда он был выделен, и событие, когда оно было освобождено.Затем пройти этот список до первого выделения, событие выделения которого больше 9000.Но, как я уже сказал, это сократит вдвое количество пунктов, которые мне придется пройти.

Мне нравится мысль Майка Ф.: ход от ближайшего сотого элемента — это постоянное время…

Answer 1

Если вы кэшируете состояние списка при каждом X-м изменении, то вы можете выполнить двоичную операцию, чтобы перейти к двум кэшированным состояниям, ограничивающим искомое изменение, а затем пройти максимум X элементов, чтобы добраться до самого элемента.Это более или менее O(log N).

Но в более общем плане снижение сложности большого О — это средство, а не цель.Если ваш список обычно состоит из 10 000 элементов, вам следует позаботиться о том, чтобы сделать его быстрым для N = 10 000, либо за счет уменьшения сложности, либо просто за счет ускорения.

Редактировать: Упс, я просто прочитал ваш вопрос внимательнее.Если вы кэшируете состояние каждые (например) 100 элементов, вы не выполняете поиск, поэтому вам даже не нужно выполнять двоичную обработку — вы просто переходите непосредственно к ближайшему кэшированному состоянию и проходите не более 100 элементов, чтобы добраться до элемента. сам.Так это алгоритм постоянного времени, нет?

Answer 2

С какой структурой вы работаете?Не существует эффективного способа обхода общей структуры данных, но существуют тысячи методов оптимизации и эффективных методов для конкретных структур.

И да, если у вас есть алгоритм с временной сложностью O(n), уменьшение вдвое количества элементов не изменит его сложность по сравнению с O(n)...но это будет означать, что каждый новый предмет будет иметь только половину того эффекта, который был изначально.Обозначение Big O — хороший способ классификации алгоритмов, но на самом деле его эффективность не влияет, за исключением огромных чисел (один хороший пример — сортировка.быстрая сортировка в худшем случае сложнее, чем сортировка слиянием...но вы можете реализовать быструю сортировку более эффективно, чем сортировку слиянием, практически для любого приложения, кроме тех, которые занимаются сортировкой миллионов элементов)

Answer 3

«Отметка времени» или отмечайте каждую вставку и удаление, тогда для поиска изменений потребуется простой обход (O (n)).