10

好的，对不起，如果我的问题看起来有点粗糙。我会试着用形象的方式来解释它，我希望这是令人满意的。

10个孩子。
5盒。
每个孩子选择三个盒子。
每个盒子被打开：
- 如果它包含一些东西，所有选择这个盒子的孩子都得到 1 分
- 否则，没有人得到一分。

我的问题是关于我用粗体表示的内容。因为在我的代码中，有很多孩子和很多盒子。

目前，我进行如下操作：

children = {"child_1" : 0, ... , "child_10": 0}

gp1 = ["child_3", "child_7", "child_10"] #children who selected the box 1
...
gp5 = ["child_2", "child_5", "child_8", "child_10"]

boxes = [(0,gp1), (0,gp2), (1,gp3), (1,gp4), (0,gp5)]

for box in boxes:
    if box[0] == 1: #something inside
        for child in box[1]:
            children[child] += 1

我主要担心为每个孩子分配一个额外点的 for 循环。因为在我的最终代码中，我有很多很多孩子，我担心这样做也会减慢程序的速度。

有没有更有效的方法让同一组的所有孩子更快地获得他们的观点？

4

6 回答 6

5

  1. 将孩子表示为数组的索引，而不是字符串：

    childrenScores = [0] * 10
gp1 = [2,6,9] # children who selected box 1
...
gp5 = [1,4,7,9]

boxes = [(0,gp1), (0,gp2), (1,gp3), (1,gp4), (0,gp5)]

  2. 然后，您可以存储childrenScores为 NumPy 数组并使用高级索引：

    childrenScores = np.zeros(10, dtype=int)
...
for box in boxes:
    if box[0]:
        childrenScores[box[1]] += 1 # NumPy advanced indexing

    这仍然涉及某个地方的循环，但循环在 NumPy 的深处，它应该提供有意义的加速。

于 2013-09-01T18:42:08.167 回答
2

我能想到的唯一加速是使用 numpy 数组和流式求和操作。

children[child] += np.ones(len(children[child]))

您应该对操作进行基准测试，看看这对于您的业务案例是否太慢。

于 2013-09-01T18:16:39.103 回答
1

我会做什么

在gpX列表中不要保存“孩子的名字”（例如"child_10"），而是保存对孩子点数的引用。

怎么做

使用列表是 python 中的对象这一事实，您可以：

  1. 将孩子的字典更改为：children = {"child_0": [0], "child_1": [0], ...}等等。
  2. 当您分配给组时，不要分配键而是分配值（例如gp1.append(children["child_0"])）。
  3. 循环应如下所示：for child in box[1]: child[0]+=1. 这将更新children字典。

编辑：

为什么这样更快：因为您忽略了搜索的部分children[child]，这可能会很昂贵。

这种技术之所以有效，是因为通过将总数存储在一个可变类型中，并将这些值附加到组列表中，dict 值和每个框的列表值都将指向相同的列表条目，而改变一个将改变另一个。

于 2013-09-01T18:16:55.027 回答
1

一般两点：

(1) 根据您告诉我们的内容，没有理由将精力集中在较小的性能优化上。你最好把时间花在思考如何让你的数据结构不那么尴尬和更具交流性。一堆相互关联的字典、列表和元组很快变得难以维护。有关替代方法，请参见下面的示例。

(2) 作为游戏设计者，您了解事件遵循一定的顺序：首先孩子们选择他们的盒子，然后他们发现他们是否获得积分。但是您不必以这种方式实现它。孩子可以选择一个盒子并立即获得积分（或不积分）。如果需要保留孩子对此类结果的无知，则依赖于这种无知的算法部分可以根据需要强制执行保密面纱。结果：不需要一个盒子循环遍历它的孩子，给每个孩子奖励分数；相反，在选择盒子时立即将积分奖励给孩子。

import random

class Box(object):
    def __init__(self, name):
        self.name = name
        self.prize = random.randint(0,1)

class Child(object):
    def __init__(self, name):
        self.name = name
        self.boxes = []
        self.score = 0
        self._score = 0

    def choose(self, n, boxes):
        bs = random.sample(boxes, n)
        for b in bs:
            self.boxes.append(b)
            self._score += b.prize

    def reveal_score(self):
        self.score = self._score

boxes = [Box(i) for i in range(5)]
kids = [Child(i) for i in range(10)]

for k in kids:
    k.choose(3, boxes)

# Later in the game ...
for k in kids:
    k.reveal_score()
    print (k.name, k.score), '=>', [(b.name, b.prize) for b in k.boxes]
于 2013-09-01T19:11:50.287 回答
0

无论如何，您将循环遍历孩子，而您的答案似乎避免了遍历没有得到任何分数的孩子。

使用 filter 或 itertools.ifilter 来选择其中包含某些内容的框可能会稍微快一些：

import itertools

...

for box in itertools.ifilter(lambda x: x[0], boxes):
    for child in box[1]
        children[child] += 1
于 2013-09-01T18:16:03.937 回答
0

如果您不需要立即打印每个孩子的分数，您可以按需计算，从而节省时间。如果您只需要不时地查询一个孩子的分数，这可能会有所帮助。您可以在获得时缓存每个结果，这样您下次需要时就不会再次计算它。

首先，您需要知道孩子属于哪些群体。我们将此信息存储为我们将调用 childToGroupsMap 的映射，它将每个孩子映射到一个包含其所属框的数组，如下所示：

childToGroupsMap = {}
for child in children:
    childToGroupsMap[child[0]] = []
for box in boxes:
    for child in box[1]:
        if (box[1] not in childToGroupsMap[child]):
            childToGroupsMap[child].append(box[1])

这构建了从孩子到盒子的反向映射。

从每个盒子到一个表示它是否已打开的布尔值的映射也将有所帮助：

boxToOpenedMap = {}
for box in boxes:
    boxToOpenedMap[box[1]] = box[0]

现在，当有人查询一个孩子有多少点时，您可以遍历它所属的每个框（childToGroupsMap当然使用 ），并简单地计算这些框中有多少已映射到1map 中boxes：

def countBoxesForChild(child):
    points = 0
    for box in childToGroupsMap[child]
        if boxToOpenedMap[box] == 1:
            points += 1
    return points

为了使这一点更好，您可以缓存得到的点数。像这样制作地图：

childToPointsCalculated = {}
for child in children:
    childToPointsCalculated[child[0]] = -1

其中-1表示我们还不知道这个孩子有多少分。

最后，您可以修改您的countBoxesForChild函数以利用缓存：

def countBoxesForChild(child):
    if childToPointsCalculated[child] != -1
        return childToPointsCalculated[child]

    points = 0
    for box in childToGroupsMap[child]
        if boxToOpenedMap[box] == 1:
            points += 1
    childToPointsCalculated[child] = points
    return points
于 2013-09-01T18:24:23.250 回答