23 февраля 2010

Использование целочисленного типа данных для размещения логических переменных

Представим себе что у нас есть некоторый объект, который описывается рядом логических параметров (флагов). Например объект у нас будет "спорткомплекс" , а параметрами
1) наличие тренажёрного зала - да/нет
2) наличие басейна - да/нет
3) наличие фитнес центра - да/нет
4) наличие футзала - да/нет
5) наличие боксёрского ринга - да/нет
и т.д.
Задача довольно проста, найболее эффективным образом хранить эти все параметры.
Самым тривиальным является вариант создания 5 булевых членов нашего класса, каждый из которых будет отвечать за свой параметр. Кроме простоты реализации, в памяти эти параметры для каждого экземпляра класса будут занимать всего лишь по 5 бит (1 boolean = 1 bit). Но, что произойдёт если надо передавать такую информацию по сети, да ещё и в более менее осмысленном виде, например в хмл. Каждый из параметров обростёт дополнительными тегами, в результате чего его размер возрастёт в несколько раз. Более того, формирование такого хмл самого по себе потребует определённых ресурсов. Необходимо найти более оптимальный метод хранения этих флагов.
Для решение этой задачи можно воспользоваться типом данных int. Как известно, целочисленный тип данных в джаве состоит из 4 байт - 32 бит. Если представить int в двоичном формате, то это будет ряд из 32х нулей и единиц, а это значит что мы можем разместить в нём аж 32 логических переменных. Для оптимального сохранения boolean переменных в int переменной удобно воспользоваться операцией побитового сдвига.
Например, для размещения флагов из выше изложенного примера, мы воспользуемся первыми 6тью битами целого числа (1й бит будет рабочим, и флаг в нём храниться не будет).
Итак, для примера, что-бы сохранить первые два флага в общей int переменной можно воспользоватся следующим кодом:

// set flag 1
int flag1 = 1; // flag = 0 / 1
int flagPosition = 1;
i = i + (flag1<<flagPosition);
// set flag 2
int flag2 = 1; // flag = 0 / 1
flagPosition = 2;
i = i + (flag2<<flagPosition);
System.out.println(i);

В результате на экран выведется число 6. В двоичной системе 6 = 110, и если отбросить первый служебный 0, то видим что оба флага установлены в единицу. Данный пример можно преобразовать в унифицированную функцию, например следующего вида:
...
int flags = 0;

void setFlags(int flagValue, int flagPosition) {
flags = flags | (flagValue<<flagPosition);
}
...

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

13 комментариев:

Vladimir Dolzhenko комментирует...

а не проще ли завести битовые маски и делать с актуальным значением "битовое или", т.е типа
i |= mask;

кстати, как не трудно понять использование данного подхода подстерегает опасность использовать неправильные данные / неправильный тип - для java 5+ есть такая замечательная вещь как Enum.
Например, мы могли бы описать
public enum SportCenterFeatures {
FITNESS,
SWIMING_POOL,
FOOTBALL,
// etc
}

и для хранения этих параметров использовать EnumSet, который можно параметризовать своим типом.
А вот EnumSet оперирует уже со значениями именно с битовыми масками, т.о. сложность операции чтения, записи и удаления - O(1), а так же эффективное использование памяти, что редко удаётся совместить.

Vladimir Dolzhenko комментирует...

flags = flags + (flagValue<<flagPosition);

если N раз будет выставлена данная позиция, то как бы появится установленным новая фича, которой на самом деле и не было.

Rumoku комментирует...

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

а вот поповоду второго коментария, не понял что имеется ввиду. о какой установленной фиче идёт речь?

Vladimir Dolzhenko комментирует...

допустим, у начальное состояние 0, т.е. flags = 0, теперь добавляем фичу "фитнес", которая идёт первой (т.е индекс 0)

flags += (1 << 0);
итого flags = 1;
теперь же, если ещё раз добавить фитнес, т.е
flags += (1 << 0);

