A + B = C + Dを満たす値のインデックスを見つける

Question

Python 2.7を使用して、以下の問題に取り組んでいます。私のコードを投稿し、それをより速く動かすためのさらにスマートなアイデアがあるのだろうか？最初にリストをソートし、ソートの振る舞いを利用するアイディアがあるかもしれないと思っていましたが、これまでのところ分かりません。私のコードはO(n^2)時間の複雑さです。

通報、整数のアレイAを考える

は、A、B、C & Dは、アレイ内の整数値であり、A + B = C + Dを満たす値のインデックスを見つけます。 quadruplesのすべての組み合わせを見つける。

コード、合計値、および合計が、そのような値をもたらす可能性インデックスである

from collections import defaultdict 

sumIndex = defaultdict(list) 

def buildIndex(numbers): 
    for i in range(len(numbers)): 
     for j in range(i+1,len(numbers)): 
      sumIndex[numbers[i]+numbers[j]].append((i,j)) 

def checkResult(): 
    for k,v in sumIndex.items(): 
     if len(v) > 1: 
      for i in v: 
       print k, i 

if __name__ == "__main__": 
    buildIndex([1,2,3,4]) 
    checkResult() 

出力、

5 (0,3) 
5 (1,2) 

Answer 1

場合を考えるのすべての要素配列は等しい。それでは、あらかじめ答えを知っていますが、単に結果を印刷するには、n*(n-1)/2という数のペアがあるので、時間はO(n^2)になります。だから私はこの問題のためにO(n^2)よりも複雑なアプローチがないと言うのは安全だと思います。

Answer 2

はい、O（n^2）よりも複雑な方法で行うことができます。アルゴは：

1. 複製配列を作成すると、元の配列の要素のインデックスorigArr []を格納しているindexArr []と仮定します。
2. origArr []を、複雑さO（nLogn）を持ついくつかのアルゴを使用して昇順にソートします。同様に、origArr []をソートしながらindexArr []をシャッフルします。
3. ソートされた配列でペアを見つける必要があります。可能な組み合わせをすべて見つけるために2つのループを実行します。 origArr[i] + origArr[i + 1] = sum.
4. sum <= origArr[n]ここで、nは最大要素である配列の最後の要素であるかどうかを検索します。またsum > origArr[n]の場合、他の組み合わせは使用できないため、内側のループと外側のループが解除されます。
5. また、sum > origArr[j]の場合は、内側ループを破ることになります。その合計のために他の組み合わせはできません。

PS - 最悪のシナリオはO（n^2）です。

Answer 3

より速く、よりPython的アプローチ用いitertools.combinations:

from collections import defaultdict 
from itertools import combinations 

def get_combos(l): 
    d = defaultdict(list) 
    for indices in combinations(range(len(l)),2): 
     d[(l[indices[0]] + l[indices[1]])].append(indices) 
    return {k:v for k,v in d.items() if len(v) > 1} 

---

タイミング

           OP  this 
len(l)=4, min(repeat=100, number=10000) | 0.09334 | 0.08050 
len(l)=50, min(repeat=10, number=100) | 0.08689 | 0.08996 
len(l)=500, min(repeat=10, number=10) | 0.64974 | 0.59553 
len(l)=1000, min(repeat=3, number=3) | 1.01559 | 0.83494 
len(l)=5000, min(repeat=3, number=1) | 10.26168 | 8.92959 

---

タイミングコード

結果

from collections import defaultdict 
from itertools import combinations 
from random import randint 
from timeit import repeat 


def lin_get_combos(l): 
    sumIndex = defaultdict(list) 
    for i in range(len(l)): 
     for j in range(i+1,len(l)): 
      sumIndex[l[i]+l[j]].append((i,j)) 
    return {k:v for k,v in sumIndex.items() if len(v) > 1} 

def craig_get_combos(l): 
    d = defaultdict(list) 
    for indices in combinations(range(len(l)),2): 
     d[(l[indices[0]] + l[indices[1]])].append(indices) 
    return {k:v for k,v in d.items() if len(v) > 1} 

l = [] 
for _ in range(4): 
    l.append(randint(0,1000)) 
t1 = min(repeat(stmt='lin_get_combos(l)', setup='from __main__ import lin_get_combos, l', repeat=100, number=10000)) 
t2 = min(repeat(stmt='craig_get_combos(l)', setup='from __main__ import craig_get_combos, l', repeat= 100, number=10000)) 
print '%0.5f, %0.5f' % (t1, t2) 

l = [] 
for _ in range(50): 
    l.append(randint(0,1000)) 
t1 = min(repeat(stmt='lin_get_combos(l)', setup='from __main__ import lin_get_combos, l', repeat=10, number=100)) 
t2 = min(repeat(stmt='craig_get_combos(l)', setup='from __main__ import craig_get_combos, l', repeat= 10, number=100)) 
print '%0.5f, %0.5f' % (t1, t2) 

l = [] 
for _ in range(500): 
    l.append(randint(0,1000)) 
t1 = min(repeat(stmt='lin_get_combos(l)', setup='from __main__ import lin_get_combos, l', repeat=10, number=10)) 
t2 = min(repeat(stmt='craig_get_combos(l)', setup='from __main__ import craig_get_combos, l', repeat= 10, number=10)) 
print '%0.5f, %0.5f' % (t1, t2) 

l = [] 
for _ in range(1000): 
    l.append(randint(0,1000)) 
t1 = min(repeat(stmt='lin_get_combos(l)', setup='from __main__ import lin_get_combos, l', repeat=3, number=3)) 
t2 = min(repeat(stmt='craig_get_combos(l)', setup='from __main__ import craig_get_combos, l', repeat= 3, number=3)) 
print '%0.5f, %0.5f' % (t1, t2) 

l = [] 
for _ in range(5000): 
    l.append(randint(0,1000)) 
t1 = min(repeat(stmt='lin_get_combos(l)', setup='from __main__ import lin_get_combos, l', repeat=3, number=1)) 
t2 = min(repeat(stmt='craig_get_combos(l)', setup='from __main__ import craig_get_combos, l', repeat= 3, number=1)) 
print '%0.5f, %0.5f' % (t1, t2)