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

by

1👍

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.

👤dani herrera

1👍

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.
👤xyres

Leave a comment