10

わかりました、私の問題が少し荒いようでしたら申し訳ありません。比喩的な方法で説明しようと思いますが、これで満足できることを願っています。

10人の子供。
5箱。
各子供は 3 つの箱を選びます。
各ボックスが開かれます:
- 何かが入っている場合、このボックスを選択したすべての子供が 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

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 に答える
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]

これで、誰かが子が持っているポイントの数を照会した場合、子が属する各ボックスを (もちろん を使用して) 調べて、それらのボックスのいくつがmap にchildToGroupsMapマッピングされているかを単純に数えることができます。1boxes

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 に答える