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

Question

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

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

Я мог бы пройтись по списку с самого начала, чтобы изменить 9'000. Это кажется мне немного скучным.

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

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

Я мог бы кэшировать состояние списка при каждом 100-м или 1000-м изменении ... но, опять же, большой O говорит, что деление количества элементов на 'n' не делает вещи более эффективными.

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

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

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

Мне нравится точка зрения Майка Ф. - ходить с ближайшего сотого пункта - это постоянное время ...

Answer 1

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

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

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

Answer 2

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

Answer 3

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

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