Redis : 정렬 된 집합에서 최고 점수 구성원을 얻으려면 여전히 O (logN)입니까?

Question

내 코드는 정렬 된 Redis 집합에서 최고 점수 구성원을 자주 얻어야합니다.

zrangebyscore의 시간 복잡도는 O (logN) : http://redis.io/commands/zrangebyscore입니다. 나는 오직 최고 점수를 얻고 싶기 때문에, Redis가 그것을 최적화하여 O (1) 시간에 최고 점수 회원을 되 찾으겠습니까?

Answer 1

Redis 문서는 이러한 최적화에 대해 설명하지 않습니다.

시간 복잡도 : 다음은 ZRANGEBYSCORE 상태 (강조는 추가)에 대한 링크 페이지 정렬 된 세트에 O (로그 (N) + M) N은 요소 수 인과 및 M 수의 요소가 반환됩니다. M이 상수 인 경우 (예 : 항상 LIMIT의 처음 10 개 요소를 묻는 경우) O (log (N))로 간주 할 수 있습니다.

이 점을 감안할 때 정렬 된 집합에 하나의 요소 만 포함되어 있지 않으면 시간 복잡도가 O (1)가 아닌 것으로 보입니다. 오히려 시간 복잡도는 정렬 된 집합의 요소 수에 따라 달라지며 여전히 O (log (N))가됩니다.

Answer 2

ZRANGE의 복잡성이 너무 자주 상위 점수를 얻으려는 경우 정렬 된 집합과 독립적으로 최고 점수를 캐시하면 O (1)로 얻을 수 있습니다.