검색하는 알고리즘에 공통 이름이 있다고 생각합니다.업데이트 목록 정렬
점수가 큰 선수 목록이 있습니다. 100 만 명 또는 10 억 명 두 번째 플레이어가 점수를 변경하고 정렬 된 목록을 업데이트하여 새 플레이어의 위치를 알고 싶습니다.
점수를 업데이트하고 구멍 목록을 다시 정렬 할 수 있습니다. (비효율적 인) 또는 [oldpos, newpos] (더 나은) 에서 다시 정렬하거나 플레이어를 이동하고 다른 플레이어를 이동할 수 있습니다. (최상)
그런 알고리즘의 이름이 있습니까?
정규 데이터베이스가 효율적으로 해당 작업을 처리하지 못하고 Java, C#, Go 등의 서비스를 개발해야 RAM에서 정렬 된 목록을 유지하고 교대조를 작성해야합니까?
AVL tree 삽입 및 삭제 작업을 O (logn) 시간과 같은 데이터 구조로 유지할 수 있습니다. 플레이어를 업데이트해야 할 때마다 : 트리에서 제거, 점수 변경, 트리에 삽입.
이것은 정확히 당신이 찾고있는 모든 작업에 O (logn)가 필요하며 모든 작업 (조회 및 업데이트 - delete \ insert)이 필요하므로 가장 적합합니다. 메모리 사용량은 O (n) btw입니다.
고맙습니다. 다음과 같은 우려가 있습니다 .1 백만 명의 "플레이어"가 있다면 20 ~ 30 단계 깊이의 나무가됩니다. 메모리 할당 및 메모리 조각화 이 예상을 바꿀 수 있습니까? int32 [1000000] 대 4MB 및 단일 할당입니다. (나는 다른 모든 데이터를 정규 데이터베이스 또는 다른 곳에 보관할 수 있습니다.) 배열에서 플레이어 ID를 이동하는 것이 더 빠르고 예측 가능할 것이라고 생각합니다. 어쨌든 새로운 알고리즘을 발명하지 마십시오. – Artem
일반 SQL 데이터베이스 *는 DB 인덱스가 찾고있는 데이터 구조의 종류이기 때문에 이러한 종류의 작업을 효율적으로 처리해야합니다. 안타깝게도, 그들은 아닙니다 : ( –