CODEWITHSUNDEEP
pythonmysqldjangodatabasesorting
Saqib Ali
Saqib Ali

Reputation: 12585

How to efficiently store a ranked list of objects in Django?

I have a Django Model:

from django.db import models

class Player(models.Model):
    name = models.CharField(max_length=254, null=True, blank=True,)
    score = models.IntegerField()

A = Player.create(name="A", score=99)
B = Player.create(name="B", score=66)
C = Player.create(name="C", score=66)
D = Player.create(name="D", score=55)
E = Player.create(name="E", score=44)

I want to maintain a ranking of all my players by score. If players have the same score, they will have the same rank. So in this case, the ranking would look like this:

Name       Score     Rank
A          99        1
B          66        2
C          66        2
D          55        4
E          44        5

I want to store this ranking in the Database so that I don't constantly have to perform expensive sorting queries. I need to efficiently perform all the following operations:

  1. Given a player, lookup their rank
  2. Given a rank, find out which player(s) have that rank
  3. Given a player, insert them into this ranking
  4. Given a player, delete them from this ranking
  5. Given a player and a score, update their position in this ranking

I will need to insert and delete players from this list. Whenever I do #3, #4 or #5, I will need to update the ranks of other players accordingly to maintain the integrity of the ranking.

What is the most efficient way to do so in Django? How do I build my models so this will work efficiently and my database operations will be minimal? Please show me what any new models should look like.

Upvotes: 3

Views: 3207

Answers (2)

xyres
xyres

Reputation: 21779

Technically, every object in the queryset is a Python object. Which means you can assign attributes to them on-the-fly. In our case we will assign each player a rank attribute.

So I wrote a small algorithm to calculate ranks on-the-fly. This algorithm works on the assumption that the queryset is sorted in decreasing order.

players = Player.objects.order_by('-score')

current_rank = 1
counter = 0

for player in players:
    if counter < 1: # for first player
        player.rank = current_rank
    else: # for other players
        if player.score == players[counter - 1].score:
            # if player and previous player have same score,
            # give them the same rank
            player.rank = current_rank
        else:
            # first update the rank
            current_rank += 1
            # then assign new rank to player
            player.rank = current_rank
    counter += 1

Now in your templates, you can access the rank by using {{ player.rank }}.

Limitations:

  1. You can't lookup a player if a rank is given. Although you can still lookup, for example, top 10 players, etc.
  2. Calculating individual ranks can be slow. For example, to know the rank of the 1000th player, you'll need to know the ranks of previous 999 players.

Upvotes: 1

dani herrera
dani herrera

Reputation: 51675

You can materialize ranks and reorder on save Player, notice than not all times you need to resort ranks when a new score is saved:

The new model:

class ScoreRank(models.Model):
    score = models.IntegerField(primary_key=True)
    rank = models.IntegerField()
    player_count = models.IntegerField()

Keeping rank sorted:

from django.db.models.signals import pre_save
@receiver(pre_save, sender=Player)
def update_score_rank(sender, instance, **kwargs):
    #delete from previous rank
    if instance.pk:
       previous_score = ( Player.objects
                         .filter( id=instance.id )
                         .values_list( 'score', flat=True ).first() )
       sc = ScoreRank.objects.get( score = previous_score )
       if sc.player_count == 1:
           #new hole in ranks, add -1 to other ranks to remove it:
           _ = (ScoreRank.objects
               .filter( score__gt = previous_score )
               .update( rank=F('rank') - 1 ) )
       sc.delete()
    #insert in new rank
    sc, is_new = ( ScoreRank.objects
                  .get_or_create(score=instance.score,
                                 defaults={'rank': -1,'player_count': 1,}) )
    if not is_new:
        #this score is not new: add one to player_count
        _ = ( ScoreRank.objects
             .filter( score = instance.score )
             .update( rank=F('player_count') + 1 ) )
    else:
        #this score is not new: make hole for it
        rank = ( ScoreRank.objects
                .filter( score__gt = instance.score )
                .annotate( m=Min("score" ) ) )
        new_rank = rank["m"] if rank["m"] else 1
        _ = ( ScoreRank.objects
             .filter( score__lte = new_rank )
             .update( rank=F('rank') + 1 ) )
        _ = ( ScoreRank.objects
             .filter( sc = sc.score )
             .update( rank=new_rank ) )

Don't forget to enclose database operations in a single transaction ( a serializable transaction )

Disclainer: not tested.

Upvotes: 1

Related Questions