Реализация очень эффективной битовой структуры

Question

Я ищу решение в псевдо-коде или Java или JS для следующей проблемы:

Нам нужно реализовать эффективную структуру битов для хранения данных для N битов (вы можете думать о битах кактакже логические, вкл / выкл).

Нам нужно поддерживать следующие методы: init (n) get (index) set (index, True / False) setAll (True / false)

Теперь я нашел решение с помощью o(1) во всем, кроме init, то есть o (n).Идея состояла в том, чтобы создать массив, в котором каждый индекс немного сохраняет значение.Для поддержки setAll я бы также сохранил временную метку с битовым паром, чтобы узнать, брать ли значение из массива tge или из последнего значения setAll tge.O (n) в init потому что нам нужно пройти через массив, чтобы обнулить его, иначе он будет иметь мусор, который может быть НИЧЕГО.Теперь меня попросили найти решение, в котором init также имеет значение o (1) (мы можем создать массив, но мы не можем очистить мусор, мусор может даже выглядеть как действительные данные, что неверно и сделать решение плохим, нам нужнорешение, которое работает на 100%).

Обновление: это алгоритмический вопрос, а не язык.Я столкнулся с этим в вопросе интервью.Также использование целого числа для представления массива битов недостаточно для ограничения объема памяти.Мне подсказали, что это как-то связано с умной обработкой мусорных данных в массиве, не проверяя их в init, используя какой-то механизм, чтобы не упасть, потому что если мусорные данные в массиве (но я неконечно как).

Answer 1

Сделать ленивый структура данных на основе hashmap (хотя иногда hashmap может иметь худшее время доступа, чем o (1)) с 32-битными значениями (8,16,64 дюйма также подходят) для хранения и вспомогательного поля InitFlag

Чтобы очистить все, создайте пустую карту с помощью InitFlag = 0 (удаление старой карты - это работа GC на Java, не так ли?)

Чтобы установить все, создайте пустую карту с помощью InitFlag = 1

. При изменении какого-либо бита проверьте, существует ли соответствующий int-ключ bitnum/32.Если да, просто измените bitnum&32 бит, если нет, и значение бита отличается от InitFlag - создайте ключ со значением на основе InitFlag (все нули или все единицы) и измените необходимый бит.

При получениипроверьте, существует ли соответствующий ключ.Если да, извлеките бит, если нет - получите InitFlag значение

SetAll(0):   ifl = 0, map - {}
SetBit(35):   ifl = 0, map - {1 : 0x10}
SetBit(32):   ifl = 0, map - {1 : 0x12}
ClearBit(32):   ifl = 0, map - {1 : 0x10}
ClearBit(1):   do nothing, ifl = 0, map - {1 : 0x10}
GetBit(1):     key=0 doesn't exist,  return ifl=0
GetBit(35):     key=1 exists,  return map[1]>>3 =1
SetAll(1):      ifl = 1, map = {}
SetBit(35):     do nothing
ClearBit(35):   ifl = 1, map - {1 : 0xFFFFFFF7 = 0b...11110111}
and so on

Answer 2

Если это экзамен по информатике для колледжа / средней школы или домашнее задание - я подозреваю, что они пытаются заставить вас использовать BOOLEAN BIT-WISE LOGIC - особенно, сохраняя бит внутриint или long.Я подозреваю (но я не читаю мысли - и я могу ошибаться!), Что использование «Массивов» - это в точности , чего ваш учитель хотел бы, чтобы вы избегали.

Например, эта цитата скопирована из результатов поиска Google:

long: Тип данных long - это 64-разрядное целое число с дополнением до двух .Подписанный long имеет минимальное значение -263 и максимальное значение 263-1.В Java SE 8 и более поздних версиях вы можете использовать тип данных long для представления 64-битной длины без знака, которая имеет минимальное значение 0 и максимальное значение 264-1

Что это означаетв том, что одна длинная переменная в Java может хранить 64 ваших побитовых значения:

long storage;
// To get the first bit-value, use logical-or ('|') and get the bit.
boolean result1 = (boolean) storage | 0b00000001; // Gets the first bit in 'storage'
boolean result2 = (boolean) storage | 0b00000010; // Gets the second
boolean result3 = (boolean) storage | 0b00000100; // Gets the third
...
boolean result8 = (boolean) storage | 0b10000000; // Gets the eighth result.

Я мог бы написать все для вас, но я не уверен на 100% в ваших реальных спецификациях - есливы используете long, вы можете хранить только 64 отдельных двоичных значения.Если вам нужно произвольное количество значений, вам придется использовать столько «длинных», сколько вам нужно.

Вот SO сообщения о двоичных / логических значениях: Двоичное представление в Java

Вот SO пост о сдвиге битов: Java - Сдвиг по кругу с использованием побитовых операций

Опять это будет работа, и я не собираюсьнапиши весь проект.Однако методы get(int index) и set(int index, boolean val) будут включать побитовое смещение числа 1.

int pos = 1;
pos = pos << 5;  // This would function as a 'pointer' to the fifth element of the binary number list.
storage | pos;  // This retrieves the value stored as position 5.