기억할 수있는 간단한 가능성은 일반적인 경우 값당 2 비트의 압축 배열을 유지하고 값당 4 바이트 (원래 요소 인덱스의 경우 24 비트, 실제 값의 경우 8 비트 (idx << 8) | value))로 분리 된 배열을 유지하는 것입니다. 다른 것들.

값을 찾을 때 먼저 2bpp 배열에서 조회를 수행합니다 (O (1)). 0, 1 또는 2를 찾으면 원하는 값입니다. 3을 찾으면 2 차 배열에서 찾아야한다는 의미입니다. 여기에서 이진 검색을 수행하여 8만큼 왼쪽으로 이동 한 관심 지수 (이것은 1 % 여야하므로 작은 n을 갖는 O (log (n))를 찾고 4에서 값을 추출합니다. 바이트 물건.

std::vector<uint8_t> main_arr;
std::vector<uint32_t> sec_arr;

uint8_t lookup(unsigned idx) {
    // extract the 2 bits of our interest from the main array
    uint8_t v = (main_arr[idx>>2]>>(2*(idx&3)))&3;
    // usual (likely) case: value between 0 and 2
    if(v != 3) return v;
    // bad case: lookup the index<<8 in the secondary array
    // lower_bound finds the first >=, so we don't need to mask out the value
    auto ptr = std::lower_bound(sec_arr.begin(), sec_arr.end(), idx<<8);
#ifdef _DEBUG
    // some coherency checks
    if(ptr == sec_arr.end()) std::abort();
    if((*ptr >> 8) != idx) std::abort();
#endif
    // extract our 8-bit value from the 32 bit (index, value) thingie
    return (*ptr) & 0xff;
}

void populate(uint8_t *source, size_t size) {
    main_arr.clear(); sec_arr.clear();
    // size the main storage (round up)
    main_arr.resize((size+3)/4);
    for(size_t idx = 0; idx < size; ++idx) {
        uint8_t in = source[idx];
        uint8_t &target = main_arr[idx>>2];
        // if the input doesn't fit, cap to 3 and put in secondary storage
        if(in >= 3) {
            // top 24 bits: index; low 8 bit: value
            sec_arr.push_back((idx << 8) | in);
            in = 3;
        }
        // store in the target according to the position
        target |= in << ((idx & 3)*2);
    }
}

제안한 것과 같은 배열의 경우 첫 번째 배열의 경우 10000000 / 4 = 2500000 바이트에 두 번째 배열의 경우 10000000 * 1 % * 4 B = 400000 바이트가 필요합니다. 따라서 2900000 바이트, 즉 원래 어레이의 3 분의 1 미만이며 가장 많이 사용 된 부분은 모두 메모리에 함께 보관되므로 캐싱에 적합해야합니다 (L3에 적합 할 수도 있음).

24 비트 이상의 주소 지정이 필요한 경우 “보조 저장소”를 조정해야합니다. 그것을 확장하는 간단한 방법은 256 요소 포인터 배열을 사용하여 인덱스의 상위 8 비트를 전환하고 위와 같이 24 비트 인덱스 정렬 배열로 전달하는 것입니다.

빠른 벤치 마크

#include <algorithm>
#include <vector>
#include <stdint.h>
#include <chrono>
#include <stdio.h>
#include <math.h>

using namespace std::chrono;

/// XorShift32 generator; extremely fast, 2^32-1 period, way better quality
/// than LCG but fail some test suites
struct XorShift32 {
    /// This stuff allows to use this class wherever a library function
    /// requires a UniformRandomBitGenerator (e.g. std::shuffle)
    typedef uint32_t result_type;
    static uint32_t min() { return 1; }
    static uint32_t max() { return uint32_t(-1); }

    /// PRNG state
    uint32_t y;

    /// Initializes with seed
    XorShift32(uint32_t seed = 0) : y(seed) {
        if(y == 0) y = 2463534242UL;
    }

    /// Returns a value in the range [1, 1<<32)
    uint32_t operator()() {
        y ^= (y<<13);
        y ^= (y>>17);
        y ^= (y<<15);
        return y;
    }

    /// Returns a value in the range [0, limit); this conforms to the RandomFunc
    /// requirements for std::random_shuffle
    uint32_t operator()(uint32_t limit) {
        return (*this)()%limit;
    }
};

struct mean_variance {
    double rmean = 0.;
    double rvariance = 0.;
    int count = 0;

    void operator()(double x) {
        ++count;
        double ormean = rmean;
        rmean     += (x-rmean)/count;
        rvariance += (x-ormean)*(x-rmean);
    }

    double mean()     const { return rmean; }
    double variance() const { return rvariance/(count-1); }
    double stddev()   const { return std::sqrt(variance()); }
};

std::vector<uint8_t> main_arr;
std::vector<uint32_t> sec_arr;

uint8_t lookup(unsigned idx) {
    // extract the 2 bits of our interest from the main array
    uint8_t v = (main_arr[idx>>2]>>(2*(idx&3)))&3;
    // usual (likely) case: value between 0 and 2
    if(v != 3) return v;
    // bad case: lookup the index<<8 in the secondary array
    // lower_bound finds the first >=, so we don't need to mask out the value
    auto ptr = std::lower_bound(sec_arr.begin(), sec_arr.end(), idx<<8);
#ifdef _DEBUG
    // some coherency checks
    if(ptr == sec_arr.end()) std::abort();
    if((*ptr >> 8) != idx) std::abort();
#endif
    // extract our 8-bit value from the 32 bit (index, value) thingie
    return (*ptr) & 0xff;
}

void populate(uint8_t *source, size_t size) {
    main_arr.clear(); sec_arr.clear();
    // size the main storage (round up)
    main_arr.resize((size+3)/4);
    for(size_t idx = 0; idx < size; ++idx) {
        uint8_t in = source[idx];
        uint8_t &target = main_arr[idx>>2];
        // if the input doesn't fit, cap to 3 and put in secondary storage
        if(in >= 3) {
            // top 24 bits: index; low 8 bit: value
            sec_arr.push_back((idx << 8) | in);
            in = 3;
        }
        // store in the target according to the position
        target |= in << ((idx & 3)*2);
    }
}

volatile unsigned out;

int main() {
    XorShift32 xs;
    std::vector<uint8_t> vec;
    int size = 10000000;
    for(int i = 0; i<size; ++i) {
        uint32_t v = xs();
        if(v < 1825361101)      v = 0; // 42.5%
        else if(v < 4080218931) v = 1; // 95.0%
        else if(v < 4252017623) v = 2; // 99.0%
        else {
            while((v & 0xff) < 3) v = xs();
        }
        vec.push_back(v);
    }
    populate(vec.data(), vec.size());
    mean_variance lk_t, arr_t;
    for(int i = 0; i<50; ++i) {
        {
            unsigned o = 0;
            auto beg = high_resolution_clock::now();
            for(int i = 0; i < size; ++i) {
                o += lookup(xs() % size);
            }
            out += o;
            int dur = (high_resolution_clock::now()-beg)/microseconds(1);
            fprintf(stderr, "lookup: %10d µs\n", dur);
            lk_t(dur);
        }
        {
            unsigned o = 0;
            auto beg = high_resolution_clock::now();
            for(int i = 0; i < size; ++i) {
                o += vec[xs() % size];
            }
            out += o;
            int dur = (high_resolution_clock::now()-beg)/microseconds(1);
            fprintf(stderr, "array:  %10d µs\n", dur);
            arr_t(dur);
        }
    }

    fprintf(stderr, " lookup |   ±  |  array  |   ±  | speedup\n");
    printf("%7.0f | %4.0f | %7.0f | %4.0f | %0.2f\n",
            lk_t.mean(), lk_t.stddev(),
            arr_t.mean(), arr_t.stddev(),
            arr_t.mean()/lk_t.mean());
    return 0;
}

(코드와 데이터는 항상 내 Bitbucket에서 업데이트됩니다)

위의 코드는 게시물에 지정된 OP로 분산 된 임의의 데이터로 10M 요소 배열을 채우고 내 데이터 구조를 초기화 한 다음 :

• 내 데이터 구조로 10M 요소의 무작위 조회를 수행합니다.
• 원래 배열을 통해 동일하게 수행합니다.

(순차적 조회의 경우 배열은 항상 캐시에 친숙한 조회이므로 엄청나게 이깁니다.)

이 마지막 두 블록은 50 번 반복되고 시간이 정해집니다. 마지막으로, 각 유형의 조회에 대한 평균 및 표준 편차가 속도 향상 (lookup_mean / array_mean)과 함께 계산 및 인쇄됩니다.

-O3 -static우분투 16.04에서 g ++ 5.4.0 ( 및 일부 경고)으로 위의 코드를 컴파일하고 일부 컴퓨터에서 실행했습니다. 그들 대부분은 Ubuntu 16.04, 일부 오래된 Linux, 일부 새로운 Linux를 실행하고 있습니다. 이 경우 OS가 전혀 관련이 없다고 생각합니다.

            CPU           |  cache   |  lookup (µs)   |     array (µs)  | speedup (x)
Xeon E5-1650 v3 @ 3.50GHz | 15360 KB |  60011 ±  3667 |   29313 ±  2137 | 0.49
Xeon E5-2697 v3 @ 2.60GHz | 35840 KB |  66571 ±  7477 |   33197 ±  3619 | 0.50
Celeron G1610T  @ 2.30GHz |  2048 KB | 172090 ±   629 |  162328 ±   326 | 0.94
Core i3-3220T   @ 2.80GHz |  3072 KB | 111025 ±  5507 |  114415 ±  2528 | 1.03
Core i5-7200U   @ 2.50GHz |  3072 KB |  92447 ±  1494 |   95249 ±  1134 | 1.03
Xeon X3430      @ 2.40GHz |  8192 KB | 111303 ±   936 |  127647 ±  1503 | 1.15
Core i7 920     @ 2.67GHz |  8192 KB | 123161 ± 35113 |  156068 ± 45355 | 1.27
Xeon X5650      @ 2.67GHz | 12288 KB | 106015 ±  5364 |  140335 ±  6739 | 1.32
Core i7 870     @ 2.93GHz |  8192 KB |  77986 ±   429 |  106040 ±  1043 | 1.36
Core i7-6700    @ 3.40GHz |  8192 KB |  47854 ±   573 |   66893 ±  1367 | 1.40
Core i3-4150    @ 3.50GHz |  3072 KB |  76162 ±   983 |  113265 ±   239 | 1.49
Xeon X5650      @ 2.67GHz | 12288 KB | 101384 ±   796 |  152720 ±  2440 | 1.51
Core i7-3770T   @ 2.50GHz |  8192 KB |  69551 ±  1961 |  128929 ±  2631 | 1.85

결과는 … 혼합입니다!

1. 일반적으로 이러한 머신의 대부분에는 속도가 다소 떨어지거나 최소한 동등합니다.
2. 어레이가 실제로 “스마트 구조”조회를 능가하는 두 가지 경우는 캐시가 많고 특히 사용량이 많지 않은 컴퓨터에 있습니다. 위의 Xeon E5-1650 (15MB 캐시)은 야간 유휴 상태입니다. Xeon E5-2697 (35MB 캐시)은 유휴 상태에서도 고성능 계산을위한 기계입니다. 원래 어레이는 거대한 캐시에 완전히 들어 맞기 때문에 컴팩트 한 데이터 구조는 복잡성을 증가시킵니다.
3. “성능 스펙트럼”의 반대편에 있지만 어레이가 약간 더 빠를 경우 NAS에 전원을 공급하는 겸손한 Celeron이 있습니다. 캐시가 너무 적기 때문에 배열이나 “스마트 구조”가 전혀 맞지 않습니다. 캐시가 작은 다른 컴퓨터도 비슷한 성능을 발휘합니다.
4. Xeon X5650은주의해서 사용해야합니다. 매우 바쁜 듀얼 소켓 가상 머신 서버의 가상 머신입니다. 명목상으로는 상당한 양의 캐시가 있지만 테스트 시간 동안 완전히 관련되지 않은 가상 머신에 의해 여러 번 선점됩니다.

답변

unsigned char lookup(int index) {
    int code = (bmap[index>>2]>>(2*(index&3)))&3;
    if (code != 3) return code;
    return full_array[index];
}