zrange complexity

[Frank Wilson]

The ZRANGE command reference (http://redis.io/commands/zrange) states
that the command has

"O(log(N)+M) complexity with N being the number of elements in the
sorted set and M the number of elements returned."

On the other hand the 2.2.2 documentation in the tarball says "doc/
IntroductionToRedisDataTypes.html".

"every time we add an element Redis performs an O(log(N)) operation,
that's good, but when we ask for sorted elements Redis does not have
to do any work at all, it's already all sorted:

$ ./redis-cli zrange hackers 0 -1
1. Alan Turing
2. Claude Shannon
3. Alan Kay
..."

Which is correct? In the former it seems that work is being done when
zrange is executed whereas in the latter the result is effectively
memoised.

Also, out of curiosity why are ZSets so called (why the Z)?

Thanks,

Frank Wilson

[Jeremy Zawodny]

I'll hazard an educated guess...

On Wed, Mar 9, 2011 at 7:15 AM, Frank Wilson <frank....@sidonis.com> wrote:

The ZRANGE command reference (http://redis.io/commands/zrange) states
that the command has

"O(log(N)+M) complexity with N being the number of elements in the
sorted set and M the number of elements returned."

Right.  Since a ZRANGE can ask for more than one element (M elements, in fact) there's a new factor.

 

On the other hand the 2.2.2 documentation in the tarball says "doc/
IntroductionToRedisDataTypes.html".

"every time we add an element Redis performs an O(log(N)) operation,
that's good, but when we ask for sorted elements Redis does not have
to do any work at all, it's already all sorted:

Because when adding a single element, M is always 1.

 

$ ./redis-cli zrange hackers 0 -1
1. Alan Turing
2. Claude Shannon
3. Alan Kay
..."

Which is correct? In the former it seems that work is being done when
zrange is executed whereas in the latter the result is effectively
memoised.

The result is not sorted when but there's still some work involved in fetching it.

Remember that big-O notation helps to understand the performance of an operation as sizes change.  But comparing the big-O for various ops may not be comparing apples-to-apples.

Jeremy 

[Salvatore Sanfilippo]

On Wed, Mar 9, 2011 at 4:15 PM, Frank Wilson <frank....@sidonis.com> wrote:
> The ZRANGE command reference (http://redis.io/commands/zrange) states
> that the command has
>
> "O(log(N)+M) complexity with N being the number of elements in the
> sorted set and M the number of elements returned."

This is exact as we need O(log(N)) to lookup the element, and O(M) to
walk all the elements to transfer.

> "every time we add an element Redis performs an O(log(N)) operation,
> that's good, but when we ask for sorted elements Redis does not have
> to do any work at all, it's already all sorted:

This is also exact :) What we mean more informally here is that since
the list is already ordered, there is no sort operation, so it's
lighting fast in the practice. An O(log(N)) lookup is really, really
cheap, even with a sorted set consisting of millions of keys.

> Also, out of curiosity why are ZSets so called (why the Z)?

I know it's a crazy mental association, but I called it this way
because of Z-Buffering:

http://en.wikipedia.org/wiki/Z-buffering

Cheers,
Salvatore

> Thanks,
>
> Frank Wilson
>
> --
> You received this message because you are subscribed to the Google Groups "Redis DB" group.
> To post to this group, send email to redi...@googlegroups.com.
> To unsubscribe from this group, send email to redis-db+u...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/redis-db?hl=en.
>
>

--
Salvatore 'antirez' Sanfilippo
open source developer - VMware

http://invece.org
"We are what we repeatedly do. Excellence, therefore, is not an act,
but a habit." -- Aristotele

[Salvatore Sanfilippo]

p.s. and for Z-order as well => http://en.wikipedia.org/wiki/Z-order
In general for all the computer graphics related things about
visualization of objects, starting with a "Z" :)