One more my article was published in real hardcopy educational magazine in Russia. This time it’s about computer since in russian high school nowdays. The main goal of the publication is to provide brief overview of the themes need to be covered and cool tips to achive best results of the general IT tests. The article is written in russian. I think it would be pretty interesting to wide range of IT people around the world to compare the IT learning of russian high school to things children study in their countries.
Some time ago I designed very efficient pattern of top-n table implementation for social games. There are a lot of users (few millions). Our goal is quickly compose top-n table for any user. Generally, each user has its own top-n table, because the table contains information about the user either he’s in the top or not. Let’s assume users has the score and we build the top-n table by that score. So, most top user in the table (rank=1) has max. score.
As we have social game, so, it’s ok to have not exactly actual top-n table, but some version cached for an hour or 20 minutes. We will update the table in the cache every 20 minutes. The question is about how to represent information of the user (current one). His score is available, but his rank in the actual top-n table is not available if the user is not in the top. It should be calculated on fly. Keep in mind, that we don’t cache whole users table ordered by the score, but only n top records.
The idea is to avoid full table scan but and use linear interpolation to gues approximate rank for user out of top table.
If user has the same score as last user in the top then the rank is N+1.
In other case:
rank = -(UsersCount – N – 1)*(score – Max)/Max + N + 1,
UsersCount is total number of users,
N is the size of top table,
score is the score of the user,
Max is the score of last user in the top table.