실시 간 TopN 랭 킹 알고리즘 에 대한 생각

실시 간 TopN 랭 킹 알고리즘 에 대한 생각

0. 머리말

1. TopN 실시 간 순위 알고리즘

1.1 실패 한 방안

1.2 기 존의 데이터 구 조 는?

1.3 합 리 적 인 방안

Reference

0. 머리말
실시 간 순 위 는 인터넷 애플 리 케 이 션 에서 흔히 볼 수 있 는 기능 이다.수요 에 따라 다음 과 같은 몇 가지 로 나 눌 수 있다.

i. TopN 랭 킹

ii. 전체 데이터 순위

일반적인 수요 로 서 우 리 는 다음 과 같은 가설 을 해 야 한다.

a. 사용자 기수 가 비교적 크다

b. 순위 데이터 업데이트 가 빈번 하 다

c. 정렬 에 사용 할 데이터 (score) 범위 가 불확실 합 니 다

d. 순위 로 사용 되 는 score 는 증가 할 뿐 감소 하지 않 습 니 다

.
상기 가설 을 바탕 으로 전체 데이터 순 위 는 대량의 데이터 처리 문제 로 일반적으로 메모리 가 감당 하기 어렵다 고 생각 하고 보통 데이터 베이스 (예 를 들 어 redis) 를 통 해 이 루어 지 므 로 본 고 는 잠시 토론 하지 않 는 다.
1. TopN 실시 간 순위 알고리즘
여기 서 우 리 는 가정 한다.

N 의 범위 가 제한 되 어 있 고 (예 를 들 어 1000) 차 트 데이터 메모리 가 충분히 처리 할 수 있 습 니 다

그럼 문제 가 생 겼 습 니 다.어떻게 데이터 구조 와 알고리즘 을 설계 하여 대량의 사용자 가 빈번하게 차 트 를 업데이트 하 는 상황 에서 실시 간 순위 수 요 를 만족 시 킵 니까?
1.1 실패 한 프로젝트
한 가지 실현 을 본 적 이 있 습 니 다. 방안 은 다음 과 같 습 니 다.

a. 길 이 를 N + 1 로 정의 하 는 배열

b. 데 이 터 를 업데이트 할 때 새 데 이 터 를 배열 의 끝 에 놓 습 니 다

.

c. 배열 을 정렬 하고 배열 의 길이 가 N + 1 이면 꼬리 요소

를 제거 합 니 다.
어떻게 보면 차 트 데이터 가 비교적 작 기 때문에 매번 업데이트 정렬 이 가능 한 것 같 지만 사용자 기수 와 업데이트 빈도 가 증가 함 에 따라 이 알고리즘 은 DB 디자인 이 query 를 index 가 없 는 table 에 세 우 는 것 만큼 무 섭 습 니 다.
업데이트 빈도 가 높 아 지면 서 이 sort 작업 은 CPU 의 악몽 이 될 것 입 니 다.
비효 율 적 인 알고리즘 은 버그 가 나 오지 않 지만 구석 에 숨 어 몰래 CPU 를 먹 는 것 은 발견 되 기 어렵다.
따라서 이 방안 은 바람 직 하지 않다.
1.2 기 존의 데이터 구조?
고전 의 질서 있 는 데이터 구조, 예 를 들 어

검 붉 은 나무

Heap

이런 요 구 를 충족 시 킬 수 있 을 것 같다.
그러나 우 리 는 균형 이 진 트 리 의 효율 적 인 조작 은 빠 른 검색 에 있 지만 나무의 균형 (삽입, 요소 삭제) 을 유지 하 는 것 은 원가 가 높 은 작업 이라는 것 을 알 고 있다.
그래서 바람 직 하지 않다.
1.3 합 리 적 인 방안
이 기능 에 골 치 아 픈 요구 가 있 습 니 다. 바로 클 라 이언 트 가 실시 간 으로 순위 상황 을 볼 수 있어 야 한 다 는 것 입 니 다. 그러면 문제 가 생 겼 습 니 다.

이곳 의 실시 간 은 서버 데이터 가 실시 간 으로 질서 가 있어 야 한 다 는 것 을 의미 합 니까?

답 은 꼭 그렇지 는 않다.우 리 는 정렬 알고리즘 이 컴퓨터 에서 비교적 시간 이 걸 리 는 조작 이 고 빈번 한 정렬 은 더욱 참 을 수 없다 는 것 을 안다.
비교적 실행 가능 한 방안 은 서버 에서 정렬 하지 않 고 차 트 에 TopN 의 데이터 만 기록 하고 실시 간 으로 정렬 된 임 무 를 클 라 이언 트 에 게 맡 기 는 것 이다.

서버 는 어떻게 차 트 에 Top N 의 데이터 만 기록 하도록 보장 합 니까?

데이터 구조 정 의 는 다음 과 같다.

type RankInfo struct{
	name  string     // name of this rank element
	score int		 // rank score
}
type RankList struct {
	list   []*RankInfo 			 // unordered top N rank list
	min    *RankInfo             // the last one who own the minimum score in list
	nameMap map[string]*RankInfo // name->rankInfo
}

포인트 랭 킹 UdateRankList (name, score) 를 업데이트 하 는 작업 절 차 는 다음 과 같 습 니 다 (score 가 증가 만 하고 감소 하지 않 는 다 고 가정 합 니 다).

a. nameMap 에서 지정 한 name 이 차 트 에 있 는 지, 존재 하면 포 인 트 를 업데이트 합 니 다.이 대상 = = min 이면 포인트 최저 대상 의 할당 값 을 다시 찾 아 min 에 게 되 돌려 줍 니 다.

b. list 길이 라면

c. score > min. score 가 있 으 면 min 대상 데 이 터 를 대신 하여 min. name, min. score 를 name, score 로 업데이트 하고 포인트 최저 대상 의 할당 값 을 다시 찾 아 min 에 게 되 돌려 줍 니 다.

d. 주어진 score 는 랭 킹 에 오 를 수 없습니다.

이로써 차 트 업데이트 가 완료 되 었 습 니 다.정렬 이 필요 없고 정렬 된 데이터 구 조 를 지원 하지 않 아 도 되 며 차 트 유지, perfect 를 효율적으로 완성 할 수 있 습 니 다.
Reference

대량의 포인트 데이터 실시 간 순위 처리 방식 소개

실시 간 정렬 알고리즘 (점프 표)

Size Balanced Tree