1 
import random

a = [int(1000*random.random()) for i in xrange(10)]
b = [int(1000*random.random()) for i in xrange(10)]
c = [int(1000*random.random()) for i in xrange(10)]
d = dict()
for i in xrange(len(a)):
    for j in xrange(len(b)):
        for k in xrange(len(c)):
            if (i+j+k == 10):
                d[(i,j,k)] = a[i]+b[j]+c[k]

print max(d.values())

a,b,cそのコードは、最大化して保持するようなa[i]+b[j]+b[k]要素i+j+k=10の最良のトリプルを見つけます

4

4 に答える 4

4

まず、ループの境界を変更して、最も内側のループを取り除くことができます。

import random
a = [int(1000*random.random()) for i in xrange(10)]
b = [int(1000*random.random()) for i in xrange(10)]
c = [int(1000*random.random()) for i in xrange(10)]
d = dict()
for i in xrange(10):
    for j in xrange(10 - i):
        k = 10 - i - j
        if k < len(c):
            d[(i,j,k)] = a[i]+b[j]+c[k]

print max(d.values())

これにより、ランタイムが最大 4.5 倍改善されます。

In [2]: %timeit original()
10000 loops, best of 3: 166 us per loop

In [3]: %timeit new()
10000 loops, best of 3: 36.1 us per loop
于 2013-03-16T08:54:28.750 に答える
3

実際には のキーを使用していないため、より迅速にdictを構築して反復することができます。listしかし、 call を除いて、実際には値を使って何もしていないので、max進むにつれて最大値を追跡することができ、何かを構築して反復する必要はありません。

NPE のソリューションの変更:

import random
a = [int(1000*random.random()) for i in xrange(10)]
b = [int(1000*random.random()) for i in xrange(10)]
c = [int(1000*random.random()) for i in xrange(10)]
maxval = 0
for i in xrange(10):
    for j in xrange(10 - i):
        k = 10 - i - j
        if k < len(c):
            val = a[i]+b[j]+c[k]
            if val > maxval:
                maxval = val
print maxval

これにより、CPython での彼のバージョンよりも大幅に高速になりますが、PyPyでは大きな違いが生じます。

                 OP    HYRY   NPE    AB
CPython 2.7.2    161.  98.8   46.9   38.0
PyPy 1.9.0       11.8  7.28   7.39   2.46

言うまでもなく、そもそも CPython の代わりに PyPy を使用することは、誰かが提案したマイクロ最適化よりもはるかに大きなメリットです。

10 ではなく 1000000 の値がある実際の問題の場合、これは解決するのにひどい方法です。

int321 つには、値を Python の代わりに値の配列として保存するだけで、メモリ使用量 (したがって、ページング時間、キャッシュ ヒットなど) を大幅に削減できますlist。そして、それを行ったら、それを 1000000x3 に入れることもできますnumpy.array。次に、i+j+k==1000000 のマスク配列を作成し、マスクを適用して、その中の最大値を見つけるだけです。これにより、すべてのループが C に移行され、10 ～ 30 倍高速になると思います。Python を使用したマイクロ最適化から得られるものは、はるかに多くあります。

しかし、別の方向に進みたいと思うかもしれません。リストが存在する必要がありますか？一連のデータが生成/読み取り/遅延されている場合、すべてをメモリに読み取らずにこれを行う方法はありますか? 完全なリストは 2 つだけ必要なようです。3 番目のリストが到着する順序を制御できる場合は 1 つだけです。実際、3 番目の順序を制御できる場合は、最初の 10% を生成/読み取るだけで済みます。

于 2013-03-16T09:22:10.947 に答える
1

コードを関数でラップすると、変数の検索速度が向上します。3 番目のループは必要ありません。

import random
def f(random=random.random):
    a = [int(1000*random()) for i in xrange(10)]
    b = [int(1000*random()) for i in xrange(10)]
    c = [int(1000*random()) for i in xrange(10)]
    d = {}
    for i in xrange(len(a)):
        for j in xrange(len(b)-i):
            k = 10 - i - j
            if 0 <= k < 10:
                d[i,j,k] = a[i]+b[j]+c[k]
    return max(d.values())
f()

最大値のみが必要な場合は、辞書は必要ありません。

于 2013-03-16T08:56:15.083 に答える
0

random.randomルックアップをキャッシュすると、パフォーマンスが劇的に向上すると思います。

import random

def f():
    rand = random.random
    a = [int(1000*rand()) for _ in xrange(10)]
    b = [int(1000*rand()) for _ in xrange(10)]
    c = [int(1000*rand()) for _ in xrange(10)]
    d = dict()
    for i in xrange(10):
        for j in xrange(10 - i):
            k = 10 - i - j
            if 0 <= k < 10:
                d[(i,j,k)] = a[i]+b[j]+c[k]

    print max(d.values())

f()
于 2013-03-16T09:14:09.477 に答える