메모리 룩업 테이블 구성(cache)

가장 빠른 방식은 배열이다. 이 방식은 요소의 갯수가 적을 때 유용하다. 다만, 이 배열 방식은 키에 해당 하는 값의 상한 값 만큼의 메모리를 요구한다.

uint64_t look_up[64];

상한 값이 큰 경우에는 해시맵을 이용할 수 있다. 키와 값 쌍을 선언하면 된다.

hash_map<uint64_t, uint64_t> look_up;

다른 방법으로는 pair<uint64_t, uint64_t>의 배열이나 벡터를 생성하고 이를 정렬한 후에 이진 검색하는 방법이 있다.

#include <stdint.h>
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <memory>

const int N = 16000;
typedef std::pair<uint64_t, uint64_t> CALC;
CALC calc[N];

static inline bool cmp_calcs(const CALC &c1, const CALC &c2)
{
    return c1.first < c2.first;
}

int main(int argc, char **argv)
{
    std::iostream::sync_with_stdio(false);
    for (int i = 0; i < N; ++i)
        calc[i] = std::make_pair(i, i);

    std::sort(&calc[0], &calc[N], cmp_calcs);

    for (long i = 0; i < 10000000; ++i) {
        int r = rand() % 16000;
        CALC *p = std::lower_bound(&calc[0], &calc[N], std::make_pair(r, 0), cmp_calcs);
        if (p->first == r)
            std::cout << "found\n";
    }

    return 0; 

}

가령 위와 같은 식으로 작성할 수 있다. 위 코드의 출처는 http://stackoverflow.com/questions/13898687/the-fastest-way-to-store-and-retrieve-lots-of-key-value-pairs 이다.