python 3.3中通过比较距离完成对应点对匹配

Question

defcompare(d1,d2,ctj,ctk):cor_=[]forj_dinrange(len(d1)):fork_dinrange(len(d2)):compare_d=abs(d1[j_d]-d2[k_d])ifcompare_d

Answer 1

我猜你这儿有个assert是d1和ctj长度相同，d2和ctk长度相同（实际上是：你在compare中只用到了ctj[:len(d1)]和ctk[:len(d2)]，所以我总可以认为这个assert成立）
如果说len(d1)=n，len(d2)=m的话，你原来的compare是O(mn)的，我测试了一下CD=100，d1、d2中均为[0,200]中的随机整数且m=n=2000的情况，大约要2.8s。
实际上可以让d1和ctj打包，d2和ctk打包，即用list(zip(d1,ctj))代替d1及ctj而用list(zip(d2,ctk))代替d2及ctj，并以lambdal:l[0]为key来sort新的d1与d2。然后再把compare改成这样：
defcompare(d1,d2):
cor_=[]
forj_dinrange(len(d1)):
fork_dinrange(len(d2)):
compare_d=abs(d1[j_d][0]-d2[k_d][0])
ifcompare_d<=CD:
cor_.append([d1[j_d][1],d2[k_d][1]])
else:
break
returncor_
这样连sort带compare大概就能做到1.4s。实际上对长度为2000的列表进行sort的时间可以忽略不计。
但本来我觉得因为如果给d2加个游标k_start像这样：
defcompare(d1,d2):
cor_=[]
k_start=0
forj_dinrange(len(d1)):
whileabs(d1[j_d][0]-d2[k_start][0])>CD:
k_start+=1
fork_dinrange(k_start,len(d2)):
compare_d=abs(d1[j_d][0]-d2[k_d][0])
ifcompare_d<=CD:
cor_.append([d1[j_d][1],d2[k_d][1]])
else:
break
returncor_
本来我觉得从代价的角度来考量这个更优一些，但不知为何后面这个反而要近3.0s才行。
                            

Answer 2

我认为，这是你算法的问题
我试着描述一下你的意思：
给定d1,d2两个list，每个元素对应数轴上一个点。
你要把所有距离小于CD的点找出来
你现在的算法是O(mn)的（别告诉我你不明白这一点）
如果这些点集中在一个很小的区间里，而且坐标都是整数的话，那么可以有很高效的算法。
我假定这些点无规律地分布在实轴上，那么，我能想到这样的算法（可能有更好的）
把d2排序
对于d1中的元素di,假定其坐标是xi，那么，在d2中二分查找所有[xi-CD,xi+CD]的元素
找到的元素都是符合要求的点
在最坏的情况下，我的算法也是O(mn)的（如果所有的点都符合要求），但一般情况下运行的能比你原先的代码快很多。
最后吐槽一下你的代码风格问题。@依云说的没错
代码也写得比较「ACM」
你的代码写得有浓厚的“C”风格（而这种风格在C语言里也是不推荐的）
我不知道你是在哪里看到的这段代码。我认为，任何一本负责的python教材，都会让你定义一个classPoint