Эффективный способ обрабатывать добавление и удаление элементов побитовым И

Question

Итак, предположим, у вас есть коллекция предметов. Каждый элемент имеет идентификатор, который может быть представлен с использованием битового поля. В качестве простого примера, предположим, что ваша коллекция: 0110, 0111, 1001, 1011, 1110, 1111

Итак, вы хотите реализовать функцию, Remove(bool bitval, int position). Например, вызов Remove(0, 2) удалит все элементы, где индекс 2 (то есть 3-й бит) равен 0. В этом случае это будет только 1001. Remove(1,1) удалит 1110, 1111, 0111 и 0110. Тривиально создать коллекцию O (n) там, где это возможно (просто используйте связанный список), где n - это количество элементов в коллекции. Как правило, количество элементов, которые должны быть удалены, будет O (n) (при условии, что данный бит имеет вероятность ≥ c%, равную 1, и вероятность ≥ c%, равную 0, где c - некоторая постоянная> 0), так что «лучшие» алгоритмы, которые так или иначе представляют собой O (l), где l - это количество удаляемых элементов, являются неинтересными.

Можно ли определить структуру данных, в которой среднее (или еще лучше, в худшем случае) время удаления лучше, чем O (n)? Бинарное дерево может работать очень хорошо (просто удалите все левые / правые ветви на высоте m, где m тестируемый индекс), но мне интересно, есть ли способ добиться большего успеха (и, честно говоря, я не знаете, как эффективно удалить все левые или правые ветви на определенной высоте). В качестве альтернативы, есть ли доказательство того, что добиться лучшего невозможно?

Редактировать: Я не уверен точно, чего я ожидаю с точки зрения эффективности (извините, Арно), но основное объяснение его возможного применения таково: предположим, мы работаем с двоичным деревом решений. Такое дерево может быть использовано для игрового дерева или для решения головоломок или чего-то еще. Далее предположим, что дерево достаточно мало, чтобы мы могли поместить все листовые узлы в память. Каждый такой узел - это просто битовое поле, в котором перечислены все решения. Теперь, если мы хотим обрезать произвольные решения из этого дерева, одним из методов будет просто перепрыгнуть на высоту, на которой принимается конкретное решение, и обрезать левую или правую сторону каждого узла (слева означает одно решение, справа - другое) , Обычно в дереве решений вы хотите обрезать поддерево только за один раз (поскольку родитель этого поддерева отличается от родителя других поддеревьев, и, следовательно, решение, которое следует удалить в одном поддереве, не следует обрезать от других), но в В некоторых ситуациях это может быть не так. Кроме того, обычно вы хотите только удалить все под конкретным узлом, но в этом случае вы оставите некоторые элементы ниже узла, но также обрежете ниже других узлов в дереве.

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

Edit: Думая об этом дальше, я думаю, что метод дерева на самом деле O (n / logn), предполагая, что он достаточно плотный. Доказательство: Предположим, у вас есть двоичное дерево с n элементами. Это высота log (n). Удаление половины дна потребует n / 2 удаления. Удаление половины строки выше потребует n / 4. Сумма операций для каждой строки равна n-1. Таким образом, среднее количество удалений составляет n-1 / log (n).

Answer 1

Если длина ваших битовых полей ограничена, может работать следующее:

• Сначала представьте битовые поля, которые находятся в наборе, как массив логических значений, поэтому в вашем случае (4-битные битовые поля), new bool[16];
• Преобразуйте этот массив логических значений в само битовое поле, так что в этом случае 16-битное битовое поле, где каждый бит представляет, включено ли битовое поле, соответствующее его индексу

Тогда операции становятся:

• Remove(0, 0) = и с битовой маской 1010101010101010
• Remove(1, 0) = и с битовой маской 0101010101010101
• Remove(0, 2) = и с битовой маской 1111000011110000

Обратите внимание, что более сложные операции добавления / удаления также могут быть добавлены как битовая логика O (1).

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

Добавление:
Дополнительные минусы:

• Как только размер целого числа будет превышен, каждый добавленный бит к исходным битовым полям удваивает объем памяти. Однако это не намного хуже, чем в типичном сценарии, использующем другую коллекцию, в которой необходимо хранить в среднем половину возможных значений битовой маски (при условии, что в типичном сценарии не хранится гораздо меньше оставшихся значений).

• Как только размер целого числа будет превышен, каждый добавленный бит также удваивает количество операций 'и', необходимых для реализации логики.

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

Дополнительное приложение:
Если вы когда-либо выполняете только операции Remove, которые с течением времени все больше и больше истощают заданное пространство состояний, вы можете расширить этот подход немного дальше (без каламбура), сделав более умную абстракцию, которая каким-то образом только сохраняет отслеживание ненулевых значений int. Обнаружение нулевых значений может быть не таким дорогостоящим, как кажется, если JIT знает, что делает, потому что операция «ЦП» и «операция» обычно устанавливают флаг «ноль», если результат равен нулю.

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

Answer 2

Если вы используете массив для хранения вашего двоичного дерева, вы можете быстро проиндексировать любой элемент (дочерние элементы узла с индексом n имеют индекс (n + 1) * 2 и (n + 1) * 2-1. Все узлы на данном уровне хранятся последовательно. Первый узел на уровне x равен 2 ^ x-1, и на этом уровне есть 2 ^ x элементов.

К сожалению, я не думаю, что это действительно дает вам много места с точки зрения сложности. Удаление всех левых узлов на уровне является O (n / 2) наихудшим случаем, который, конечно, O (n). Конечно, фактическая работа зависит от того, какой бит вы проверяете, поэтому среднее значение может быть несколько лучше. Это также требует O (2 ^ n) памяти, что намного хуже, чем связанный список и совсем не практично.

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

Answer 3

Конечно, это возможно (даже если это «обман»). Просто держите стопку объектов Remove:

struct Remove {
    bool set;
    int index;
}

Функция удаления просто помещает объект в стек. Виола, О (1).

Если вы хотите получить фантазию, ваш стек не может превышать (количество бит) без дублирования или невозможных сценариев.

Остальная часть коллекции должна применять логику всякий раз, когда вещи извлекаются или повторяются.

Два способа сделать вставку в коллекцию:

1. Применить правила удаления при вставке, чтобы очистить стек, сделав в O (n). Должен заплатить где-нибудь.
   • Каждое битовое поле должно хранить свой индекс в стеке удалений, чтобы знать, какие правила применяются к нему. Тогда ограничение размера стека выше не будет иметь значения

Answer 4

Если каждый бит решения и позиция указаны как объекты {значение бита, k-я позиция}, вы получите массив длиной 2 * k. Если вы ссылаетесь на каждую из этих позиций массива из вашего элемента, представленного в виде связанного списка (длиной k), используя указатель на объект {bit, position} в качестве значения узла, вы можете «аннулировать» группу элементы, просто удалив объект {bit, position}. Это потребует от вас при поиске в списке предметов, чтобы найти "завершенные" предметы (это делает поиск действительно медленным?).

Так что-то вроде: [{0,0}, {1,0}, {0,1}, {1, 1}, {0,2}, {1, 2}, {0,3}, {1,3}]

и связано с "0100", представленным как: {0-> 3-> 4-> 6}

Вы не узнаете, какие элементы были недействительными, пока не попытаетесь их найти (поэтому это не ограничивает область поиска, а это то, что вам нужно).

Ну хорошо, я пытался.