使用Python中的缓存加速求和

Question

在每次10000迭代中，我们选择总分最少的player来玩游戏，在那里他将获得一个随机的分数。

我认为每个迭代中最慢的部分似乎是所有玩家得分的总和。

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))

Answer 1

一个解决方案

一种方法是使用字典来记录总分：

players = {f"player{i}": [] for i in range(8)}
total_player_score = dict.fromkeys(players, 0)

for i in range(10000):
    player = min(total_player_score, key=total_player_score.get)
    game = Game(random.randint(0, 10))
    players[player].append(game)
    total_player_score[player] += game.score

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

输出(一次运行)

player0 : 6252
player1 : 6250
player2 : 6247
player3 : 6247
player4 : 6244
player5 : 6248
player6 : 6250
player7 : 6245

一个更快的解决方案(O(mlogn))

最重要的是，我建议您使用堆来跟踪最小值：

import heapq

players = {f"player{i}": [] for i in range(8)}
total_player_score = [(0, player) for player in players]
heapq.heapify(total_player_score)

for i in range(10000):
    score, player = heapq.heappop(total_player_score)
    game = Game(random.randint(0, 10))
    players[player].append(game)
    heapq.heappush(total_player_score, (score + game.score, player))

第二种方法将代码从O(m*n)转换为O(m*logn)，其中n是参与者的数量，m是迭代的次数(代码中的range(1000))。

Answer 2

如果您将数据和行为封装在一个Player类中，您可以让该类跟踪总计的文件记录，这样类的调用者就不需要知道它了。这使您可以使用易于准备和高效的代码，而代价是更长的代码：

import random

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

class Player:
    def __init__(self, name):
        self.name = name
        self.scores = []
        self.total = 0
        
    def add_game(self, game):
        self.scores.append(game)
        self.total += game.score


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


for i in range(10000):
    player = min(players, key=lambda player: player.total)
    player.add_game(Game(random.randint(0, 10)))

for player in players:
    print(player.name, ":", player.total)

此打印没有明显的延迟：

player0 : 6280
player1 : 6281
player2 : 6283
player3 : 6280
player4 : 6279
player5 : 6283
player6 : 6277
player7 : 6283