同点を考慮した順位表を出す処理を考える

今回はちょっと息抜き?に、数理パズルっぽい問題について考えてみます。

導入

「あるゲームの得点を入力として与えます。これを得点が高い順に、順位とともに出力してください。
ただし、同じ得点は同じ順位とし、そのように重複した数だけ次の順位を低くする。」
まどろこしい言い方になっていますが、要はよく見る感じのランキングを正確に出してください、ということです。
つまり、(98, 95, 94, 94, 91) という並びであれば、

1位: 98
2位: 95
3位: 94
3位: 94 (同率)
5位: 91

となるようにしろ、ということです。
対戦ゲームでも当たり前のように見かけるものではありますが、いざ自分で実装するとなるとどう考えて行けば良いか？というのを辿ってみることにします。

設定

今回はPythonでゲームのスコアランキングを管理するというテーマで考えてみます。
スコアランキングには順位、プレイヤー名、得点が表示されているものとします。
これらのデータを辞書型で管理するとしましょう。

データのイメージはこんな感じ。
ここではALICEとDAVIDの得点を同じとします。つまり2位が二人となるようにするのがゴールです。

records = [{'name': 'ALICE', 'score': 250}, {'name': 'BOB', 'score': 180}, {'name': 'CHAMP', 'score': 400}, {'name': 'DAVID', 'score': 250}]

解いてみる

名前と得点が与えられた状態で、これに順位を加えに行きます。
まずはscoreの降順に並べてみます。

>>> sorted(records, key=lambda e:e['score'], reverse=True)
[{'name': 'CHAMP', 'score': 400}, {'name': 'ALICE', 'score': 250}, {'name': 'DAVID', 'score': 250}, {'name': 'BOB', 'score': 180}]

ここにリストの添字を足してみると、順位っぽいものになりますが…もちろんALICEとDAVIDの添字が同じになることはありません。順位はこちらでうまく生成してやる必要があります。
得点順に並べることはできるので、それを軸に試してみます。

素直に頭から順に見てカウントする方法だと…

def ranking1(records):
    rec_sort = list(sorted(records, key=lambda r:r['score'], reverse=True))
    rank = 1
    count = 0
    last_score = None
    for r in rec_sort:
        if last_score != r['score']:
            rank += count
            count = 0
            last_score = r['score']
        r['rank'] = rank
        count += 1
    return rec_sort

処理は以下の通り。

• 最後に見た得点を比較する
• 一致してなければ、重複した数だけ順位を下げる
• 最後に見た得点を更新する
• 計算した順位を記憶する

実行例

>>> ranking1(records)
[{'name': 'CHAMP', 'score': 400, 'rank': 1}, {'name': 'ALICE', 'score': 250, 'rank': 2}, {'name': 'DAVID', 'score': 250, 
'rank': 2}, {'name': 'BOB', 'score': 180, 'rank': 4}]

問題に対し忠実に実装できています。

ちょっと改良

ただちょっと気になるのは、地味に長いこと。長くても動けばよかろうはそうなんですが、なんかもうちょっとスマートに書きたい気持ちに駆られます。
ここで閃きます。リストに対する要素の検索って、一番最初の要素を取ってこなかったかしらと。得点のリストに対して得点の検索をかければ、同じことができるんじゃないかしらと。

>>> [100, 80, 80, 60].index(100)
0
>>> [100, 80, 80, 60].index(80)
1
>>> [100, 80, 80, 60].index(60)
3

やっぱり。これに1を加えれば順位になりますね。

def ranking2(records):
    scores = sorted(list(map(lambda r:r['score'], records)), reverse=True)
    for r in records:
        r['rank'] = scores.index(r['score']) + 1
    return records

• 得点リストを作成
• 順位 = 得点リストを検索して見つかった添字 + 1

得点リストから生成するようにしました。さっきと比べてかなり減量できています。

ランダムデータでテスト

折角なので、ちゃんと動くかどうかをランダム生成のデータでもテストしてみます。
Pythonだとrandomモジュールを使えば良さそうです。

from random import randrange
# 得点が0以上10000未満の整数となるデータを10000件生成
records = [ { 'id': i, 'score': randrange(10000) } for i in range(10000) ]

このデータを同様に順位づけしていきますが、流石に10000件全て見るわけには行かないので、上位20件だけ確認してみます。

>>> result1=ranking1(records)
>>> for x in result1[:20]: print(x['rank'], x['id'], x['score'])  
... 
1 7443 9999
2 5252 9998
2 9421 9998
4 9149 9997
4 9876 9997
6 5675 9996
7 1694 9995
8 7628 9993
9 9494 9992
10 1375 9991
10 8786 9991
12 85 9990
12 4577 9990
14 6393 9989
14 7393 9989
16 7254 9988
16 9848 9988
18 838 9986
18 9046 9986
20 358 9985

>>> result2=ranking2(records)
>>> result2.sort(key=lambda x: x['rank'])
>>> result1 == result2
True

//2023-09-28 余分なスライス指定を削除

正しく出ましたが、ranking2の方は僅かに出力が遅く見えました。
実行速度に影響が出ているのでしょうか？

実行時間

少量のコード片の実行時間を計測するにはtimeitモジュールが使えます。1000回実行に要する時間を計測します。

>>> import timeit
>>> timeit.timeit(lambda: ranking1(records), number=1000)
1.233031599998867
>>> timeit.timeit(lambda: ranking2(records), number=1000) 
560.4779846000001

ranking1は1.2秒ほどなのに対し、ranking2は560秒、9分オーバーと大変長くなっています。
一体どうなっているのでしょう？ranking2のコードを眺めてみます。
得点のリストを生成する処理が遅いのでしょうか?

>>> timeit.timeit(lambda: sorted(list(map(lambda r:r['score'], records)), reverse=True), number=1000)
1.2820350000001781

ここは1秒もかかっていません。つまりこの後ろのindex()関数の繰り返し呼び出しが重いということになります。
リストのindex()関数ですが、リスト先頭から順に1件ずつ引数の値と比較して、最初に一致した要素の添字を返します。
したがって、検索対象がリスト後方にある場合は見つけるのに時間がかかることになります。
これはごく簡単なリストを使って実験することができます。

a10k = ['a'] * 10000 # 'a'を10000個持つ配列
a10k[-1] = 'z' # 末尾に別の値を設定
timeit.timeit(lambda: a10k.index('a')) # 'a' の検索を100万回実行 (リスト先頭がヒット)
timeit.timeit(lambda: a10k.index('z')) # 'z' の検索を100万回実行 (リスト末尾がヒット)

ご覧の通り、実行時間に100倍もの差が生じます。
今回扱っている得点リストは得点がほぼ一様に分布しており、ranking2ではリスト後方の要素の検索が多数発生するために、ボトルネックが顕在化したと考えられます。
他方、ranking1はリストに対して各要素1回の参照しか行わないようになっているため、処理時間が短いです。
見た目は綺麗になっても、実行効率は悪化するという残念な結果になっていました。

実行時間を考慮する意義

システムとしての応答時間が重要になる場面、それこそオンラインゲームなどでは重要になると思います。
得点が変化する度に順位も変動する可能性があり、再計算が必要になります。とりわけ多数のユーザが関与するような状況では、秒間何百回、何千回と処理する状況になることも考えられるでしょう。

感想

課題を一旦解いてみて、そこから色々試してみて、綺麗なコードが必ずしも上手くいくとは限らないという非情な現実を知ることができました。
コンソールでコード実行できる言語はこういう実験が気軽にできて良いですね。