홈페이지>프로그래밍 관련>C# 소스 코드
다운로드

으르렁거리다

선호하는 컴파일러(GNU GCC, LLVM의 clang, Visual Studio, Apple Xcode, Intel oneAPI)를 완벽하게 지원하는 C(및 C++)의 휴대용 Roaring 비트맵입니다. 오픈 소스 C 소프트웨어의 Awesome C 목록에 포함되어 있습니다.

소개

비트맵이라고도 하는 비트세트는 일반적으로 빠른 데이터 구조로 사용됩니다. 불행하게도 너무 많은 메모리를 사용할 수 있습니다. 이를 보완하기 위해 압축된 비트맵을 사용하는 경우가 많습니다.

Roaring 비트맵은 WAH, EWAH 또는 Concise와 같은 기존 압축 비트맵보다 성능이 뛰어난 경향이 있는 압축 비트맵입니다. Apache Lucene과 같은 여러 주요 시스템과 Solr 및 Elasticsearch, Metamarkets의 Druid, LinkedIn Pinot, Netflix Atlas, Apache Spark, OpenSearchServer, Cloud Torrent, Whoosh, InfluxDB, Pilosa, Bleve, Microsoft Visual Studio Team과 같은 파생 시스템에서 사용됩니다. 서비스(VSTS) 및 eBay의 Apache Kylin. CRoaring 라이브러리는 Apache Doris, ClickHouse, Redpanda 및 StarRocks와 같은 여러 시스템에서 사용됩니다. YouTube SQL 엔진인 Google Procella는 색인 생성을 위해 Roaring 비트맵을 사용합니다.

우리는 이 라이브러리의 설계 및 평가에 대한 동료 검토 기사를 게시했습니다.

  • 활활 타오르는 비트맵: 최적화된 소프트웨어 라이브러리의 구현, 소프트웨어: 실습 및 경험 48 (4), 2018 arXiv:1709.07821

활활 타오르는 비트맵은 여러 중요한 응용 프로그램에서 잘 작동하는 것으로 나타났습니다.

가능하면 비트맵 압축에 Roaring을 사용하십시오. 다른 비트맵 압축 방법을 사용하지 마십시오(Wang et al., SIGMOD 2017)

구현 간의 상호 운용성을 위한 직렬화된 형식 사양이 있습니다. 따라서 C++에서 Roaring Bitmap을 직렬화하고, Java에서 읽고, 수정하고, 다시 직렬화하고, Go 및 Python에서 읽는 것이 가능합니다.

목적

CRoaring의 주요 목표는 최신 하드웨어를 최대한 활용하는 고성능 하위 수준 구현을 제공하는 것입니다. 활발한 비트맵은 이미 Java, Go, Rust... 구현을 통해 다양한 플랫폼에서 사용할 수 있습니다. CRoaring은 최신 하드웨어를 사용하여 뛰어난 성능을 달성하고자 하는 라이브러리입니다.

(c) 2016-... CRoaring 저자.

요구사항

  • Linux, macOS, FreeBSD, Windows(MSYS2 및 Microsoft Visual Studio).
  • ARM, x64/x86 및 POWER 프로세서를 사용하여 라이브러리를 테스트합니다. 우리는 리틀 엔디안 시스템만 지원합니다(빅 엔디안 시스템은 거의 없습니다).
  • C11 표준(GCC 7 이상, LLVM 8 이상(clang), Xcode 11 이상, Microsoft Visual Studio 2022 이상, Intel oneAPI Compiler 2023.2 이상)을 지원하는 최신 C 컴파일러에는 다음이 필요한 선택적 C++ 클래스도 있습니다. C++11 표준을 지원하는 C++ 컴파일러.
  • CMake(프로젝트에 기여하기 위해 사용자는 CMake를 사용하지 않으려는 경우 합병/통합 빌드에 의존할 수 있습니다).
  • CMake 시스템은 git을 사용할 수 있다고 가정합니다.
  • x64 시스템에서 라이브러리는 감지된 CPU 기능을 기반으로 최적화된 함수가 호출되도록 런타임 디스패치를 ​​제공합니다. GCC, clang(버전 9 이상) 및 Visual Studio(2017 이상)에서 작동합니다. 다른 시스템(예: ARM)에는 런타임 디스패치가 필요하지 않습니다.

실제 빅엔디안 시스템에 접근할 수 있는 사람은 거의 없습니다. 그럼에도 불구하고 우리는 에뮬레이터를 통해 IBM s390x와 같은 빅엔디안 시스템을 지원합니다. 리틀엔디안 시스템에서만 지원되는 IO 직렬화는 제외됩니다(문제 423 참조).

빠른 시작

CRoaring 라이브러리는 다른 프로젝트에 더 쉽게 통합할 수 있도록 단일 소스 파일로 통합될 수 있습니다. 또한 중요한 코드를 모두 하나의 컴파일 단위로 컴파일할 수 있도록 함으로써 성능을 향상시킬 수 있습니다. 근거는 SQLite 문서나 해당 Wikipedia 항목을 참조하세요. 이 경로를 선택하는 사용자는 CRoaring의 빌드 시스템(CMake 기반)에 의존할 필요가 없습니다.

