[erlang-questions] How would you do it?

[Francesco Mazzoli]

At Mon, 2 Jul 2012 14:29:32 +0400,
Max Bourinov wrote:
>  1. I have to rank about 50 000 - 100 000 different players.
>  2. On each score message I have to re-sort whole ranking table.
>  3. It must be very cheap to get:
>      1. top 100 players
>      2. player's rating +/- 10 players about current player
>  4. I expect about 20-50 score messages per seconds
>  5. Size of score message is about 4KB (profile takes most of the space).
> 
> Any ideas or suggestions are welcome!

A priority search queue will fit your bill. You can to 2 in and 3.1 in
logarithmic time, and 3.1 in constant time.

I'm not aware of an Erlang implementation, here is an Haskell module
with link to a paper with implementation details:
http://hackage.haskell.org/packages/archive/PSQueue/1.1/doc/html/Data-PSQueue.html .

If you know some Haskell, this is an - untested - stub that will do
what you want:

-------------8<-----------------------------------

import Data.PSQueue as PSQ

type Ranking = PSQ Player Score 

newRanking :: Ranking
newRanking = PSQ.empty

updateScore :: Player -> Score -> Ranking -> Ranking
updateScore player score rank =
    case PSQ.lookup player rank of
        Nothing     -> PSQ.insert player score rank
        Just score' -> let score'' = magic to get new score
                       in  PSQ.insert player score'' rank

topNPlayers :: Int -> Ranking -> [Player]
topNPlayers n = take n . PSQ.toDescList

worsePlayers :: Player -> Int -> Ranking
             -> Maybe [Binding Player Score]
worsePlayers player n rank =
    case PSQ.lookup player rank of
        Nothing    -> Nothing
        Just score -> Just (take n (PSQ.atMost score rank))

------------->8-----------------------------------

For some reason you don't have the dual of `atMost' which returns the
items with a priority *greater* then the one given. I'd be surprised
if you can't implement that.

--
Francesco * Often in error, never in doubt