如何在Python中利用缓存加速玩家分数求和，将O(N)优化为O(1)？

在10000次迭代中，我们每次选择总分最低的玩家参与游戏，该玩家会获得随机分数。当前代码中每次迭代最耗时的部分为计算玩家总分：sum(g.score for g in players[x])。由于每次迭代仅更新一名玩家的分数，可通过缓存将当前O(N)的实现优化为O(1)，请问有什么合适的缓存使用方法？

原代码 #

import random

class Game:
    def __init__(self, score):
        self.score = score

players = {f"player{i}": [] for i in range(8)}

for i in range(10000):
    player = min(players, key=lambda x: sum(g.score for g in players[x]))
    players[player].append(Game(random.randint(0, 10)))

for player, games in players.items():
    print(player, ":", sum(g.score for g in games))

解决方案 #

方案1：独立字典缓存总分 #

维护一个单独的字典存储每个玩家的实时总分，每次给玩家添加新分数时同步更新缓存，获取总分直接从字典读取，时间复杂度为O(1)。

修改后的代码：

import random

class Game:
    def __init__(self, score):
        self.score = score

# 初始化玩家游戏列表与总分缓存
players = {f"player{i}": [] for i in range(8)}
player_totals = {player: 0 for player in players}

for i in range(10000):
    # 直接用缓存总分找最低分玩家
    player = min(players, key=lambda x: player_totals[x])
    new_score = random.randint(0, 10)
    players[player].append(Game(new_score))
    # 同步更新缓存
    player_totals[player] += new_score

# 打印时直接使用缓存的总分
for player, total in player_totals.items():
    print(player, ":", total)

方案2：面向对象封装缓存逻辑 #

将玩家的游戏记录和总分封装到Player类中，让对象自身维护总分状态，代码结构更清晰，缓存逻辑内聚。

修改后的代码：

import random

class Game:
    def __init__(self, score):
        self.score = score

class Player:
    def __init__(self):
        self.games = []
        self.total_score = 0
    
    def add_game(self, game):
        self.games.append(game)
        self.total_score += game.score

# 初始化玩家字典
players = {f"player{i}": Player() for i in range(8)}

for i in range(10000):
    # 直接访问玩家的total_score属性获取总分
    player = min(players, key=lambda x: players[x].total_score)
    new_score = random.randint(0, 10)
    players[player].add_game(Game(new_score))

# 打印玩家总分
for player_name, player in players.items():
    print(player_name, ":", player.total_score)

优化说明 #

原代码每次执行min操作时，都要遍历玩家的所有Game对象求和，时间复杂度为O(M)（M为该玩家的游戏次数）。10000次迭代下来，总时间复杂度为O(10000NM)（N为玩家数量）。

使用缓存后，获取总分只需直接读取缓存值（O(1)），更新总分仅需一次加法操作（O(1)），单次迭代的时间复杂度降至O(N)（因玩家数量固定为8，实际可视为O(1)），整体运行效率会大幅提升。

内容的提问来源于stack exchange，提问作者gameveloster