HashMap<br>얼마나 빨리

5010 단어 listStringHashMap테스트iteratorreference
맵 사용하기의 코드, unordered 를 사용한 코드도 있습니다.map 혹은hashmap, 물론,hashmap은 표준이 아닙니다, unorderedmap도 boost,tr1, c++ 0x에서만 사용할 수 있습니다.코드의 간결성과 이식성에서 볼 때 표준적인 std::map이 첫 번째 선택이다.
그러나 다른 측면에서 보면 gcc의string은refcounted © on write이고 64비트 환경에서 한string의 추가 비용은 32바이트이다. 만약string 내용의 추가 정렬(8byte align) 비용을 더하면 평균 최소 36바이트로 올라간다.그래서 나의string은 단순히'a'일지라도 전체 메모리는 32+8=40바이트이다.그리고 만약에 우리가 찾을 때stringliteral, 즉smap["a"]와 같은 간단한 사용법을 사용한다면 시스템은tempstring을 만들어서 전달할 것이다......
그래서 저는 Key를 대상으로 하는string을 위한hashmap을 쓰려고 합니다. 그날 오후에 2시간이 걸려서 초보적인 버전을 완성했습니다.
  • strpool을 사용하면 모든string은 연속적인malloc에서 나온 메모리에 존재한다
  • HashNode는 고정 배열을 사용하고 링크는 정수
    • 를 사용합니다.
  • bucket은 단독 int수 그룹을 사용합니다
    • HashNode 정의는 다음과 같습니다.
    struct Node { // in template hash_strmap
    int link; // link to next Node in the same bucket, -1 indicate list end
    unsigned offset; // to strpool, align to 4 or 8
    size_t hash; // cached hash code
    Value value; // could be eliminate from Node and save at a parallel array
};
    string의 길이는 수조에서 두 개의 인접한 Node를 사용할 수 있습니다.오프셋을 상감하여 얻을 수 있으며, 수조는 마지막으로dummy node를 포함하고, 오프셋은strpool의 끝을 가리킨다.
    다른 fstring:
    struct fstring {
    const char* p;
    ptrdiff_t n;
    fstring(const char* s) : p(s), strlen(s) {}
    fstring(const char* s, ptrdiff_t len) : p(s), n(len) {}
    fstring(const std::string& s) : p(s.data()), n(s.size()) {}
};

    hash function, equal function 등 내부의 다른 코드를 더하면...총 130줄입니다. 물론 이 실현된 인터페이스와 표준 stl 용기는 약간의 차이가 있습니다.
    맵, unordered 에 대한 테스트 프로그램을 썼습니다.map, 이 hash 와string 테스트.결과는 놀랍다: 서로 다른 데이터량에 대한hashstrmap은 맵보다 30~40배 빠르고 unordered맵이 5~8배 빠르고 32바이트 길이의 키는 초당 20M회 찾을 수 있다.또한, 예상에 따르면 메모리 사용량도 맵과 unordered 보다맵이 매우 작기 때문에 구체적인 데이터는 더 많은 테스트가 필요합니다.
    이 고무적인 결과를 보고 나는 또 한참이 걸려서hashstrmap의 인터페이스는 표준 stl 용기와 일치하는데 그 중 하나는 좀 번거롭다.
    표준 *map, 그valuetype은 std::pair(value type과Value는 두 가지 물건임을 주의하세요)이고 저는 이것을 실현했습니다. 키의string은strpool을 가리키는 편이입니다. fstring(base+offset,len)을 구성할 수 있지만 Value는 어떻게 합니까? std::pair는reference를 지원하지 않습니다. std::pair는 불법입니다.나의 해결 방법은value 를type은 std::pair처럼 보이는 것으로 정의됩니다.
    그리고valuetype의 문제는iterator로서operator*와operator->,operator*가 실현되려면value 로 되돌아오기만 하면 됩니다.type(value 아님)type & 하면 돼요.operator->어떡하지?되돌아오는 바늘은 임시 대상을 가리킬 수 없습니다. 이것을iterator에 넣을 수 있습니다. 그러나 이것은iterator의 크기를 증가시킵니다. 사용자가operator->를 사용하든지 않든지,operator++와operator를 복잡하게 만들 수 있습니다.무슨 해결 방법이 있습니까?
    물론 있습니다. C++ 표준 규정:operator->는 바늘을 되돌려야 하는 것이 아닙니다. 바늘이 되돌려주는 것이operator->만 지원하면 됩니다. 그래서 저는iterator::pointer를 하나의 대상으로 정의하고...모든 문제가 해결되었다.
    또 하나의 번거로운 문제가 있다. 원소 삭제. 노드가 수조에 놓여 있기 때문에 수조의 원소 삭제 작업의 복잡도는 O(n)이다. 이것은 받아들일 수 없다!어떡하죠?두 가지 방법이 있다.
    1.Node때문에 표시를 합니다.link > = -1, <-1의 값으로 설정하면 됩니다. 그러나 이것은 그룹에 구멍을 남깁니다.
    a. 이 구멍들은 검색에 영향을 주지 않지만iterator,iterate에 영향을 줄 때 구멍을 뛰어넘어야 한다
    2. 삭제할 때 그룹 끝의 Node를 삭제된 곳으로 이동하고 해당하는 링크를 수정하여 그룹 크기를 1로 줄인다. 그러면 구멍이 없지만 키 string의 길이는 인접한 Node이다.offset을 상감하여 획득, 이동 노드는 이 약속을 파괴합니다.따라서 이러한 전략을 실현하려면 키 스트링의 길이를 따로 저장하거나 노드에 저장하거나 스트링의 내용 앞에 저장할 수 밖에 없다.
    a. 이 전략은iterator를 매우 쉽게 실현할 수 있고 iterator는random 이다access iterator
    3. strpool에 구멍이 남는데 어떡하지?이 구멍들을 freelist로 연결하려고 생각했지만 여전히 문제가 있습니다.
    a.strpool 중의 이 구멍들은 길이가 같지 않고 길이마다 하나의list를 분배하는 건가요?아니면 같은 리스트에 넣을까요?
    b. 같은 리스트를 놓고 적당한 사이즈의 블록을 찾는 것은 매우 느리다
    c. 다른list에 놓으려면 하나의 요소가 아니라freelisthead 그룹이 필요합니다
    d. 맵 삭제 요소는 일반적으로 비교적 적게 사용하는데 매우 적게 사용하는 특성을 위해 너무 많은 돈을 지불할 가치가 있습니까?
    이러한 문제점을 감안하여 1, 2가지 전략을 모두 실현했다.strpool은 빈 공간을 방출하지 않고 빈 공간이 일정한 한도값보다 클 때만 긴축하여 그 빈 공간을 없애고 전략 1, 긴축할 때 노드 그룹을 함께 긴축한다. 
    내부적으로 Value Out을 지원합니다. 즉, Value와 Node는 인접한 공간에 저장되지 않습니다.
    마지막으로, Node는 그룹에 저장되어 있기 때문에, 이hashmap은 정렬, 범위 검색을 지원합니다!물론, 이곳의 정렬과 범위 검색은 제한이 있습니다. 맵이 만들어진 후에만 삽입하고 삭제하지 않습니다.sort와 lowerbound/upper_bound/equal_range가 이미 실현되었습니다. 물론, 정렬 후에 다시 링크를 해서 hash에 따라 정확한 검색을 할 수 있도록 해야 합니다.또한, 정렬은 키로 정렬할 수도 있고,value로 정렬할 수도 있다.value로 정렬하면ValueOut은 2분 검색의 속도를 높일 수 있다(메모리 접근의 국부성, 특히 마지막 몇 라운드까지 순환할 때).
    또 다른 세부적인 문제가 있으니 나중에 기회가 되면 다시 쓰자.
    최종적으로 실현된 것은 130줄을 시작한 코드에 비해 1400여 줄로 팽창했다. 물론 효율은 같다.iterator의 실현은 std::map과 unorded 보다map은 수량급이 빠르고 메모리 접근이 매우 좋습니다.
    나중에 Google sparsehashmap의 성능 테스트 코드에 대해 약간의 변경을 해서 저의hash 를 받아들일 수 있도록 했습니다.strmap, 최종적으로 얻은 결과도 매우 좋다. 거의 모든 조작은 테스트에 참가한 모든 맵보다 빠르고 가장 관건적인 삽입/찾기 조작은 다른 모든 맵에서 가장 빠른 맵보다 3배 이상 빠르다. 그리고 그 성능 테스트는 StringKey가 쓴 것이 아니기 때문이다.hashstrmap은 이 방면에서 자신의 장점을 발휘하지 못했습니다. 다음에 상세한 결과를 붙여 드리겠습니다.
    이hash가 생겼어요.strmap, 데이터 분석, 데이터 발굴에서aggregation을 할 때 성능 문제를 걱정할 필요가 없습니다. 다른 저급 오류를 범하지 않으면 IO 문제만 있습니다.가장 간단한 응용:Word Count, 평균 Word 32 바이트에 따라 초당 32*20M = 640M의 데이터를 처리할 수 있다. 낮은 8핵 서버에 대해 640M*8=5120M이다. 만약에 IO+parse가 이렇게 빠르다면.
    2011-09-28: 최신 테스트가 초당 30M에 달하는 조회를 했습니다.
    2011-09-30: iteration의 속도를 테스트하여 std::map보다 150배 이상 빠르고 unordered맵이 130배 빠르다는 것은 당연한 일입니다. 노드는 그룹에 저장되어 있기 때문입니다. 다른 것은 아무리 빨리 옮겨다녀도 그룹을 옮겨다니는 것보다 빠를 수 있습니까?
    reduce() 함수 정리
    Proisma를 사용하여 테이블을 모두 Truncate로 만드는 방법

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage