玩蛇网提供最新Python编程技术信息以及Python资源下载!

求Python3.3比较距离完成对应点对匹配改进方法

def compare(d1, d2, ctj, ctk):

cor_ = []
for j_d in range(len(d1)):
    for k_d in range(len(d2)):
        compare_d = abs(d1[j_d] - d2[k_d])
        if compare_d <= CD:
            cor_.append([ctj[j_d], ctk[k_d]])
return cor_

这个函数中d1,d2,ctj,ctk皆为列表,每个列表中的元素有2000个左右,但是运行速度太慢了,达不到要求,(我觉得是复杂度太高了),有没有其他方法改进?

我猜你这儿有个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,并以lambda l: l[0]keysort新的d1与d2。然后再把compare改成这样:

def compare(d1, d2):
    cor_ = []
    for j_d in range(len(d1)):
        for k_d in range(len(d2)):
            compare_d = abs(d1[j_d][0] - d2[k_d][0])
            if compare_d <= CD:
                cor_.append([d1[j_d][1], d2[k_d][1]])
            else:
                break
    return cor_

这样连sortcompare大概就能做到1.4s。实际上对长度为2000的列表进行sort的时间可以忽略不计。
但本来我觉得因为如果给d2加个游标k_start像这样:

def compare(d1, d2):
    cor_ = []
    k_start = 0
    for j_d in range(len(d1)):
        while abs(d1[j_d][0] - d2[k_start][0]) > CD:
            k_start += 1
        for k_d in range(k_start, len(d2)):
            compare_d = abs(d1[j_d][0] - d2[k_d][0])
            if compare_d <= CD:
                cor_.append([d1[j_d][1], d2[k_d][1]])
            else:
                break
    return cor_

本来我觉得从代价的角度来考量这个更优一些,但不知为何后面这个反而要近3.0s才行。

我认为,这是你算法的问题
我试着描述一下你的意思:

给定 d1, d2 两个 list,每个元素对应数轴上一个点。
你要把所有距离小于 CD 的点找出来

你现在的算法是 O(mn) 的(别告诉我你不明白这一点)

如果这些点集中在一个很小的区间里,而且坐标都是整数的话,那么可以有很高效的算法。
我假定这些点无规律地分布在实轴上,那么,我能想到这样的算法(可能有更好的)

在最坏的情况下,我的算法也是 O(mn) 的(如果所有的点都符合要求),但一般情况下运行的能比你原先的代码快很多。

最后吐槽一下你的代码风格问题。@依云 说的没错

你的代码写得有浓厚的 “C” 风格(而这种风格在 C 语言里也是不推荐的)
我不知道你是在哪里看到的这段代码。我认为,任何一本负责的 python 教材,都会让你定义一个
class Point

玩蛇网文章,转载请注明出处和文章网址:https://www.iplaypy.com/wenda/wd19628.html

相关文章 Recommend

玩蛇网Python互助QQ群,欢迎加入-->: 106381465 玩蛇网Python新手群
修订日期:2017年05月22日 - 09时03分58秒 发布自玩蛇网

您现在的位置: 玩蛇网首页 > Python问题解答 > 正文内容
我要分享到:

必知PYTHON教程 Must Know PYTHON Tutorials

必知PYTHON模块 Must Know PYTHON Modules