5

これをPythonで行う必要があります。与えられたリスト l があり、5000 を超える整数要素を含む場合があります。数の合計には制限があり、20000 またはそれ以上になる可能性があります。出力は、リストから選択された 2 つの数値のすべての可能な合計である必要があります。

l=[1,2,3,4,5,6,7,8,9]
output 
1+1,1+2,1+3,1+4,1+5,1+6...........
2+2,2+3,2+4.......
.........
.......

2,3,4,5,6... like that

私はこのコードを使っています.とりあえずこれをしています.しかし遅いです.

l=listgen()
p=[]
for i in range(0,len(l)):
    for j in range(i,len(l)):
        k=l[i]+l[j]
        if k not in p:
            p.append(k)
p.sort
print(p)

listgen()入力リストを生成する関数です。

4

6 に答える 6

10

いくつかの昔ながらの最適化により、複数の for ループを使用したリスト内包表記よりも理解しやすい高速なコードが得られる場合があります。

def sums(lst, limit):    # prevent global lookups by using a function
    res = set()          # set membership testing is much faster than lists
    res_add = res.add    # cache add method
    for i, first in enumerate(lst):   # get index and item at the same time
        for second in lst[i:]:        # one copy operation saves n index ops.
            res_add(first + second)   # prevent creation/lookup of extra local temporary
    return sorted([x for x in res if x < limit])

print sums(listgen(), 20000)

追加のボーナスとして、このバージョンは psyco、cython などで美しく最適化されます。

更新： これを他の提案と比較すると（listgenをrange（5000）に置き換えると、次のようになります：

mine:        1.30 secs
WolframH:    2.65 secs
lazyr:       1.54 secs (estimate based on OPs timings -- I don't have Python 2.7 handy)
于 2012-08-03T09:33:03.937 に答える
3

編集: Thebjorn は、彼が最も効率的な解決策を持っていると述べており、私自身のテストでも一致していますが、パフォーマンスは少し向上しました。彼のコードは、Python のバージョンへの依存度も低く、最適化に関して非常によく考えられ、説明されているようです。あなたは彼の答えを受け入れる必要があります（そして彼に賛成票を投じてください）。

itertools.combinations_with_replacement（python 2.7で追加）を使用してp、set.

def sums(lst, limit):
    from itertools import combinations_with_replacement
    p = set(x + y for x, y in combinations_with_replacement(listgen(), 2))
    return sorted([x for x in p if x < limit])

次の行が原因で、コードが遅くなります。

if k not in p: # O(N) lookup time in lists vs average case O(1) in sets

pコードにいくつかの小さな変更を加えるだけでset、大きな違いが生まれます。

L = listgen()
p = set()
for i in range(0, len(L)):
    for j in range(i, len(L)):
        p.add(L[i] + L[j])
print(sorted(p))

ところで、あなたの例のこの行

p.sort

効果はありません。実際に実行するには、次のようにメソッドを呼び出す必要があります。

p.sort()
于 2012-08-03T09:13:21.523 に答える
2

編集：制限を含めました（OPのコードにはありませんでした）。

a = set(x + y for x in l for y in l)
print(sorted(x for x in a if x < limit))

これにより、アルゴリズムの複雑さも軽減されます (リスト内のメンバーシップ テストのため、O(n^4) になる可能性があります)。

于 2012-08-03T09:15:27.190 に答える
1

これには「NumPy」を使用できます。これにより、必要なパフォーマンスが明確に得られます。

import numpy as np

data = np.arange(5000)
limit = 20000
result = np.zeros(0,dtype='i4')
for i in data:
    result = np.concatenate((result,data[i]+data[i:]))
    if len(result) >= limit: break
result = result[:limit]

編集: 制限は要素の数ではなく合計にあることに気付きました。次に、コードは次のようになります。

EDIT2: さらに論理エラーが見つかりました。私の修正された提案は次のとおりです。

for idx, x in np.ndenumerate(data):
    result = np.concatenate((result,x+data[idx[0]:]))
    if x + data[-1] >= limit: break
result = result[result <= limit]
于 2012-08-03T09:40:27.583 に答える
1

入力リストがソートされている場合、制限に達したときに内側のループから抜け出すことができます。また、pセットにしてください。

lst=listgen()
lst.sort()
p=set()
for i in range(0,len(lst)):
    for j in range(i,len(lst)):
        k=lst[i]+lst[j]
        if k > limit:
            break
        p.add(k)
p = sorted(p)
print(p)
于 2012-08-03T09:29:53.663 に答える
0

リストに要素の繰り返しが含まれる可能性がある場合は、リストをセットに変換するなどして、最初にそれらを取り除くのが賢明かもしれません。

于 2012-08-03T09:17:41.347 に答える