то flags = 2, т.е у нас теперь это не фитнес-центр, а бассейн.

дальше - лучше, как теперь удалить какое-либо поле ?

через
flags |= flagValue << flagPosition;

используя flagValue = 0 не пойдёт, чтобы сбросить бит нужно применить "битовое И"
т.е
void resetValue(int flagPosition){
flags &= 1 << flagPosition;
}
void setValue(int flagPosition){
flags |= 1 << flagPosition;
}

и в итоге придём к своему велосипеду, заменяющему EnumSet ;)
ps. не плодите без надобности сущности.

Vladimir Dolzhenko комментирует...

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

void resetValue(int flagPosition){
flags &= ~(1 << flagPosition);
}

Rumoku комментирует...

Согласен, в моей функции setFlag бага, + надо заменить на побитовое или |, тогда всё будет "пахать".
Кроме того моя же setFlag позволяет(и будет позволять) сбрасывать флаг, всего лишь передав первым параметром 0.

Vladimir Dolzhenko комментирует...

ух ты!
можно пояснить как же оно будет сбрасывать бит, если "всего лишь передав первым параметром 0" (т.е flagValue) ?

когда это 1 | 0 давало 0?

Rumoku комментирует...

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

Vladimir Dolzhenko комментирует...

отдельную обработку для нуля - я уже написал (resetValue)
какое же приумещество этот велосипед будет иметь перед type safety EnumSet'ом ?

Rumoku комментирует...

Ну так изначальная идея была в экономии места/памяти при работе с набором логических флагов у объекта.
Вот например, 2 объекта, у каждого по 2 флага, сериализируем их и видим что разница в занимаемом месте объектами почти в 10 раз. Код представлен ниже.
Хотя проблема выдумана, и возможно такая замена в большинстве задач не целесообразна:).

import java.io.*;
import java.util.EnumSet;

enum Features {
SWIMMING_POOL,/*1*/
FITNES /*2*/
}

class SportsComplex1 implements Serializable {
int features = 0;

void setFeatures(int flagPosition){
features |= 1 << flagPosition;
}
}

class SportsComplex2 implements Serializable {
EnumSet features;
}

public class Test {


public static void main(String[] args) {

SportsComplex1 sc1 = new SportsComplex1();
sc1.setFeatures(1);
sc1.setFeatures(2);

SportsComplex2 sc2 = new SportsComplex2();
sc2.features = EnumSet.of(Features.SWIMMING_POOL, Features.FITNES);

sendObjectByNetwork(sc1);
sendObjectByNetwork(sc2);

}

static void sendObjectByNetwork(Object o){
// stub, just save object to file to check it's size
try {
// Serialize to a file
ObjectOutput out = new ObjectOutputStream(new FileOutputStream("file_"+o.getClass()));
out.writeObject(o);
out.close();
} catch (IOException ee) { }

}



}

Vladimir Dolzhenko комментирует...

фишка в том, что EnumSet сериализуется как строки типа FITNESS,SWIMING_POOL и т.п
это сделано исходя из тех соображений, что если при десериализации поменяется порядок enum'ов, то восстановится всё правильно - ибо восстанавливается через MyEnum.valueOf(stringValue).

Однако, проблема сериализации это не внутреннего представления.
Опять же - никто не запрещает его (де)сериализовать так как он хранится.

Vladimir Dolzhenko комментирует...

т.е. идея о том, что можно упаковывать несколько логических значений используя подход "1 флаг -> 1 бит" - это хороший и верный подход. предоставлять на уровне api такой прямой низкоуровневый доступ - это моветон (надо знать конретные значения, type safety, масштабируемость и т.п).

скорее если и делать то что-то utility-method типа
byte serialize(boolean[] values)
byte serialize(EnumSet values)

и симметричный
boolean[] deserialize(byte value)
EnumSet deserialize(Class enumType, byte value)

TheMalkolm комментирует...

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