우리는 각 릴리스의 일부로 통합된 파일을 제공합니다.

Linux 또는 macOS 사용자는 최신 C 또는 C++ 컴파일러가 설치되어 있고 표준 유틸리티( wget )가 있는 경우 다음 지침을 따를 수 있습니다.

  1. 라이브러리를 디렉토리로 가져옵니다. 
     wget https://github.com/RoaringBitmap/CRoaring/releases/download/v2.1.0/roaring.c
wget https://github.com/RoaringBitmap/CRoaring/releases/download/v2.1.0/roaring.h
wget https://github.com/RoaringBitmap/CRoaring/releases/download/v2.1.0/roaring.hh
  2. 다음 내용으로 demo.c 라는 새 파일을 만듭니다. 
     #include 
#include 
#include "roaring.c"
int main () {
    roaring_bitmap_t * r1 = roaring_bitmap_create ();
    for ( uint32_t i = 100 ; i < 1000 ; i ++ ) roaring_bitmap_add ( r1 , i );
    printf ( "cardinality = %dn" , ( int ) roaring_bitmap_get_cardinality ( r1 ));
    roaring_bitmap_free ( r1 );

    bitset_t * b = bitset_create ();
    for ( int k = 0 ; k < 1000 ; ++ k ) {
            bitset_set ( b , 3 * k );
    }
    printf ( "%zu n" , bitset_count ( b ));
    bitset_free ( b );
    return EXIT_SUCCESS ;
}
  3. 다음 내용으로 demo.cpp 라는 새 파일을 만듭니다. 
    # include < iostream >
# include " roaring.hh " // the amalgamated roaring.hh includes roaring64map.hh
# include " roaring.c "
int main () {
    roaring::Roaring r1;
    for ( uint32_t i = 100 ; i < 1000 ; i++) {
        r1. add (i);
    }
    std::cout << " cardinality = " << r1. cardinality () << std::endl;

    roaring::Roaring64Map r2;
    for ( uint64_t i = 18000000000000000100ull ; i < 18000000000000001000ull ; i++) {
        r2. add (i);
    }
    std::cout << " cardinality = " << r2. cardinality () << std::endl;
    return 0 ;
}
  4. 엮다 
     cc -o demo demo.c
c++ -std=c++11 -o demopp demo.cpp
  5. ./demo 
     cardinality = 900
1000
  6. ./demopp 
     cardinality = 900
cardinality = 900

Roaring을 CPM 종속성으로 사용

CMake 및 CPM을 좋아한다면 CMakeLists.txt 파일에 몇 줄만 추가하여 CRoaring 릴리스를 얻을 수 있습니다. 자세한 내용은 CPM 데모를 참조하세요. 

 cmake_minimum_required ( VERSION 3.10)
project (roaring_demo
  LANGUAGES CXX C
)
set (CMAKE_CXX_STANDARD 17)
set (CMAKE_C_STANDARD 11)

add_executable (hello hello.cpp)
# You can add CPM.cmake like so:
# mkdir -p cmake
# wget -O cmake/CPM.cmake https://github.com/cpm-cmake/CPM.cmake/releases/latest/download/get_cpm.cmake
include (cmake/CPM.cmake)
CPMAddPackage(
  NAME roaring
  GITHUB_REPOSITORY "RoaringBitmap/CRoaring"
  GIT_TAG v2.0.4
  OPTIONS "BUILD_TESTING OFF"
)

target_link_libraries (hello roaring::roaring)

FetchContent와 함께 CMake 종속성으로 사용

CMake가 마음에 들면 CMakeLists.txt 파일에 몇 줄만 추가하여 CRoaring 릴리스를 얻을 수 있습니다. 자세한 내용은 데모를 참조하세요.

CRoaring 라이브러리를 로컬에 설치한 경우 다음 예와 같이 CMake의 find_package 함수와 함께 사용할 수 있습니다. 

 cmake_minimum_required ( VERSION 3.15)

project (test_roaring_install VERSION 0.1.0 LANGUAGES CXX C)

set (CMAKE_CXX_STANDARD 11)
set (CMAKE_CXX_STANDARD_REQUIRED ON )


set (CMAKE_C_STANDARD 11)
set (CMAKE_C_STANDARD_REQUIRED ON )

find_package (roaring REQUIRED)

