I am writing an application using redis where I need a sort of priority queue- items are assigned a priority between 1 and 10 and then one of the highest priority items is popped (order does not matter). From my understanding, the priority set's ZADD and BZPOPMAX seem perfect for this use case.
However, I noticed in the Redis docs that both operations have an O(LOG(N)) whereas equivalent operations for lists and sets are O(1).
This leads me to a couple performance-related questions:
Even though I know my queue will have a very small range of priorities (1-10), will the practical big O of the redis priority set implementations still be O(LOG(N))?
The time complexity of Redis sorted set has nothing to do with the range of scores (in your case, the priorities). Instead, it's related to the number of items in the sorted set. So the practical big O is still O(LOG(N)).
Is it likely to be worth pursuing an alternative implementation (perhaps one that uses a couple calls to lists and sets instead)?
You cannot achieve the goal with Redis List and Redis Set. Because Redis set is unordered, and searching list and accessing items in list (except the head and tail of the list) are O(N).
O(LOG(N)) is not slow. Even if you have 1 million items, a call to ZPOPMAX only needs about 20 comparisons to get the result, which is quite fast.
Try the simple solution and do a benchmark before choosing a more complex algorithm.