Битовая карта
В вычислениях , A растрового отображение из некоторой области (например, диапазон целых чисел) , чтобы биты . Его также называют битовым массивом или индексом битовой карты .
Как существительное, термин «растровое изображение» очень часто используется для обозначения конкретного приложения растрового отображения: пиксельная карта , которая относится к карте пикселей , где каждый может хранить более двух цветов, таким образом, используя более одного бита. на пиксель. В таком случае рассматриваемая область представляет собой массив пикселей, которые составляют устройство вывода цифровой графики (экран или монитор). В некоторых контекстах термин растровое изображение подразумевает один бит на пиксель, в то время как растровое изображение используется для изображений с несколькими битами на пиксель. [1] [2]
Растровое изображение — это тип организации памяти или формат файла изображения, используемый для хранения цифровых изображений . Термин битовая карта происходит от терминологии компьютерного программирования , означающей просто карту битов , пространственно отображенный массив битов . Теперь, наряду с растровым изображением , это обычно относится к аналогичной концепции пространственно отображенного массива пикселей. Растровые изображения в целом могут называться растровыми или растровыми изображениями, синтетическими или фотографическими, в файлах или в памяти.
Многие графические пользовательские интерфейсы используют растровые изображения во встроенных графических подсистемах; [3] , например, Microsoft Windows и OS / 2 Platforms’ GDI подсистема, где формат конкретных используемый является Windows , и / 2 растровый формат файла ОС , как правило , с именем с расширением файла из .BMP (или .DIB для аппаратно-независимого растрового изображения ). Помимо BMP , другие форматы файлов, в которых хранятся буквальные растровые изображения, включают InterLeaved Bitmap (ILBM) , Portable Bitmap (PBM) , X Bitmap (XBM) и Bitmap Wireless Application Protocol (WBMP). . Точно так же большинство других форматов файлов изображений, таких как JPEG , TIFF , PNG и GIF , также хранят растровые изображения (в отличие от векторной графики ), но их обычно не называют растровыми изображениями , поскольку они используют сжатые форматы внутри.
В типичных несжатых растровых изображениях пиксели изображения обычно хранятся с переменным числом бит на пиксель, которые определяют его цвет, глубину цвета . Пиксели размером 8 бит и менее могут представлять оттенки серого или индексированный цвет . Альфа — канал (для прозрачности ) может быть сохранен в виде отдельного растрового изображения, где он похож на черно — белое растровое изображение, или в четвертом канале , что, например, преобразует 24-битные изображения до 32 бит на пиксель.
Биты, представляющие пиксели битовой карты, могут быть упакованы или распакованы (разнесены по границам байтов или слов) в зависимости от формата или требований устройства. В зависимости от глубины цвета пиксель изображения будет занимать не менее n / 8 байт, где n — битовая глубина.
Битовые карты RAID
Если диск был временно отключен от группы RAID, а затем повторно подключен, группе RAID потребуется выполнить синхронизацию всех своих данных. Этот процесс может занять длительное время. Если у группы RAID имеется битовая карта, то в синхронизацию будут включены только те изменения, которые произошли после отсоединения диска, что существенно ускоряет процесс синхронизации.
Временное отключение диска может быть вызвано следующими ситуациями.
- Диск был случайно извлечен из NAS во время работы NAS.
- Неожиданное выключение NAS из-за аппаратной или программной ошибки.
- Пользователь удерживал кнопку включения питания в течение 10 секунд или отключил шнур питания во время работы NAS.
- Битовые карты можно создавать только для групп RAID 1, RAID 5, RAID 6 и RAID 10.
- Активация битовой карты RAID приводит к небольшому снижению производительности операций чтения и записи в группе RAID.
- Битовая карта позволяет оптимизировать время синхронизации только в том случае, если был отсоединен, а затем повторно подключен один и тот диск. Наличие битовой карты не улучшает синхронизацию, если в группу RAID добавляется новый диск.
На уровень выше: Массив RAID
Как мне пригодились битовые карты (Bitmaps)
Для начала вспомним, что такое битовые карты — (wiki) Би́товая ка́рта (англ. bitmap, bitset, bit array) — набор последовательно записанных двоичных разрядов, то есть последовательность (массив) битов.
Начну с задачи: есть выгрузка недействительных, просроченных и утерянных паспортов граждан РФ. Выгрузка представляет из себя csv файл, следующего содержания:
SERIAL,NUMBER
4213,123456
9212,654321
1031,001234
.
Данные в файле не отсортированы, их много (2Gb, ~150 000 000 записей) и обновления происходят ежедневно. Появилась необходимость в быстром обновлении и поиске по файлу.
Для решения испробовано 3 варианта:
1) Сортировка файла с помощью утилиты sort и поиск по отсортированному файлу. Сортировка заняла минимум час, поэтому этот вариант сразу не подошел, не говоря уже и о поиске.
2) Построчное чтение файла с записью в sqllite — 20 минут c индексированием. Поиск достаточно быстрый, но файл базы sqllite занимает 6Gb.
3) Запись файла в Postgres, тоже прошла довольно быстро, но данные и индекс так же занимали больше, чем исходный файл.
Но чувствовало мое сердечко, что можно добиться лучшего результата в использовании жесткого диска. И в какой-то момент я вспомнил про битовые карты, ведь серия и номер паспорта можно закодировать положением бита в файле. Для оптимизации поиска и возможности последовательного обновления я решил для каждой серии создавать свою битовую карту.
Получается, что для каждой серии паспорта будет создаваться битовая карта, которая может хранить информацию о 999 999 паспортах (=125 000 байт). Один байт хранит информацию о 8 паспортах, если бит в нужной позиции равен 1 — паспорт недействителен
Если мы захотим найти паспорт: 3456, 354407, то:
- Вычислим байт, в котором хранится информация о паспорте
354407 div 8 = 44300 - Вычислим бит, в котором хранится информация о паспорте
354407 mod 8 = 7 - Откроем битовую карту для нужной серии, 3456.bitmap
- Откроем файл в режиме чтения и прочитаем только 1 байт в нужной нам позиции.
byte — номер байта
bit_pos_in_file — номер бита в файле
bit_pos_in_byte — номер бита в байте
bit_value — значение бита
Получается поиск по времени ограничен скоростью чтения с диска (на самом деле нет, поиск одного паспорта занимает меньше 1ms и в настоящее время чтение с диска — дешевая операция), а все битовые карты для исходного файла занимают 600Mb (т.к. я не генерирую карту для серий, которых нет в файле).
Хочу отметить плюс этого решения: csv файл со временем будет занимать все больше и больше, а битовые карты будут занимать константное максимальное значение, вычисляемое по формуле:
Количество серий паспортов * Размер битовой карты = 9999 * 125Kb = 1.3Gb
Итог: битовые карты генерируются за 30 секунд и пока занимают 600Мб.
Тесты проводились на MacBook:
CPU: 2,3 GHz 2‑ядерный процессор Intel Core i5
RAM: 8 ГБ 2133 MHz LPDDR3
Как понять и реализовать битовую карту?
Я как-то увидел, что можно реализовать хранение состояний того или иного субъекта с помощью битовой карты. То были состояния кнопки. Каждое состояние закодировано определённой степенью двойки. После записи «стартовых» состояний с ними можно проводить операции с помощью побитовых операторов javascript.
Component.State =
Допустим, состояние HOVERED и FOCUSED будет записано как Component.State[HOVERED | FOCUSED]
Можете рассказать, как это работает? Чтобы было понимание не только на конкретном примере, а чтобы я мог сам писать и обрабатывать такие состояния побитовыми операциями. Мне это показалось очень интересным и довольно-таки применимым, так как код становится логичнее и удобочитаемее. Где-то глубоко в голове я понимаю, что тут что-то происходит с двоичным представлением числа, но это лишь догадки, да и с двоичными числами я знаком только по школьной программе.
Источники для ознакомления приветсвуются. Только не слишком сложные, потому что «академического» образования я не имею и мне, возможно, будет тяжело читать совсем научную литературу.
- Вопрос задан более трёх лет назад
- 1168 просмотров
2 комментария
Простой 2 комментария