가장 많이 방문한 개체의 구조

Question

object에 대한 hit 매개 변수가 수신되어 빈도를 표시하려고합니다. 가장 자주 올 수있는 것은 위로 hit, object s입니다. Unordered_map은 object을 키로하고 hit을 값으로 갖는 첫 번째 파트에 맞습니다.

unordered_map<object,int> 

이 object에 대한 빠른 검색과 hit를 증가 할 수 있습니다. 그러나 정렬 방법은 어떨까요? priority_queue을 사용하면 최상위 히트 객체를 사용할 수 있습니다. 그러나 객체의 히트를 증가시키는 것은 어떻습니까?

Answer 1

가장 최근에 가장 많이 액세스 한 개체가 맨 위에 더 가깝도록 개체를 보관하는 splay tree을 살펴 보시기 바랍니다. 이것은 여러 euristicts에 의존하므로 완벽한 솔루션의 근사치를 제공 할 것입니다.

정확한 해결책을 얻으려면 자신의 binary heap을 구현하고 작업 우선 순위 작업을 구현하는 것이 좋습니다. 이론 상으로는 priority_queue에 대한 백업용으로 사용되지만, 데이터 구조의 연산 복잡도에 영향을주지 않으면 서 수행 할 수있는 반면, 우선 순위 연산은 없습니다.

Answer 2

개체를 삽입 할 때 정렬 된 개체 목록을 조회수로 추적하여 해결할 수있었습니다. 따라서 항상 N 개의 인기 히트 곡 목록이 있습니다. 이 3,000,000 개체는 다음과 나는 여기에 상위 20

을 갖고 싶어 내가 사용하는 구조입니다 :

unordered_map<string, int> key_hit; 

: key_hit이 (키 문자열, 내가 객체를 의미)를 히트를 추적 할 수는

두 개의 배열 : hits[N], keys[N] (상위 히트와 해당 키 (개체) 포함).

unordered_map<string,int> key_idx; 

알고리즘 (상세 없이도) :

idx, hits, keys 
0,  212, x 
1,  200, y 
... 
N,  12,  z 

다른지도 key_idx 키 및 해당 인덱스를 유지

• key가 입력된다.
• key을 key_hit으로 검색하면 해당 횟수와 증가분 (이 값은 충분히 빠름)을 찾습니다.
• hit<hits[N] 인 경우 무시하십시오.
다른
• , idx=key_idx[key], (발견되지 않는 경우는, 구조에 추가하고 기존 하나를 삭제합니다. 너무 오래 모든 세부 사항을 작성하는)는 위의 항목 h[idx-1]<H보다 큰지 여부를
• H=h[idx]++
• 확인하시기 바랍니다. 예인 경우 key_idx, hits, keys에 idx 및 idx-1을 바꿔 넣으십시오.

나는 그것을 빨리 만들려고 노력했다. 하지만 얼마나 빠르지는 모르겠다.