2
웹 사이트 용 웹 로그 분석을 구축하고 오늘 가장 인기있는 페이지를 N 개 표시하고 싶습니다. 알고리즘은 상수 메모리 및 이동 카운터의 두 가지 요구 사항을 충족해야합니다.오늘 카운트가 가장 많은 N 개의 이벤트가 많습니다.
상수 메모리
페이지의 수십억가있을 수 있습니다, 우리는 그들 모두를 위해 수를 유지하고 싶지 않아요. 알고리즘은 상수 메모리를 사용하는 일종의 스마트 확률 카운터를 사용해야합니다. Count–min sketch이 있지만 모든 요소의 개수를 계산하려고 시도하는 것 같습니다. 모든 요소를 신경 쓰지 않고 최상위 N 만 고려하면 더 간단하고 견적이 더 좋은가?
이동 카운터 탑 N 페이지
는 매일, 오늘 최고 2 페이지 /cats.html 및 /dogs.html 될 수 있지만 내일이 /pizza.html 및 /donuts.html 같은 완전히 다른 일 수 다릅니다. 가장 간단한 방법은 카운터를 매일 다시 시작하는 것이지만 괜찮 으면 좋겠지 만 이동 평균과 같은 더 똑똑한 방법이있을 수 있습니까? 이벤트 스트림의
예 : 만약 내가 올바르게 기억
[
{ page: '/cats.html', time: 'today, 12:00' },
{ page: '/cats.html', time: 'today, 11:00' },
{ page: '/dogs.html', time: 'today, 10:00' },
{ page: '/dogs.html', time: 'today, 09:00' },
{ page: '/donuts.html', time: 'today, 08:00' },
{ page: '/donuts.html', time: 'yesterday, 20:00' },
{ page: '/cats.html', time: 'yesterday, 19:00' },
...
]