6

2 つのリストがあります。1 つは大規模 (数百万の要素) で、もう 1 つは数千です。私は次のことをしたい

bigArray=[0,1,0,2,3,2,,.....]

smallArray=[0,1,2,3,4]

for i in len(smallArray):
  pts=np.where(bigArray==smallArray[i])
  #Do stuff with pts...

上記は機能しますが、遅いです。Cで何かを書くことに頼らずに、これをより効率的に行う方法はありますか?

4

3 に答える 3

8

あなたの場合、大きな配列を事前にソートすることでメリットが得られる場合があります。これは、時間を〜45秒から2秒に短縮する方法を示す例です（私のラップトップで）（配列5e6と1e3の特定の長さのセットの場合）。明らかに、配列のサイズが無駄に異なる場合、ソリューションは最適ではありません。たとえば、デフォルトのソリューションでは複雑さは O(bigN*smallN) ですが、私が提案するソリューションでは O((bigN+smallN)*log(bigN)) です。

import numpy as np, numpy.random as nprand, time, bisect

bigN = 5e6
smallN = 1000
maxn = 1e7
nprand.seed(1)  
bigArr = nprand.randint(0, maxn, size=bigN)
smallArr = nprand.randint(0, maxn, size=smallN)

# brute force 
t1 = time.time()
for i in range(len(smallArr)):
    inds = np.where(bigArr == smallArr[i])[0]
t2 = time.time()
print "Brute", t2-t1

# not brute force (like nested loop with index scan)
t1 = time.time()
sortedind = np.argsort(bigArr)
sortedbigArr = bigArr[sortedind]
for i in range(len(smallArr)):
    i1 = bisect.bisect_left(sortedbigArr, smallArr[i])
    i2 = bisect.bisect_right(sortedbigArr, smallArr[i])
    inds = sortedind[i1:i2]
t2=time.time()
print "Non-brute", t2-t1

出力：

ブルート 42.5278530121

非ブルート 1.57193303108

于 2012-04-25T20:02:11.877 に答える
3

これまでのところ、numpy の必要はないと思います。defaultdictメモリが十分であれば、を利用できます。観測数が数百万にすぎない場合は、それを使用する必要があります。

big_list = [0,1,0,2,3,2,5,6,7,5,6,4,5,3,4,3,5,6,5]
small_list = [0,1,2,3,4]

from collections import defaultdict

dicto = defaultdict(list) #dictionary stores all the relevant coordinates
                          #so you don't have to search for them later

for ind, ele in enumerate(big_list):
    dicto[ele].append(ind)

結果：

>>> for ele in small_list:
...     print dicto[ele]
... 
[0, 2]
[1]
[3, 5]
[4, 13, 15]
[11, 14]

これにより、ある程度の速度が得られるはずです。

于 2012-04-26T01:06:15.817 に答える