file (WRITE main.cpp "
#include 
#include " roaring/roaring.hh "
int main() {
  roaring::Roaring r1;
  for (uint32_t i = 100; i < 1000; i++) {
    r1.add(i);
  }
  std::cout << " cardinality = " << r1.cardinality() << std::endl;
  return 0;
}" )

add_executable (repro main.cpp)
target_link_libraries (repro PUBLIC roaring::roaring)

합병

병합된 파일을 직접 생성하려면 bash 스크립트를 호출할 수 있습니다. 

./amalgamation.sh

자동 출력을 선호하는 경우 다음 명령을 사용하여 stdout 리디렉션할 수 있습니다. 

./amalgamation.sh > /dev/null

(Bash 쉘은 Linux 및 macOS에서 표준입니다. Bash 쉘은 Windows에서 Git Shell 이름으로 GitHub 데스크탑의 일부로 사용할 수 있습니다. 따라서 GitHub 데스크탑 내에서 CRoaring GitHub 저장소를 복제한 경우 CRoaring 마우스 오른쪽 버튼으로 클릭할 수 있습니다. , Git Shell 선택한 후 위의 명령을 입력하세요.)

CRoaring 디렉터리에서 스크립트를 호출할 필요는 없습니다. 병합 파일을 작성하려는 모든 디렉터리에서 이를 호출할 수 있습니다.

C 사용자를 위한 세 가지 파일인 roaring.h , roaring.c 및 amalgamation_demo.c ...와 몇 가지 간단한 지침이 생성됩니다. amalgamation_demo.c 파일은 간단한 예인 반면 roaring.h 및 roaring.c 는 "융합된" 파일입니다(프로젝트의 모든 소스 및 헤더 파일 포함). 즉, roaring.h 및 roaring.c 파일을 프로젝트에 복사하기만 하면 바로 사용할 수 있습니다! 라이브러리를 제작할 필요가 없습니다! amalgamation_demo.c 파일을 참조하세요.

API

C 인터페이스는 파일에 있습니다.

  • 포효.h,
  • roaring64.h.

C++ 인터페이스도 있습니다:

  • 포효.아아,
  • roaring64map.hh.

대용량 처리

일부 사용자는 대량의 데이터를 처리해야 합니다. 가능하면 일괄적으로 값을 추가하는 것이 훨씬 빠르고 경제적이므로 이러한 사용자는 addMany (C++) roaring_bitmap_or_many (C) 함수를 알고 있는 것이 중요할 수 있습니다. 또한 runOptimize (C++) 또는 roaring_bitmap_run_optimize (C) 함수를 주기적으로 호출하는 것이 도움이 될 수 있습니다.

마이크로벤치마크 실행

Google 벤치마크로 구성된 마이크로벤치마크가 있습니다. Linux 또는 macOS에서는 다음과 같이 실행할 수 있습니다. 

 cmake -B build -D ENABLE_ROARING_MICROBENCHMARKS=ON
cmake --build build
./build/microbenchmarks/bench

기본적으로 벤치마크 도구는 하나의 데이터 세트(예: CRoaring/benchmarks/realdata/census1881 )를 선택합니다. 우리는 여러 데이터 세트를 보유하고 있으며 다른 데이터 세트를 선택할 수도 있습니다. 

 ./build/microbenchmarks/bench benchmarks/realdata/wikileaks-noquotes

벤치마킹을 위해 일부 기능을 비활성화할 수 있습니다. 예를 들어 x64 프로세서가 있다고 가정하면 프로세서와 컴파일러가 모두 AVX-512를 지원하더라도 AVX-512 없이 코드를 벤치마킹할 수 있습니다. 

 cmake -B buildnoavx512 -D ROARING_DISABLE_AVX512=ON -D ENABLE_ROARING_MICROBENCHMARKS=ON
cmake --build buildnoavx512
./buildnoavx512/microbenchmarks/bench

AVX 또는 AVX-512 없이도 벤치마크할 수 있습니다. 

 cmake -B buildnoavx -D ROARING_DISABLE_AVX=ON -D ENABLE_ROARING_MICROBENCHMARKS=ON
cmake --build buildnoavx
./buildnoavx/microbenchmarks/bench

사용자 정의 메모리 할당자

일반 사용자의 경우 CRoaring은 추가 코드 없이 기본 할당자를 적용합니다. 그러나 사용자 정의 메모리 할당자를 원하는 사람들을 위해 전역 메모리 후크도 제공됩니다. 예는 다음과 같습니다. 

 #include 

int main (){
    // define with your own memory hook
    roaring_memory_t my_hook { my_malloc , my_free ...};
    // initialize global memory hook
    roaring_init_memory_hook ( my_hook );
    // write you code here
    ...
}

기본적으로 다음을 사용합니다. 

 static roaring_memory_t global_memory_hook = {
    . malloc = malloc ,
    . realloc = realloc ,
    . calloc = calloc ,
    . free = free ,
    . aligned_malloc = roaring_bitmap_aligned_malloc ,
    . aligned_free = roaring_bitmap_aligned_free ,
};

free / aligned_free 함수는 free(NULL) / aligned_free(NULL) 가 효과가 없는 C 규칙을 따라야 합니다.

예시(C)

이 예에서는 CRoaring이 빌드되었으며 해당 라이브러리에 연결되어 있다고 가정합니다. 기본적으로 CRoering은 헤더 파일을 roaring 디렉터리에 설치합니다. 합병 스크립트에서 작업하는 경우 사전 구축된 CRoaring 라이브러리에 대해 링크하지 않는 경우 #include "roaring.c" 줄을 추가하고 #include #include "roaring.h" 로 바꿀 수 있습니다. . 

 #include 
#include 
#include 
#include 

bool roaring_iterator_sumall ( uint32_t value , void * param ) {
    * ( uint32_t * ) param += value ;
    return true;  // iterate till the end
}

int main () {
    // create a new empty bitmap
    roaring_bitmap_t * r1 = roaring_bitmap_create ();
    // then we can add values
    for ( uint32_t i = 100 ; i < 1000 ; i ++ ) roaring_bitmap_add ( r1 , i );
    // check whether a value is contained
    assert ( roaring_bitmap_contains ( r1 , 500 ));
    // compute how many bits there are:
    uint32_t cardinality = roaring_bitmap_get_cardinality ( r1 );
    printf ( "Cardinality = %d n" , cardinality );

    // if your bitmaps have long runs, you can compress them by calling
    // run_optimize
    uint32_t expectedsizebasic = roaring_bitmap_portable_size_in_bytes ( r1 );
    roaring_bitmap_run_optimize ( r1 );
    uint32_t expectedsizerun = roaring_bitmap_portable_size_in_bytes ( r1 );
    printf ( "size before run optimize %d bytes, and after %d bytesn" ,
           expectedsizebasic , expectedsizerun );

    // create a new bitmap containing the values {1,2,3,5,6}
    roaring_bitmap_t * r2 = roaring_bitmap_from ( 1 , 2 , 3 , 5 , 6 );
    roaring_bitmap_printf ( r2 );  // print it

    // we can also create a bitmap from a pointer to 32-bit integers
    uint32_t somevalues [] = { 2 , 3 , 4 };
    roaring_bitmap_t * r3 = roaring_bitmap_of_ptr ( 3 , somevalues );

    // we can also go in reverse and go from arrays to bitmaps
    uint64_t card1 = roaring_bitmap_get_cardinality ( r1 );
    uint32_t * arr1 = ( uint32_t * ) malloc ( card1 * sizeof ( uint32_t ));
    assert ( arr1 != NULL );
    roaring_bitmap_to_uint32_array ( r1 , arr1 );
    roaring_bitmap_t * r1f = roaring_bitmap_of_ptr ( card1 , arr1 );
    free ( arr1 );
    assert ( roaring_bitmap_equals ( r1 , r1f ));  // what we recover is equal
    roaring_bitmap_free ( r1f );

    // we can go from arrays to bitmaps from "offset" by "limit"
    size_t offset = 100 ;
    size_t limit = 1000 ;
    uint32_t * arr3 = ( uint32_t * ) malloc ( limit * sizeof ( uint32_t ));
    assert ( arr3 != NULL );
    roaring_bitmap_range_uint32_array ( r1 , offset , limit , arr3 );
    free ( arr3 );

    // we can copy and compare bitmaps
    roaring_bitmap_t * z = roaring_bitmap_copy ( r3 );
    assert ( roaring_bitmap_equals ( r3 , z ));  // what we recover is equal
    roaring_bitmap_free ( z );

    // we can compute union two-by-two
    roaring_bitmap_t * r1_2_3 = roaring_bitmap_or ( r1 , r2 );
    roaring_bitmap_or_inplace ( r1_2_3 , r3 );

    // we can compute a big union
    const roaring_bitmap_t * allmybitmaps [] = { r1 , r2 , r3 };
    roaring_bitmap_t * bigunion = roaring_bitmap_or_many ( 3 , allmybitmaps );
    assert (
        roaring_bitmap_equals ( r1_2_3 , bigunion ));  // what we recover is equal
    // can also do the big union with a heap
    roaring_bitmap_t * bigunionheap =
        roaring_bitmap_or_many_heap ( 3 , allmybitmaps );
    assert ( roaring_bitmap_equals ( r1_2_3 , bigunionheap ));

    roaring_bitmap_free ( r1_2_3 );
    roaring_bitmap_free ( bigunion );
    roaring_bitmap_free ( bigunionheap );

    // we can compute intersection two-by-two
    roaring_bitmap_t * i1_2 = roaring_bitmap_and ( r1 , r2 );
    roaring_bitmap_free ( i1_2 );

    // we can write a bitmap to a pointer and recover it later
    uint32_t expectedsize = roaring_bitmap_portable_size_in_bytes ( r1 );
    char * serializedbytes = malloc ( expectedsize );
    // When serializing data to a file, we recommend that you also use
    // checksums so that, at deserialization, you can be confident
    // that you are recovering the correct data.
    roaring_bitmap_portable_serialize ( r1 , serializedbytes );
    // Note: it is expected that the input follows the specification
    // https://github.com/RoaringBitmap/RoaringFormatSpec
    // otherwise the result may be unusable.
    // The 'roaring_bitmap_portable_deserialize_safe' function will not read
    // beyond expectedsize bytes.
    // We also recommend that you use checksums to check that serialized data corresponds
    // to the serialized bitmap. The CRoaring library does not provide checksumming.
    roaring_bitmap_t * t = roaring_bitmap_portable_deserialize_safe ( serializedbytes , expectedsize );
    if ( t == NULL ) { return EXIT_FAILURE ; }
    const char * reason = NULL ;
    // If your input came from an untrusted source, then you need to validate the
    // resulting bitmap. Failing to do so could lead to undefined behavior, crashes and so forth.
    if (! roaring_bitmap_internal_validate ( t , & reason )) {
        return EXIT_FAILURE ;
    }
    // At this point, the bitmap is safe.
    assert ( roaring_bitmap_equals ( r1 , t ));  // what we recover is equal
    roaring_bitmap_free ( t );
    // we can also check whether there is a bitmap at a memory location without
    // reading it
    size_t sizeofbitmap =
        roaring_bitmap_portable_deserialize_size ( serializedbytes , expectedsize );
    assert ( sizeofbitmap ==
           expectedsize );  // sizeofbitmap would be zero if no bitmap were found
    // We can also read the bitmap "safely" by specifying a byte size limit.
    // The 'roaring_bitmap_portable_deserialize_safe' function will not read
    // beyond expectedsize bytes.
    // We also recommend that you use checksums to check that serialized data corresponds
    // to the serialized bitmap. The CRoaring library does not provide checksumming.
    t = roaring_bitmap_portable_deserialize_safe ( serializedbytes , expectedsize );
    if ( t == NULL ) {
        printf ( "Problem during deserialization.n" );
        // We could clear any memory and close any file here.
        return EXIT_FAILURE ;
    }
    // We can validate the bitmap we recovered to make sure it is proper.
    // If the data came from an untrusted source, you should call
    // roaring_bitmap_internal_validate.
    const char * reason_failure = NULL ;
    if (! roaring_bitmap_internal_validate ( t , & reason_failure )) {
        printf ( "safely deserialized invalid bitmap: %sn" , reason_failure );
        // We could clear any memory and close any file here.
        return EXIT_FAILURE ;
    }
    assert ( roaring_bitmap_equals ( r1 , t ));  // what we recover is equal
    roaring_bitmap_free ( t );

    free ( serializedbytes );

    // we can iterate over all values using custom functions
    uint32_t counter = 0 ;
    roaring_iterate ( r1 , roaring_iterator_sumall , & counter );

    // we can also create iterator structs
    counter = 0 ;
    roaring_uint32_iterator_t * i = roaring_iterator_create ( r1 );
    while ( i -> has_value ) {
        counter ++ ;  // could use    i->current_value
        roaring_uint32_iterator_advance ( i );
    }
    // you can skip over values and move the iterator with
    // roaring_uint32_iterator_move_equalorlarger(i,someintvalue)

    roaring_uint32_iterator_free ( i );
    // roaring_bitmap_get_cardinality(r1) == counter

    // for greater speed, you can iterate over the data in bulk
    i = roaring_iterator_create ( r1 );
    uint32_t buffer [ 256 ];
    while ( 1 ) {
        uint32_t ret = roaring_uint32_iterator_read ( i , buffer , 256 );
        for ( uint32_t j = 0 ; j < ret ; j ++ ) {
            counter += buffer [ j ];
        }
        if ( ret < 256 ) {
            break ;
        }
    }
    roaring_uint32_iterator_free ( i );

    roaring_bitmap_free ( r1 );
    roaring_bitmap_free ( r2 );
    roaring_bitmap_free ( r3 );
    return EXIT_SUCCESS ;
}

압축된 64비트 Roaring 비트맵(C)

또한 C에서 효율적인 64비트 압축 비트맵을 지원합니다. 

  roaring64_bitmap_t *r2 = roaring64_bitmap_create();
  for ( uint64_t i = 100 ; i < 1000 ; i++) roaring64_bitmap_add(r2, i);
  printf ( " cardinality (64-bit) = %d n " , ( int ) roaring64_bitmap_get_cardinality(r2));
  roaring64_bitmap_free (r2);

API는 기존의 32비트 비트맵과 유사합니다. 헤더 파일 roaring64.h 를 참조하세요( roaring.h 와 비교).

기존 비트 세트(C)

우리는 라이브러리의 일부로 규칙 비트 세트(압축되지 않음)를 지원합니다.

간단한 예: 

 bitset_t * b = bitset_create ();
bitset_set ( b , 10 );
bitset_get ( b , 10 ); // returns true
bitset_free ( b ); // frees memory

고급 예: 

 bitset_t * b = bitset_create ();
for ( int k = 0 ; k < 1000 ; ++ k ) {
    bitset_set ( b , 3 * k );
}
// We have bitset_count(b) == 1000.
// We have bitset_get(b, 3) is true
// You can iterate through the values:
size_t k = 0 ;
for ( size_t i = 0 ; bitset_next_set_bit ( b , & i ); i ++ ) {
    // You will have i == k
    k += 3 ;
}
// We support a wide range of operations on two bitsets such as
// bitset_inplace_symmetric_difference(b1,b2);
// bitset_inplace_symmetric_difference(b1,b2);
// bitset_inplace_difference(b1,b2);// should make no difference
// bitset_inplace_union(b1,b2);
// bitset_inplace_intersection(b1,b2);
// bitsets_disjoint
// bitsets_intersect

경우에 따라 Roaring 비트맵을 기존(압축되지 않은) 비트 세트로 변환해야 할 수도 있습니다. 실제로 비트 세트는 어떤 경우에는 더 높은 쿼리 성능과 같은 장점을 가지고 있습니다. 다음 코드는 그렇게 하는 방법을 보여줍니다. 

 roaring_bitmap_t * r1 = roaring_bitmap_create ();
for ( uint32_t i = 100 ; i < 100000 ; i += 1 + ( i % 5 )) {
     roaring_bitmap_add ( r1 , i );
}
for ( uint32_t i = 100000 ; i < 500000 ; i += 100 ) {
     roaring_bitmap_add ( r1 , i );
}
roaring_bitmap_add_range ( r1 , 500000 , 600000 );
bitset_t * bitset = bitset_create ();
bool success = roaring_bitmap_to_bitset ( r1 , bitset );
assert ( success ); // could fail due to memory allocation.
assert ( bitset_count ( bitset ) == roaring_bitmap_get_cardinality ( r1 ));
// You can then query the bitset:
for ( uint32_t i = 100 ; i < 100000 ; i += 1 + ( i % 5 )) {
    assert ( bitset_get ( bitset , i ));
}
for ( uint32_t i = 100000 ; i < 500000 ; i += 100 ) {
    assert ( bitset_get ( bitset , i ));
}
// you must free the memory:
bitset_free ( bitset );
roaring_bitmap_free ( r1 );

어떤 경우에는 규칙 비트 세트( bitset_t * )가 Roaring 비트맵보다 훨씬 더 많은 메모리를 사용할 수 있다는 점에 유의해야 합니다. 벤치마크를 실행하여 비트 세트로의 변환이 귀하의 경우 성능상의 이점을 갖는지 확인해야 합니다.

예(C++)

이 예에서는 CRoaring이 빌드되었으며 해당 라이브러리에 연결되어 있다고 가정합니다. 기본적으로 CRoaring은 헤더 파일을 roaring 디렉토리에 설치하므로 #include "roaring.hh" #include 로 바꿔야 할 수도 있습니다. 합병 스크립트에서 작업하는 경우 미리 빌드된 CRoaring 라이브러리에 연결하지 않는 경우 #include "roaring.c" 줄을 추가할 수 있습니다. 

# include < iostream >

# include " roaring.hh "

using namespace roaring ;

int main () {
    Roaring r1;
    for ( uint32_t i = 100 ; i < 1000 ; i++) {
        r1. add (i);
    }

    // check whether a value is contained
    assert (r1. contains ( 500 ));

    // compute how many bits there are:
    uint32_t cardinality = r1. cardinality ();

    // if your bitmaps have long runs, you can compress them by calling
    // run_optimize
    uint32_t size = r1. getSizeInBytes ();
    r1. runOptimize ();

    // you can enable "copy-on-write" for fast and shallow copies
    r1. setCopyOnWrite ( true );

    uint32_t compact_size = r1. getSizeInBytes ();
    std::cout << " size before run optimize " << size << " bytes, and after "
              << compact_size << " bytes. " << std::endl;

    // create a new bitmap with varargs
    Roaring r2 = Roaring::bitmapOf ( 5 , 1 , 2 , 3 , 5 , 6 );

    r2. printf ();
    printf ( " n " );

    // create a new bitmap with initializer list
    Roaring r2i = Roaring::bitmapOfList ({ 1 , 2 , 3 , 5 , 6 });

    assert (r2i == r2);

    // we can also create a bitmap from a pointer to 32-bit integers
    const uint32_t values[] = { 2 , 3 , 4 };
    Roaring r3 ( 3 , values);

    // we can also go in reverse and go from arrays to bitmaps
    uint64_t card1 = r1. cardinality ();
    uint32_t *arr1 = new uint32_t [card1];
    r1. toUint32Array (arr1);
    Roaring r1f (card1, arr1);
    delete[] arr1;

    // bitmaps shall be equal
    assert (r1 == r1f);

    // we can copy and compare bitmaps
    Roaring z (r3);
    assert (r3 == z);

    // we can compute union two-by-two
    Roaring r1_2_3 = r1 | r2;
    r1_2_3 |= r3;

    // we can compute a big union
    const Roaring *allmybitmaps[] = {&r1, &r2, &r3};
    Roaring bigunion = Roaring::fastunion ( 3 , allmybitmaps);
    assert (r1_2_3 == bigunion);

    // we can compute intersection two-by-two
    Roaring i1_2 = r1 & r2;

    // we can write a bitmap to a pointer and recover it later
    uint32_t expectedsize = r1. getSizeInBytes ();
    char *serializedbytes = new char [expectedsize];
    r1. write (serializedbytes);
    // readSafe will not overflow, but the resulting bitmap
    // is only valid and usable if the input follows the
    // Roaring specification: https://github.com/RoaringBitmap/RoaringFormatSpec/
    Roaring t = Roaring::readSafe (serializedbytes, expectedsize);
    assert (r1 == t);
    delete[] serializedbytes;

    // we can iterate over all values using custom functions
    uint32_t counter = 0 ;
    r1.iterate(
        []( uint32_t value, void *param) {
            *( uint32_t *)param += value;
            return true ;
        },
        &counter);

    // we can also iterate the C++ way
    counter = 0 ;
    for (Roaring::const_iterator i = t. begin (); i != t. end (); i++) {
        ++counter;
    }
    // counter == t.cardinality()

    // we can move iterators to skip values
    const uint32_t manyvalues[] = { 2 , 3 , 4 , 7 , 8 };
    Roaring rogue ( 5 , manyvalues);
    Roaring::const_iterator j = rogue. begin ();
    j. equalorlarger ( 4 );  // *j == 4
    return EXIT_SUCCESS;
}

cmake를 사용하여 빌드(Linux 및 macOS, Visual Studio 사용자는 아래를 참조해야 함)

CRoaring은 표준 cmake 작업 흐름을 따릅니다. 프로젝트의 루트 디렉터리(CRoaring)에서 시작하여 다음을 수행할 수 있습니다. 

 mkdir -p build
cd build
cmake ..
cmake --build .
# follow by 'ctest' if you want to test.
# you can also type 'make install' to install the library on your system
# C header files typically get installed to /usr/local/include/roaring
# whereas C++ header files get installed to /usr/local/include/roaring

( build 디렉터리를 다른 디렉터리 이름으로 바꿀 수 있습니다.) 기본적으로 모든 테스트는 모든 플랫폼에서 빌드됩니다. 테스트 빌드 및 실행을 건너뛰려면 명령줄에 -DENABLE_ROARING_TESTS=OFF 추가하세요.

모든 cmake 프로젝트와 마찬가지로 cmake 명령줄에 -DCMAKE_C_COMPILER=gcc -DCMAKE_CXX_COMPILER=g++ 를 추가하여 사용하려는 컴파일러를 지정할 수 있습니다.

clang 또는 gcc를 사용 중이고 대상 아키텍처를 알고 있는 경우 -DROARING_ARCH=arch 지정하여 아키텍처를 설정할 수 있습니다. 예를 들어 서버가 많지만 가장 오래된 서버가 Intel haswell 아키텍처를 실행하는 경우 - DROARING_ARCH=haswell 지정할 수 있습니다. 이러한 경우 생성된 바이너리는 Haswell 프로세스의 특성을 갖는 프로세서에 최적화되며 이전 아키텍처에서는 실행되지 않을 수 있습니다. man gcc 입력하여 유효한 아키텍처 값 목록을 확인할 수 있습니다. 

 mkdir -p build_haswell
cd build_haswell
cmake -DROARING_ARCH=haswell ..
cmake --build .

디버그 릴리스의 경우 프로젝트의 루트 디렉터리(CRoaring)에서 시작하여 다음을 시도해 보세요. 

 mkdir -p debug
cd debug
cmake -DCMAKE_BUILD_TYPE=Debug -DROARING_SANITIZE=ON ..
ctest

코드가 스타일 규칙을 준수하는지 확인하려면( clang-format 설치되어 있는지 확인하세요): 

 ./tools/clang-format-check.sh

스타일 규칙에 따라 코드 형식을 다시 지정하려면( clang-format 설치되어 있는지 확인하세요): 

 ./tools/clang-format.sh

빌드(Windows의 Visual Studio)

우리는 귀하가 최소한 Visual Studio 2015와 x64 프로세서를 갖춘 일반 Windows PC를 가지고 있다고 가정합니다.

명령줄에서 최소한 Visual Studio 2015를 사용하여 빌드하려면 다음을 수행하세요.

  • GitHub Desktop을 사용하여 복제하는 등 GitHub에서 CRoaring 코드를 가져옵니다.
  • CMake를 설치합니다. 설치할 때 cmake 명령줄에서 사용할 수 있도록 요청하세요.
  • VisualStudio 와 같은 CRoaring 내에 하위 디렉터리를 만듭니다.
  • 셸을 사용하여 새로 생성된 이 디렉터리로 이동합니다. 예를 들어 GitHub Desktop 내에서 GitHub 저장소 목록의 CRoaring 마우스 오른쪽 버튼으로 클릭하고 Open in Git Shell 을 선택한 다음 새로 생성된 셸에 cd VisualStudio 입력할 수 있습니다.
  • VisualStudio 저장소에 있는 동안 셸에 cmake -DCMAKE_GENERATOR_PLATFORM=x64 .. 입력합니다. (또는 정적 라이브러리를 구축하려는 경우 명령줄 cmake -DCMAKE_GENERATOR_PLATFORM=x64 -DROARING_BUILD_STATIC=ON .. 사용할 수 있습니다.)
  • 이 마지막 명령은 새로 생성된 디렉터리(예: RoaringBitmap.sln )에 Visual Studio 솔루션 파일을 생성했습니다. Visual Studio에서 이 파일을 엽니다. 이제 프로젝트를 빌드하고 테스트를 실행할 수 있습니다. 예를 들어 Solution Explorer 창( View 메뉴에서 사용 가능)에서 ALL_BUILD 마우스 오른쪽 버튼으로 클릭하고 Build 선택합니다. 코드를 테스트하려면 여전히 Solution Explorer 창에서 RUN_TESTS 선택하고 Build 선택합니다.

IDE에서 직접 Visual Studio 2017 이상을 사용하여 빌드하려면 다음을 수행하세요.

  • GitHub Desktop을 사용하여 복제하는 등 GitHub에서 CRoaring 코드를 가져옵니다.
  • Visual Studio 내에서 C++ 개발 워크로드를 설치할 때 Visual C++ tools for CMake 선택합니다.
  • Visual Studio 내에서 File > Open > Folder... 사용하여 CRoaring 폴더를 엽니다.
  • Solution Explorer 내의 상위 디렉터리에 있는 CMakeLists.txt 마우스 오른쪽 버튼으로 클릭하고 Build 선택하여 프로젝트를 빌드합니다.
  • 테스트하려면 표준 도구 모음에서 Select Startup Item... 메뉴를 드롭하고 테스트 중 하나를 선택하세요. 드롭다운 왼쪽에 있는 버튼을 눌러 테스트를 실행하세요.

코드에는 AVX2 및 AVX-512에 특정한 최적화가 있으며 런타임 시 감지된 하드웨어를 기반으로 동적으로 변환됩니다.

사용법( conan 사용)

roaring 용으로 사전 빌드된 바이너리를 설치하거나 Conan을 사용하여 소스에서 빌드할 수 있습니다. 최신 버전을 설치하려면 다음 명령을 사용하십시오. 

 conan install --requires="roaring/[*]" --build=missing

Conan 사용 방법에 대한 자세한 지침은 Conan 설명서를 참조하세요.

roaring 의 레시피는 Conan 관리자와 커뮤니티 기여자들에 의해 최신 상태로 유지됩니다. 버전이 오래된 경우 ConanCenterIndex 저장소에서 이슈나 풀 요청을 생성하세요.

사용법(Windows, Linux 및 macOS에서 vcpkg 사용)

Windows, Linux 및 macOS의 vcpkg 사용자는 즐겨 사용하는 셸에서 단일 명령으로 roaring 다운로드하고 설치할 수 있습니다.

Linux 및 macOS의 경우: 

 $ ./vcpkg install roaring

roaring 정적 라이브러리로 빌드하고 설치합니다.

Windows(64비트)의 경우: 

 .vcpkg.exe install roaring:x64-windows

roaring 공유 라이브러리로 빌드하고 설치합니다. 

 .vcpkg.exe install roaring:x64-windows-static

roaring 정적 라이브러리로 빌드하고 설치합니다.

이러한 명령은 MSBuild 또는 CMake 기반 프로젝트에서 라이브러리를 사용하는 방법에 대한 지침도 인쇄합니다.

vcpkg 와 함께 제공되는 roaring 버전이 오래된 버전인 경우 문제를 제출하거나 PR을 작성하여 vcpkg 커뮤니티에 신고해 주세요.

SIMD 관련 제한

AVX2 코드는 부동 소수점 숫자나 곱셈을 사용하지 않으므로 다중 코어 Intel 프로세서에서 터보 주파수 조절이 적용되지 않습니다.

AVX-512 코드는 SIMD별 주파수 조절이 관찰되지 않는 최신 하드웨어(Intel Ice Lake 이상 및 AMD Zen 4)에서만 활성화됩니다.

스레드 안전성

예를 들어 STL 컨테이너와 마찬가지로 CRoaring 라이브러리에는 기본 스레드 지원이 없습니다. 따라서 한 스레드에서 비트맵을 수정할 때마다 다른 스레드에서 이를 쿼리하는 것은 안전하지 않습니다. 그러나 비트맵을 안전하게 복사하고 두 복사본을 모두 사용할 수 있습니다.

확장하다
추가 정보
관련 애플리케이션
추천
관련 정보 전체