0

I have two large vectors (~133000 values) of different length. They are each sortet from small to large values. I want to find values that are similar within a given tolerance. This is my solution but it is very slow. Is there a way to speed this up?

import numpy as np

for lv in range(np.size(vector1)):
    for lv_2 in range(np.size(vector2)):
        if np.abs(vector1[lv_2]-vector2[lv])<.02: 
            print(vector1[lv_2],vector2[lv],lv,lv_2)
            break
4

3 回答 3

0

以下代码可以很好地提高性能，具体取决于数字的密集程度。使用一组 1000 个随机数，在 0 到 100 之间均匀采样，它的运行速度比您的实现快大约 30 倍。

pos_1_start = 0

for i in range(np.size(vector1)):
    for j in range(pos1_start, np.size(vector2)):
        if np.abs(vector1[i] - vector2[j]) < .02:
            results1 += [(vector1[i], vector2[j], i, j)]
        else:
            if vector2[j] < vector1[i]:
                pos1_start += 1
            else:
                break

时机：

time new method: 0.112464904785
time old method: 3.59720897675

由以下脚本生成：

import random
import numpy as np
import time

# initialize the vectors to be compared
vector1 = [random.uniform(0, 40) for i in range(1000)]
vector2 = [random.uniform(0, 40) for i in range(1000)]

vector1.sort()
vector2.sort()

# the arrays that will contain the results for the first method
results1 = []

# the arrays that will contain the results for the second method
results2 = []

pos1_start = 0

t_start = time.time()
for i in range(np.size(vector1)):
    for j in range(pos1_start, np.size(vector2)):
        if np.abs(vector1[i] - vector2[j]) < .02:
            results1 += [(vector1[i], vector2[j], i, j)]
        else:
            if vector2[j] < vector1[i]:
                pos1_start += 1
            else:
                break

t1 = time.time() - t_start
print "time new method:", t1

t = time.time()
for lv1 in range(np.size(vector1)):
    for lv2 in range(np.size(vector2)):
        if np.abs(vector1[lv1]-vector2[lv2])<.02: 
            results2 += [(vector1[lv1], vector2[lv2], lv1, lv2)]
t2 = time.time() - t_start

print "time old method:", t2
# sort the results

results1.sort()
results2.sort()

print np.allclose(results1, results2)
于 2012-10-10T11:47:37.703 回答
0

您的算法远非最佳。你比较了太多的价值观。假设您处于某个位置，vector1并且当前值 invector2已经0.02大得多了。你为什么要比较其余的vector2？

从类似的东西开始

pos1 = 0
pos2 = 0

现在比较向量中这些位置的值。如果差值太大，则移动较小的位置，重新检查。继续直到到达一个向量的末尾。

于 2012-10-10T08:58:57.200 回答
0

尚未对其进行测试，但以下应该可以工作。这个想法是利用向量被排序的事实

lv_1, lv_2 = 0,0
while lv_1 < len(vector1) and lv_2 < len(vector2):
  if np.abs(vector1[lv_2]-vector2[lv_1])<.02:
     print(vector1[lv_2],vector2[lv_1],lv_1,lv_2)
     lv_1 += 1
     lv_2 += 1
  elif vector1[lv_1] < vector2[lv_2]: lv_1 += 1
  else: lv_2 += 1
于 2012-10-10T09:00:16.190 回答