Последици за производителността от използването на Java BigInteger за огромна битова маска

Имаме интересно предизвикателство. Трябва да контролираме достъпа до данни, които се намират в "кошчета". Потенциално ще има стотици хиляди „кошчета“. Достъпът до всеки контейнер се контролира индивидуално, но ограниченията могат и вероятно ще се припокриват. Мислим да присвоим на всеки контейнер позиция в битова маска (1,2,3,4 и т.н.).

След това, когато потребител влезе в системата, ние преглеждаме неговите атрибути за сигурност и определяме кои контейнери му е позволено да вижда. С тази информация изграждаме битова маска за този потребител, където "настроените" битове съответстват на идентификатора на кошчетата, които му е позволено да вижда. Така че, ако може да види контейнери 1, 3 и 4, битовата му маска ще бъде 1101.

Така че, когато потребител търси в данните, можем да погледнем индекса на bin на върнатия ред и да видим дали този бит е зададен на неговата битова маска. Ако битовата му маска има този бит, ние му позволяваме да види този ред. Планираме битовата маска да се съхранява като BigInteger в Java.

Въпросът ми е: Ако приемем, че числото на индекса не стане по-голямо от Integer.MAX_INT, битова маска BigInteger ще се мащабира ли за стотици хиляди битови позиции? Ще отнеме ли цяла вечност да се изпълнява BigInteger.isBitSet(n), където n може да е огромно (напр. 874 837)? Ще отнеме ли цяла вечност създаването на такова BigInteger?

И второ: ако имате алтернативен подход, ще се радвам да го чуя.


java biginteger bitmask
person PaulG    schedule 19.09.2012    source източник
comment
Може би BitSet?   -  person Piotr Praszmo    schedule 19.09.2012
comment
Може би различно решение? Вече казвате, че вашето решение не се мащабира. Огромни растерни изображения в паметта + (надяваме се) много потребители = лоша идея.   -  person Augusto    schedule 19.09.2012
comment
@Banthar най-накрая се използва за BitSet... Най-големият проблем с BitSet (мисля) е, че има малко или никакви методи за конвертиране към/от BitSet, следователно не се използва толкова много - нула пъти в Java API последния път, когато погледна.   -  person Maarten Bodewes    schedule 19.09.2012
comment
@Augusto, не съм казал, че не се мащабира. Тествах го до 2000 позиции на битова маска и успях да изпълня милион произволни теста с да/не (е бит x зададен) за 0,2 секунди. Предполагам, че трябва да направя някои тестове за производителност за милиони битови позиции. (-1 за мен). Въпросът ми беше по-скоро насочен към това колко лошо е да се използва BigInteger за това. Свиня на паметта ли е? Излиза ли някъде, където перфомансът отива надолу по тръбата? и т.н   -  person PaulG    schedule 19.09.2012
comment
@owlstead, подобрено е в Java 7. Например вече можете да създадете BitSet от байтов масив.   -  person finnw    schedule 19.09.2012
comment
@finnw благодаря, ще го разгледам веднага. Аз сам създадох няколко общи класа, за да създам EnumSet от флагове (битове) в BitSet и BigInteger. Може би най-накрая трябва да споделя и това.   -  person Maarten Bodewes    schedule 20.09.2012

Отговори (4)


arrow_upward
4
arrow_downward

BigInteger трябва да е бърз, ако не го променяте често.

По-очевиден избор би бил BitSet, който е предназначени за такива неща. За търсене на битове подозирам, че производителността е подобна. За създаване/модифициране би било по-ефективно да използвате BitSet.

Забележка: PaulG коментира, че разликата е "впечатляваща" и BitSet е по-бърз.

person Peter Lawrey    schedule 19.09.2012
comment
Благодаря, Питър, това е посоката, в която ще тръгна. Направих някои изследвания на BitSet и предимството в производителността пред BigInteger е впечатляващо. - person PaulG; 20.09.2012

arrow_upward
2
arrow_downward

Java има по-удобен клас за това, наречен BitSet.

Не е необходимо да проверявате дали битът е зададен в цикъл: можете да направите маска, да използвате побитово and и да видите дали резултатът не е празен, за да решите дали да предоставите или откажете достъпа:

BitSet resourceAccessMask = ...
BitSet userAllowedAccessMask = ...
BitSet test = (BitSet)resourceAccessMask.clone();
test.and(userAllowedAccessMask);
if (!test.isEmpty()) {
    System.out.println("access granted");
} else {
    System.out.println("access denied");
}

Използвахме този клас в подобна ситуация в предишната ми компания и производителността беше приемлива за нашите цели.

person Sergey Kalinichenko    schedule 19.09.2012
comment
Благодаря за примерния код, бих искал да приема два отговора, тъй като бяхте само няколко минути зад Питър. :) Следващият път. - person PaulG; 20.09.2012
comment
@PaulG Това се случва, когато напишете примерен код ;-) Успех с вашия проект! - person Sergey Kalinichenko; 20.09.2012

arrow_upward
1
arrow_downward

Можете да дефинирате свой собствен Java интерфейс за това, като първоначално използвате Java BitSet за реализиране на този интерфейс.

Ако се сблъскате с проблеми с производителността или ако се нуждаете от използването на long по-късно, винаги можете да предоставите различна реализация (напр. такава, която използва кеширане или подобни подобрения), без да променяте останалата част от кода. Помислете добре за интерфейса, от който се нуждаете, и изберете long индекс, за да сте сигурни, че винаги можете да проверите дали е извън границите при изпълнението по-късно (или просто да върнете "няма достъп" първоначално) за всичко index > Integer.MAX_VALUE.

Използването на BigInteger не е толкова добра идея, тъй като класът не е написан за тази конкретна цел и единственият начин да го промените е да създадете напълно ново копие. Той е ефективен по отношение на използването на паметта; той използва вътрешно масив, състоящ се от 64 бита дълги (в момента това разбира се може да се промени).

person Maarten Bodewes    schedule 19.09.2012
comment
Нямам нищо против да ме гласуват против, но мразя да ме гласуват против, без да знам защо. Моля обяснете. - person Maarten Bodewes; 20.09.2012

arrow_upward
0
arrow_downward

Едно нещо, което трябва да се обмисли (освен използването на BitSet), е използването на различна детайлност. Следователно вие използвате по-къс набор от битове, където всеки бит „пази“ множество реални бита. По този начин няма да е необходимо да имате милиони битове на потребител в ram.

Лесен начин да постигнете това е да имате по-малък бит като n/32 и да направите нещо подобно:

boolean isSet(int n) {
    return guardingBits.isSet(n / 32) && realBits.isSet(n);
}

Това ви дава добър шанс да избегнете зареждането на реалните битове, ако тези битове са предимно нула. Можете да промените този подход, за да съответства на очаквания набор от битове. Ако очаквате, че почти всички битове са зададени, можете да използвате тези битове за защита за съхраняване на единица, ако всички битове, които той защитава, са зададени. Така че трябва да проверите само за битове, които може да са нула.

Също така това може да е дори началото. В зависимост от употребата и изискванията може да искате да използвате B-дърво или пагинирана версия, където сте запазили само част от голямото битово поле в паметта.

person Martin Kersten    schedule 09.12.2013