RoaringBitmap
1.3.16
비트맵이라고도 하는 비트세트는 일반적으로 빠른 데이터 구조로 사용됩니다. 불행하게도 너무 많은 메모리를 사용할 수 있습니다. 이를 보완하기 위해 압축된 비트맵을 사용하는 경우가 많습니다.
Roaring 비트맵은 WAH, EWAH 또는 Concise와 같은 기존 압축 비트맵보다 성능이 뛰어난 경향이 있는 압축 비트맵입니다. 어떤 경우에는 굉음이 나는 비트맵이 수백 배 더 빠를 수 있으며 종종 훨씬 더 나은 압축을 제공합니다. 압축되지 않은 비트맵보다 더 빠를 수도 있습니다.
활활 타오르는 비트맵은 여러 중요한 응용 프로그램에서 잘 작동하는 것으로 나타났습니다.
가능하면 비트맵 압축을 위해 Roaring을 사용하십시오. 다른 비트맵 압축 방법을 사용하지 마십시오(Wang et al., SIGMOD 2017)
소프트웨어를 5배 더 빠르게 실행할 수 있는 제품을 만들어주셔서 감사합니다(BigML의 Charles Parker).
이 라이브러리는 다음에서 사용됩니다.
라이브러리는 성숙되었으며 수년 동안 프로덕션에 사용되었습니다.
YouTube SQL 엔진인 Google Procella는 색인 생성을 위해 Roaring 비트맵을 사용합니다. Apache Lucene은 Roaring 비트맵을 사용하지만 자체적으로 독립적으로 구현됩니다. Solr 및 Elastic과 같은 Lucene의 파생물도 Roaring 비트맵을 사용합니다. Whoosh, Microsoft VSTS(Microsoft Visual Studio Team Services) 및 Pilosa와 같은 다른 플랫폼에서도 자체 구현에 Roaring 비트맵을 사용합니다. InfluxDB, Bleve, Cloud Torrent, Redpanda 등에서 Roaring 비트맵을 찾을 수 있습니다.
구현 간의 상호 운용성을 위한 직렬화된 형식 사양이 있습니다. 우리는 상호 운용 가능한 C/C++, Java 및 Go 구현을 보유하고 있습니다.
(c) 2013-... RoaringBitmap 작성자
이 코드는 Apache 라이센스 버전 2.0(AL2.0)에 따라 라이센스가 부여됩니다.
세트는 소프트웨어의 기본 추상화입니다. 해시 세트, 트리 등 다양한 방법으로 구현될 수 있습니다. 데이터베이스와 검색 엔진에서 세트는 종종 인덱스의 필수 부분입니다. 예를 들어, 일부 속성을 충족하는 모든 문서 또는 행(숫자 식별자로 표시) 집합을 유지해야 할 수 있습니다. 집합에서 요소를 추가하거나 제거하는 것 외에도 교집합, 합집합, 집합 간 차이 등을 계산하는 빠른 함수가 필요합니다.
정수 집합을 구현하기 위한 특히 매력적인 전략은 비트맵(비트 집합 또는 비트 벡터라고도 함)입니다. n 비트를 사용하면 [0,n) 범위의 정수로 구성된 모든 집합을 나타낼 수 있습니다. 집합에 정수 i가 있으면 i번째 비트는 1로 설정됩니다. 상용 프로세서는 W=32 또는 W=64비트의 워드를 사용합니다. 그러한 단어를 많이 결합함으로써 우리는 n의 큰 값을 지원할 수 있습니다. 그런 다음 교집합, 합집합 및 차이를 비트 AND, OR 및 ANDNOT 연산으로 구현할 수 있습니다. 더 복잡한 집합 함수는 비트 연산으로 구현될 수도 있습니다.
비트 세트 접근 방식을 적용할 수 있는 경우 몇 배 더 적은 메모리를 사용하면서 다른 가능한 세트 구현(예: 해시 세트)보다 훨씬 더 빠른 속도를 낼 수 있습니다.
그러나 비트 세트는 압축된 비트 세트라도 항상 적용 가능한 것은 아닙니다. 예를 들어 무작위로 보이는 정수가 1000개 있는 경우 간단한 배열이 가장 적합할 수 있습니다. 우리는 이 경우를 "희소" 시나리오라고 부릅니다.
압축되지 않은 BitSet은 많은 메모리를 사용할 수 있습니다. 예를 들어, BitSet을 가져와서 위치 1,000,000의 비트를 true로 설정했는데 100kB가 조금 넘는 경우가 있습니다. 1비트의 위치를 저장하려면 100kB가 넘는다. 메모리에 관심이 없더라도 이는 낭비입니다. 이 BitSet과 1,000,001 위치에 있는 비트가 있는 다른 BitSet 사이의 교차점을 계산해야 한다고 가정하면 원하는지 여부에 관계없이 이러한 0을 모두 통과해야 합니다. 아니면. 그것은 매우 낭비가 될 수 있습니다.
즉, 압축된 비트맵을 사용하려는 시도가 낭비적인 경우가 분명히 있습니다. 예를 들어 우주 크기가 작은 경우입니다. 예를 들어 비트맵은 n이 작은 [0,n)의 정수 집합을 나타냅니다(예: n=64 또는 n=128). 압축되지 않은 BitSet을 사용할 수 있고 메모리 사용량이 늘어나지 않는다면 압축된 비트맵은 아마도 유용하지 않을 것입니다. 실제로 압축이 필요하지 않은 경우 BitSet은 놀라운 속도를 제공합니다.
희소 시나리오는 압축된 비트맵을 사용해서는 안 되는 또 다른 사용 사례입니다. 무작위로 보이는 데이터는 일반적으로 압축할 수 없다는 점을 명심하세요. 예를 들어, 작은 32비트 임의 정수 세트가 있는 경우 정수당 32비트보다 훨씬 적은 수를 사용하는 것은 수학적으로 불가능하며 압축 시도는 비생산적일 수 있습니다.
Roaring에 대한 대부분의 대안은 실행 길이로 인코딩된 비트맵인 압축 비트맵의 대규모 제품군의 일부입니다. 이는 1 또는 0의 장기 실행을 식별하고 이를 표시 단어로 표시합니다. 1과 0의 로컬 혼합이 있는 경우 압축되지 않은 단어를 사용합니다.
이 제품군에는 다양한 형식이 있습니다.
이러한 형식에는 큰 문제가 있지만 어떤 경우에는 심각한 해를 끼칠 수 있습니다. 즉, 무작위 액세스가 없습니다. 주어진 값이 세트에 존재하는지 확인하려면 처음부터 시작하여 전체를 "압축 해제"해야 합니다. 즉, 큰 세트와 큰 세트를 교차시키려면 최악의 경우에도 전체 큰 세트의 압축을 풀어야 한다는 뜻입니다...
Roaring은 이 문제를 해결합니다. 다음과 같은 방식으로 작동합니다. 데이터를 2 16 정수(예: [0, 2 16 ), [2 16 , 2 x 2 16 ), ...)의 청크로 나눕니다. 청크 내에서는 압축되지 않은 비트맵, 간단한 정수 목록 또는 실행 목록을 사용할 수 있습니다. 어떤 형식을 사용하든 모두 하나의 값이 있는지 빠르게 확인할 수 있습니다(예: 이진 검색 사용). 결과적으로 Roaring은 WAH, EWAH, Concise와 같은 실행 길이 인코딩 형식보다 훨씬 빠르게 많은 작업을 계산할 수 있습니다. 놀랍게도 Roaring은 일반적으로 더 나은 압축 비율도 제공합니다.
import org . roaringbitmap . RoaringBitmap ;
public class Basic {
public static void main ( String [] args ) {
RoaringBitmap rr = RoaringBitmap . bitmapOf ( 1 , 2 , 3 , 1000 );
RoaringBitmap rr2 = new RoaringBitmap ();
rr2 . add ( 4000L , 4255L );
rr . select ( 3 ); // would return the third value or 1000
rr . rank ( 2 ); // would return the rank of 2, which is index 1
rr . contains ( 1000 ); // will return true
rr . contains ( 7 ); // will return false
RoaringBitmap rror = RoaringBitmap . or ( rr , rr2 ); // new bitmap
rr . or ( rr2 ); //in-place computation
boolean equals = rror . equals ( rr ); // true
if (! equals ) throw new RuntimeException ( "bug" );
// number of values stored?
long cardinality = rr . getLongCardinality ();
System . out . println ( cardinality );
// a "forEach" is faster than this loop, but a loop is possible:
for ( int i : rr ) {
System . out . println ( i );
}
}
} ./gradlew :examples:runAll 로 실행하거나 ./gradlew :examples:runExampleBitmap64 등으로 특정 예제를 실행할 수 있는 더 많은 예제를 보려면 예제 폴더를 참조하세요.
http://www.javadoc.io/doc/org.roaringbitmap/RoaringBitmap/
github에서 릴리스를 다운로드할 수 있습니다: https://github.com/RoaringBitmap/RoaringBitmap/releases
pom.xml 파일에 다음 종속성을 추가합니다...
< dependency >
< groupId >com.github.RoaringBitmap.RoaringBitmap</ groupId >
< artifactId >roaringbitmap</ artifactId >
< version >1.3.16</ version >
</ dependency >버전 번호를 조정할 수 있습니다.
그런 다음 pom.xml 파일에 저장소를 추가합니다.
< repositories >
< repository >
< id >jitpack.io</ id >
< url >https://jitpack.io</ url >
</ repository >
</ repositories >전체 예제는 https://github.com/RoaringBitmap/JitPackRoaringBitmapProject를 참조하세요.
<dependencies> 요소 내의 pom.xml 파일에 다음 종속성을 추가합니다.
< dependency >
< groupId >org.roaringbitmap</ groupId >
< artifactId >roaringbitmap</ artifactId >
< version >1.3.16</ version >
</ dependency > <repositories> 요소( pom.xml 파일) 내에 GitHub 저장소를 추가합니다...
< repositories >
< repository >
< id >github</ id >
< name >Roaring Maven Packages</ name >
< url >https://maven.pkg.github.com/RoaringBitmap/RoaringBitmap</ url >
< releases >< enabled >true</ enabled ></ releases >
< snapshots >< enabled >true</ enabled ></ snapshots >
</ repository >
</ repositories >전체 예제는 https://github.com/RoaringBitmap/MavenRoaringBitmapProject를 참조하세요.
레지스트리 액세스는 인증에 의해 보호됩니다. 따라서 전역 settings.xml: $HOME.m2settings.xml 에 GitHub 자격 증명을 추가해야 합니다.
GitHub에서 생성할 수 있는 토큰이 필요합니다.
GitHub > Settings > Developer Settings > Personal access tokens > Generate new token
토큰에는 read:packages 권한이 필요합니다. 토큰 식별자는 ghp_ieOkN 과 같은 긴 문자열입니다.
<servers> 요소 내 settings.xml 파일에 다음을 입력합니다.
< server >
< id >github</ id >
< username >lemire</ username >
< password >ghp_ieOkN</ password >
</ server > lemire GitHub 사용자 이름으로 바꾸고 ghp_ieOkN 방금 생성한 토큰 식별자로 바꾸세요.
그런 다음 build.gradle 파일을 다음과 같이 편집하면 됩니다.
plugins {
id ' java '
}
group ' org.roaringbitmap ' // name of your project
version ' 1.0-SNAPSHOT ' // version of your project
repositories {
mavenCentral()
maven {
url ' https://jitpack.io '
}
}
dependencies {
implementation ' com.github.RoaringBitmap.RoaringBitmap:roaringbitmap:1.3.16 '
testImplementation ' junit:junit:3.8.1 '
}전체 예제는 https://github.com/RoaringBitmap/JitPackRoaringBitmapProject를 참조하세요.
먼저 GitHub 자격 증명이 필요합니다. 이동
GitHub > Settings > Developer Settings > Personal access tokens > Generate new token
그리고 read:packages 권한이 있는 토큰을 만듭니다.
GitHub 사용자 이름이 lemire 이고 GitHub 개인 토큰이 ghp_ieOkN 인 경우 시스템 변수를 사용하여 설정할 수 있습니다. Bash에서는 다음과 같이 할 수 있습니다:
export GITHUB_USER=lemire
export GITHUB_PASSWORD=ghp_ieOkN
원하는 경우 gradle.properties 파일에 GitHub 자격 증명을 작성할 수 있습니다.
# gradle.properties
githubUser=lemire
githubPassword=ghp_ieOkN
그런 다음 build.gradle 파일을 다음과 같이 편집하면 됩니다.
plugins {
id ' java '
}
group ' org.roaringbitmap ' // name of your project
version ' 1.0-SNAPSHOT ' // version of your project
repositories {
mavenCentral()
maven {
url ' https://maven.pkg.github.com/RoaringBitmap/RoaringBitmap '
credentials {
username = System . properties[ ' githubUser ' ] ?: System . env . GITHUB_USER
password = System . properties[ ' githubPassword ' ] ?: System . env . GITHUB_PASSWORD
}
}
}
dependencies {
implementation ' org.roaringbitmap:roaringbitmap:1.3.16 '
testImplementation ' junit:junit:3.8.1 '
}전체 예제는 https://github.com/RoaringBitmap/MavenRoaringBitmapProject를 참조하세요.
Java에는 기본 부호 없는 정수가 없지만 정수는 여전히 Roaring 내에서 부호 없는 것으로 간주되며 Integer.compareUnsigned 에 따라 정렬됩니다. 이는 Java가 0, 1, ..., 2147483647, -2147483648, -2147483647,..., -1과 같은 숫자를 정렬한다는 것을 의미합니다. 올바르게 해석하려면 Integer.toUnsignedLong 및 Integer.toUnsignedString 사용할 수 있습니다.
비트맵을 메모리 매핑된 파일에 두려면 대신 org.roaringbitmap.buffer 패키지를 사용할 수 있습니다. 여기에는 ImmutableRoaringBitmap과 MutableRoaringBitmap이라는 두 가지 중요한 클래스가 포함되어 있습니다. MutableRoaringBitmap은 ImmutableRoaringBitmap에서 파생되므로 일정 시간 내에 MutableRoaringBitmap을 ImmutableRoaringBitmap으로 변환(캐스트)할 수 있습니다.
MutableRoaringBitmap의 인스턴스가 아닌 ImmutableRoaringBitmap은 약간의 성능 오버헤드가 있지만 데이터가 어디에나(Java 힙 외부 포함) 상주할 수 있는 유연성이 추가된 ByteBuffer에 의해 지원됩니다.
때때로 디스크에 있는 비트맵(ImmutableRoaringBitmap의 인스턴스)과 Java 메모리에 있는 비트맵을 사용하여 작업해야 할 수도 있습니다. 비트맵이 Java 메모리에 상주한다는 것을 알고 있는 경우 MutableRoaringBitmap 인스턴스를 사용하는 것이 가장 좋습니다. 인스턴스를 수정할 수 있을 뿐만 아니라 속도도 더 빠릅니다. 또한 MutableRoaringBitmap 인스턴스는 ImmutableRoaringBitmap 인스턴스이기도 하므로 ImmutableRoaringBitmap을 기대하는 코드의 상당 부분을 작성할 수 있습니다.
인스턴스 캐스팅을 시도하지 않고 ImmutableRoaringBitmap 인스턴스를 예상하는 코드를 작성하면 개체는 실제로 불변이 됩니다. MutableRoaringBitmap에는 ImmutableRoaringBitmap 인스턴스로 간단히 다시 변환하는 편리한 메서드(toImmutableRoaringBitmap)가 있습니다. 언어 디자인 관점에서 ImmutableRoaringBitmap 클래스의 인스턴스는 ImmutableRoaringBitmap 클래스의 인터페이스에 따라 사용되는 경우에만 변경할 수 없습니다. 클래스가 최종 클래스가 아니므로 다른 인터페이스를 통해 인스턴스를 수정할 수 있습니다. 따라서 우리는 "불변"이라는 용어를 순수주의적인 방식으로 받아들이지 않고 오히려 실제적인 방식으로 받아들입니다.
MutableRoaringBitmap 인스턴스를 ImmutableRoaringBitmap 인스턴스로 캐스팅할 수 있는 이 디자인에 대한 동기 중 하나는 비트맵이 종종 크거나 메모리 할당을 피해야 하는 컨텍스트에서 사용되므로 강제 복사를 피한다는 것입니다. ImmutableRoaringBitmap 및 MutableRoaringBitmap 인스턴스를 혼합하고 일치시켜야 하는 경우 복사본이 예상될 수 있습니다.
다음 코드 샘플은 ByteBuffer에서 ImmutableRoaringBitmap을 생성하는 방법을 보여줍니다. 이러한 경우 생성자는 요청 시 ByteBuffer에서 실제 데이터에 액세스하는 동안 RAM의 메타데이터만 로드합니다.
import org . roaringbitmap . buffer .*;
//...
MutableRoaringBitmap rr1 = MutableRoaringBitmap . bitmapOf ( 1 , 2 , 3 , 1000 );
MutableRoaringBitmap rr2 = MutableRoaringBitmap . bitmapOf ( 2 , 3 , 1010 );
ByteArrayOutputStream bos = new ByteArrayOutputStream ();
DataOutputStream dos = new DataOutputStream ( bos );
// If there were runs of consecutive values, you could
// call rr1.runOptimize(); or rr2.runOptimize(); to improve compression
rr1 . serialize ( dos );
rr2 . serialize ( dos );
dos . close ();
ByteBuffer bb = ByteBuffer . wrap ( bos . toByteArray ());
ImmutableRoaringBitmap rrback1 = new ImmutableRoaringBitmap ( bb );
bb . position ( bb . position () + rrback1 . serializedSizeInBytes ());
ImmutableRoaringBitmap rrback2 = new ImmutableRoaringBitmap ( bb ); 또는 serialize(ByteBuffer) 메서드를 사용하여 ByteBuffer 에 직접 직렬화할 수 있습니다.
and, 또는 xor, Flip과 같은 ImmutableRoaringBitmap에 대한 작업은 RAM에 있는 RoaringBitmap을 생성합니다. 이름에서 알 수 있듯이 ImmutableRoaringBitmap 자체는 수정할 수 없습니다.
이 디자인은 Apache Druid에서 영감을 받았습니다.
테스트 파일 TestMemoryMapping.java에서 완전한 작업 예제를 찾을 수 있습니다.
org.roaringbitmap 패키지의 클래스를 org.roaringbitmap.buffer 패키지의 클래스와 혼합하면 안 됩니다. 호환되지 않습니다. 그러나 동일한 출력으로 직렬화됩니다. org.roaringbitmap 패키지의 코드 성능은 ByteBuffer 인스턴스 사용으로 인한 오버헤드가 없기 때문에 일반적으로 우수합니다.
일반적으로 서로 다른 스레드를 사용하여 동일한 비트맵에 액세스하는 것은 안전하지 않습니다. 비트맵은 성능을 위해 동기화되지 않습니다. 둘 이상의 스레드에서 비트맵에 액세스하려면 동기화를 제공해야 합니다. 그러나 ImmutableBitmapDataProvider 인터페이스를 준수하는 한 여러 스레드에서 변경할 수 없는 비트맵에 액세스할 수 있습니다.
많은 애플리케이션은 직렬화/역직렬화를 위해 Kryo를 사용합니다. 사용자 정의 직렬 변환기(Kryo 5) 덕분에 Kryo에서 Roaring 비트맵을 효율적으로 사용할 수 있습니다.
public class RoaringSerializer extends Serializer < RoaringBitmap > {
@ Override
public void write ( Kryo kryo , Output output , RoaringBitmap bitmap ) {
try {
bitmap . serialize ( new KryoDataOutput ( output ));
} catch ( IOException e ) {
e . printStackTrace ();
throw new RuntimeException ();
}
}
@ Override
public RoaringBitmap read ( Kryo kryo , Input input , Class <? extends RoaringBitmap > type ) {
RoaringBitmap bitmap = new RoaringBitmap ();
try {
bitmap . deserialize ( new KryoDataInput ( input ));
} catch ( IOException e ) {
e . printStackTrace ();
throw new RuntimeException ();
}
return bitmap ;
}
} Roaring Bitmaps는 32비트 사례를 염두에 두고 설계되었지만 64비트 정수에 대한 확장도 있습니다. 이 목적을 위해 Roaring64NavigableMap 및 Roaring64Bitmap 이라는 두 가지 클래스를 제공합니다.
Roaring64NavigableMap 은 기존의 레드-블랙-트리를 사용합니다. 키는 요소의 가장 중요한 32비트를 나타내는 32비트 정수인 반면, 트리의 값은 32비트 Roaring 비트맵입니다. 32비트 Roaring 비트맵은 요소 집합의 최하위 비트를 나타냅니다.
최신 Roaring64Bitmap 접근 방식은 ART 데이터 구조를 사용하여 키/값 쌍을 보유합니다. 키는 가장 중요한 48비트 요소로 구성되는 반면 값은 16비트 Roaring 컨테이너입니다. Leis 등의 The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases에서 영감을 받았습니다. (ICDE '13).
import org . roaringbitmap . longlong .*;
// first Roaring64NavigableMap
LongBitmapDataProvider r = Roaring64NavigableMap . bitmapOf ( 1 , 2 , 100 , 1000 );
r . addLong ( 1234 );
System . out . println ( r . contains ( 1 )); // true
System . out . println ( r . contains ( 3 )); // false
LongIterator i = r . getLongIterator ();
while ( i . hasNext ()) System . out . println ( i . next ());
// second Roaring64Bitmap
bitmap1 = new Roaring64Bitmap ();
bitmap2 = new Roaring64Bitmap ();
int k = 1 << 16 ;
long i = Long . MAX_VALUE / 2 ;
long base = i ;
for (; i < base + 10000 ; ++ i ) {
bitmap1 . add ( i * k );
bitmap2 . add ( i * k );
}
b1 . and ( bitmap2 );64비트 Roaring 비트맵의 직렬화가 지정됩니다. https://github.com/RoaringBitmap/RoaringFormatSpec#extention-for-64-bit-implementations를 참조하세요.
그러나 이는 다음을 전환하여 Roaring64NavigableMap 에 의해서만 구현됩니다.
Roaring64NavigableMap.SERIALIZATION_MODE = Roaring64NavigableMap.SERIALIZATION_MODE_PORTABLE
RangeBitmap 은 범위 쿼리를 지원하는 간결한 데이터 구조입니다. 비트맵에 추가된 각 값은 증분 식별자와 연결되며 쿼리는 쿼리를 충족하는 값과 연결된 식별자의 RoaringBitmap 을 생성합니다. 비트맵에 추가된 모든 값은 별도로 저장되므로 값이 두 번 추가되면 두 번 저장되고 해당 값이 일부 임계값보다 작으면 결과 RoaringBitmap 에 최소 두 개의 정수가 있게 됩니다.
최대 가치를 제공하는 것이 시간과 공간 측면에서 더 효율적입니다. 최대값을 모르는 경우 Long.MAX_VALUE 를 제공하세요. 서명되지 않은 순서는 라이브러리의 다른 곳과 마찬가지로 사용됩니다.
var appender = RangeBitmap . appender ( 1_000_000 );
appender . add ( 1L );
appender . add ( 1L );
appender . add ( 100_000L );
RangeBitmap bitmap = appender . build ();
RoaringBitmap lessThan5 = bitmap . lt ( 5 ); // {0,1}
RoaringBitmap greaterThanOrEqualTo1 = bitmap . gte ( 1 ); // {0, 1, 2}
RoaringBitmap greaterThan1 = bitmap . gt ( 1 ); // {2}
RoaringBitmap equalTo1 = bitmap . eq ( 1 ); // {0, 1}
RoaringBitmap notEqualTo1 = bitmap . neq ( 1 ); // {2} RangeBitmap 은 디스크에 기록되고 메모리에 매핑될 수 있습니다.
var appender = RangeBitmap . appender ( 1_000_000 );
appender . add ( 1L );
appender . add ( 1L );
appender . add ( 100_000L );
ByteBuffer buffer = mapBuffer ( appender . serializedSizeInBytes ());
appender . serialize ( buffer );
RangeBitmap bitmap = RangeBitmap . map ( buffer );직렬화 형식은 리틀 엔디안 바이트 순서를 사용합니다.
자바 받기
./gradlew assemble 컴파일됩니다
./gradlew build 단위 테스트를 컴파일하고 실행합니다.
./gradlew test 테스트를 실행합니다.
./gradlew :roaringbitmap:test --tests TestIterators.testIndexIterator4 TestIterators.testIndexIterator4 테스트만 실행합니다. ./gradlew -i :roaringbitmap:test --tests TestRoaringBitmap.issue623 콘솔에 인쇄하는 동안 TestRoaringBitmap 클래스의 테스트 issue623 만 실행합니다.
./gradlew bsi:test --tests BufferBSITest.testEQ bsi 하위 모듈에서 BufferBSITest.testEQ 테스트만 실행합니다.
RoaringBitmap에 기여할 계획이라면 즐겨 사용하는 IDE에 로드할 수 있습니다.
기여를 초대합니다. 우리는 Google Java 스타일을 사용합니다( roaring_google_checks.xml 참조). ./gradlew spotlessApply 사용하여 코드에 자동으로 적용할 수 있습니다.
코드를 불필요하게 다시 포맷하지 마십시오(특히 comments/javadoc의 경우).
직렬화된 파일에서 처음 4바이트 중 일부는 파일 형식을 나타내는 역할을 하는 "쿠키" 전용입니다.
인식할 수 없는 "쿠키"가 있는 데이터에서 비트맵을 역직렬화하거나 매핑하려고 하면 코드가 프로세스를 중단하고 오류를 보고합니다.
이 문제는 버전 0.4.x 이상으로 업그레이드할 때 0.4.x 이전 버전을 사용하여 Roaring 비트맵을 직렬화한 모든 사용자에게 발생합니다. 이러한 사용자는 직렬화된 비트맵을 새로 고쳐야 합니다.
[0,x)에 N개의 정수가 주어지면 활활 비트맵의 직렬화된 크기(바이트)는 이 범위를 초과해서는 안 됩니다.
8 + 9 * ((long)x+65535)/65536 + 2 * N
즉, 유니버스 크기(x)에 대한 고정 오버헤드가 주어지면 Roaring 비트맵은 정수당 2바이트를 초과하지 않습니다. 보다 정확한 추정을 위해 RoaringBitmap.maximumSerializedSize 호출할 수 있습니다.
항상 이상적인 데이터 구조란 없습니다. Roaring 비트맵이 애플리케이션 프로필에 맞는지 확인해야 합니다. Roaring 비트맵을 압축 측면에서 우수한 대안으로 쉽게 대체할 수 있는 경우가 최소한 두 가지 있습니다.
큰 간격에 걸쳐 있는 임의의 값이 거의 없습니다(즉, 매우 희박한 세트가 있음). 예를 들어, 0, 65536, 131072, 196608, 262144 ... 집합을 선택합니다. 이것이 응용 프로그램의 일반적인 경우 HashSet 또는 간단한 정렬 배열 사용을 고려할 수 있습니다.
연속적인 값을 형성하지 않는 조밀한 임의 값 세트가 있습니다. 예를 들어 0,2,4,...,10000 세트를 생각해 보세요. 이것이 귀하의 응용 프로그램에 일반적이라면 일반적인 비트 세트(예: Java의 BitSet 클래스)를 사용하는 것이 더 나을 수 있습니다.
요소를 무작위로 선택하려면 어떻게 해야 합니까?
Random random = new Random();
bitmap.select(random.nextInt(bitmap.getCardinality()));
JMH 벤치마크를 실행하려면 다음 명령을 사용하십시오.
$ ./gradlew jmh::shadowJar
$ java -jar jmh/build/libs/benchmarks.jar
특정 벤치마크를 실행할 수도 있습니다.
$ java -jar jmh/build/libs/benchmarks.jar 'org.roaringbitmap.aggregation.and.identical.*'
Bash 쉘이 있는 경우 특정 테스트를 자동으로 빌드하고 실행하는 스크립트를 실행할 수도 있습니다.
$ ./jmh/run.sh 'org.roaringbitmap.aggregation.and.identical.*'
https://groups.google.com/forum/#!forum/roaringbitmaps
이 작업은 NSERC 부여 번호 26143의 지원을 받았습니다.
