时间戳

首页 > 解决方案 > 降低python（2.7）算法的时间复杂度

python - 降低python（2.7）算法的时间复杂度

问题描述

我输入了一个列表，该列表由三个列表组成，每个列表分别代表 X、Y 和 Z 坐标。例如：

coords = [[2, 1, 5, 2, 8, 6, 8, 6, 1, 2, 3 , 4], [1, 3, 4, 1, 2, 2, 2, 4, 2, 3, 4, 5], [2, 4, 7, 2, 1, 2, 1, 4, 5, 6, 9, 8]]

其中坐标 X 的列表是：X = [2, 1, 5, 2, 8, 6, 8, 6, 1, 2, 3 , 4]

一个点将像这样形成：point = [2, 1, 2]。点 XYZ 表示立方体的一个顶点。（在我的程序中，我必须分析一组堆叠或并排的立方体）。

作为函数的输出，我想要一个与总点数一样大的 ID 列表（= 坐标列表之一的长度）。对于不同的点，ID 必须是唯一的，并且随着点列表的迭代而顺序递增。当一个点已经遇到时（例如，当一个立方体的顶点与另一个立方体的顶点重合时），在输出列表中，该点必须具有首先遇到相同点的 ID。

该示例的结果应该是outp = [1, 2, 3, 1, 5, 6, 5, 8, 9, 10, 11]

这是我编写的代码，它运行良好：

def AssignIDtoNode(coords):

    outp = []
    n_points = len(coords[0])
    points = []

    memo_set = set()
    memo_lst = ["" for x in xrange(0, n_points)]

    for i in range(n_points):

        point = "(X = " + str(coords[0][i]) + ", Y = " + str(coords[1][i]) + ", Z = " + str(coords[2][i]) + ")"
        if punto not in memo_set:
            outp.append(i+1)
            memo_set.add(point)
            memo_lst[i] = point
        else:
            ind = memo_lst.index(point)
            outp.append(ind+1)
                
    return outp

当函数的输入中有一个非常大的点列表（数百万个点）并且计算时间显着增加时，就会出现问题。我已将每个点转换为一个字符串以方便搜索，并尽可能使用一组来减少第一次搜索时间。在我看来，程序需要通过 .index() 函数搜索某个点的索引时会花费很长时间。

有没有办法进一步优化这个功能？

标签： pythonalgorithmoptimizationtime-complexityironpython

解决方案

使用 enumerate、zip 和字典来存储索引 -{(x,y,z):index,...}

def f(coords):

    d = {}
    outp = []
    for i,punto in enumerate(zip(*coords),1):
        d[punto] = d.get(punto,i)    # if it doesn't exist add it with the current index
        outp.append(d[punto])
                
    return outp

单次通过点，无类型转换，恒定时间查找。

>>> AssignIDtoNode(coords) == f(coords)
True

压缩和枚举文档

LBYL ...

def g(coords):
    outp = []
    d = {}
    for i,punto in enumerate(zip(*coords),1):
        if punto not in d:
            d[punto] = i
        outp.append(d[punto])        
    return outp

g比f100 万和 300 万 (x,y,z) 点快约 25%。

推荐阅读