거대한 비트 마스크에 Java BigInteger를 사용했을 때 성능에 미치는 영향

Question

우리에게는 흥미로운 도전이 있습니다. "bins"에있는 데이터에 대한 액세스를 제어해야합니다. 잠재적으로 수십만 개의 "쓰레기통"이있을 것입니다. 각 저장소에 대한 액세스는 개별적으로 제어되지만 제한 사항은 겹칠 수 있으며 중복 될 수 있습니다. 우리는 각 bin을 비트 마스크 (1,2,3,4 등)에 위치 시키려고합니다.

사용자가 시스템에 로그인하면 그의 보안 속성을보고 그가 볼 수있는 저장소를 결정합니다. 이 정보를 가지고 우리는이 사용자를 위해 비트 마스크를 구성합니다. "설정"비트는 그가 볼 수있는 빈의 식별자에 해당합니다. 그래서 1, 3, 4 칸을 볼 수 있다면 비트 마스크는 1101이 될 것입니다.

그래서 사용자가 데이터를 검색하면 반환 된 행의 bin 인덱스를보고 해당 비트가 설정되어 있는지 확인할 수 있습니다 그의 비트 마스크. 그의 비트 마스크에 비트가 설정되어 있다면 그 행을 볼 수있게합니다. 우리는 비트 마스크가 Java에서 BigInteger으로 저장되도록 계획하고 있습니다.

제 질문은 : 색인 번호가 Integer.MAX_INT보다 커지지 않는다고 가정하면 수십만 비트 위치에 대해 BigInteger 비트 마스크가 확장됩니까? BigInteger.isBitSet(n)을 실행하는 데 영원히 걸릴 수 있습니다. 여기서 n은 큰 수 있습니다 (예 : 874,837)? 그런 BigInteger을 만드는 데 영원히 걸릴까요?

둘째로 : 대체 접근법이 있다면 나는 그것을 듣고 싶습니다.

Answer 1

자주 변경하지 않으면 BigInteger가 빠를 것입니다.

이 종류의 일을 위해 설계된 BitSet이 더 분명히 선택됩니다. 비트를 찾는 경우 성능이 비슷하다고 생각됩니다. 생성/수정을 위해서는 BitSet을 사용하는 것이 더 효율적입니다.

참고 : PaulG는 차이점이 "인상적"이며 BitSet이 빠르다고 말했습니다.

Answer 2

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"); 
} 

우리는 이전 회사와 비슷한 상황에서이 클래스를 사용했으며 성능은 우리의 목적에 부합했습니다.

Answer 3

처음에는 Java BitSet을 사용하여이 인터페이스를 구현할 수있는 고유 한 Java 인터페이스를 정의 할 수 있습니다.

성능 문제가 발생하거나 나중에 사용해야하는 경우 나머지 코드를 변경하지 않고 언제든지 다른 구현 (예 : 캐싱 또는 유사한 개선을 사용하는 구현)을 제공 할 수 있습니다. 필요한 인터페이스에 대해 잘 생각하고 확실하게 long 색인을 선택하십시오. 나중에 구현에서 범위를 벗어나면 (또는 단순히 "no access"를 반환하는 경우) index > Integer.MAX_VALUE에 대해 항상 확인할 수 있습니다.

BigInteger을 사용하면 클래스가 특정 목적을 위해 작성되지 않았으므로 좋은 생각이 아니며 변경하는 유일한 방법은 완전히 새로운 복사본을 만드는 것입니다. 메모리 사용과 관련하여 효율적입니다. 내부적으로 64 비트 길이로 구성된 배열을 사용합니다 (이 순간은 물론 변경할 수 있습니다).

Answer 4

고려해야 할 가치가있는 것 (BitSet 사용)은 다른 세분성을 사용하고 있습니다. 그러므로 각 비트가 여러 개의 실제 비트를 '보호'하는 짧은 비트 세트를 사용합니다. 이렇게하면 숫양에 사용자 당 수백만 비트가 필요하지 않습니다.

이 N/32 같은 설정 작은 비트를 가진이 같은 일을한다 달성하는 간단한 방법 :

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

이 당신에게 그 비트가 대부분의 경우 실제 비트를로드하지 않도록 할 수있는 좋은 기회를 제공합니다 제로. 예상되는 비트 세트와 일치하도록이 접근법을 수정할 수 있습니다. 거의 모든 비트가 설정되어 있다고 예상되는 경우이 비트를 사용하여 보호하는 비트가 모두 설정되어 있으면이 비트를 사용하여 저장할 수 있습니다. 따라서 0이 될 수있는 비트 만 확인하면됩니다.

또한 시작일 수도 있습니다. 사용법 및 요구 사항에 따라 B- 트리 또는 페이지 번호가 매겨진 버전을 사용하여 메모리의 큰 비트 필드 만 유지하려는 경우가 있습니다.