代码之家 › 专栏 › 技术社区 › MarkS

精简嵌套元组列表

tuples python-3.x

MarkS · 技术社区 · 5 年前

我有一个使用defaultdict(list)成功解决的任务。

简而言之,取两对点(Ax,Ay)和(Bx,By)并计算斜率。

然后将具有相同坡度的所有点组合在一起。

使用defaultdict(list)我做到了:

dic = defaultdict(list)
for elem in result:
    x1 = elem[0][0]
    y1 = elem[0][1]
    x2 = elem[1][0]
    y2 = elem[1][1]
    si = slope_intercept(x1, y1, x2, y2)
    temp = defaultdict(list)
    temp[si].append(elem)
    FullMergeDict(dic, temp)
    temp.clear()

工作非常完美。(是的,整个程序还有很多内容没有显示。)

然而,我被告知要放弃defaultdict(list),并且必须使用嵌套的基于元组的结构。

我有一个元组列表,其中的结构看起来像:(((1,2),3),(2,5)

(1, 2) is the first coordinate point
3 is the computed slope
(2, 5) is the second coordinate point

注:这些只是用来说明结构的虚构值。这些观点几乎肯定不会生成所示的斜率。

如果我从这个开始:

start = [(((1, 2), 3), (2, 5)), (((4, 5), 2), (3, 7)), (((2, 4), 1), (8, 9)), (((1, 2), 3), (4, 8))]

我最终需要这样做:

end = [((1, 2), (2, 5), (1, 2), (4, 8)), ((4, 5), (3, 7)), ((2, 4), (8, 9))]

对于每个唯一的斜率,我需要共享相同斜率的所有坐标的元组。在上面的例子中,第一个和最后一个元组共享相同的斜率3,因此所有的坐标对具有斜率3的元组被组合成一个元组。是的,我意识到(1,2)在我的例子中被表示了两次。如果有另一组斜率为3的坐标,那么第一个元组将包含那些额外的坐标,包括重复坐标。请注意,从“起点”开始的嵌入坡度将被丢弃。

defaultdict(list)使这一点变得非常简单。我将关键点设置为坡度,然后合并值(坐标)。

我似乎无法理解如何使用这个必需的结构将“开始”转换为“结束”。

0 回复 | 直到 5 年前

pho 5 年前

我不知道你说的“我必须使用上面详述的结构”是什么意思。你有 start ,你想要 end ,所以在某个时刻,结构发生了变化。你的意思是说你根本不允许使用字典或列表吗?你的教练希望你从哪里开始 开始 到 终止 不使用其他任何东西?这里有一种方法,它只使用元组(和 开始 和 终止 列表)。

终止 将是元组的列表。我们将在单独的列表中跟踪坡度。预料 终止 和 lookup 看起来是这样的:

lookup = [   slope_1,                       , slope_2,                   ...]
end =    [((p1_x, p1_y), (p2_x, p2_y), ...), ((p10_x, p10_y), (p11_x, p11_y)), ...]

start = [(((1, 2), 3), (2, 5)), (((4, 5), 2), (3, 7)), (((2, 4), 1), (8, 9)), (((1, 2), 3), (4, 8))]
end = []
lookup = []

def find_tuple_index_with_slope(needle_slope):
    for index, item in enumerate(lookup):
        if item == needle_slope:
            return index
    return None

for item in start:
    p1 = item[0][0]
    slope = item[0][1]
    p2 = item[1]

    # Check if end already contains this slope
    slope_index = find_tuple_index_with_slope(slope)
    if slope_index is None:
        # If it doesn't exist, add an item to end
        end.append(p1, p2))
        # And add the slope to lookup
        lookup.append(slope)

    else:
        # If it exists, append the new points to the existing value and
        # reassign it to the correct index of end
        end[slope_index] = (*end[slope_index], p1, p2)

现在,我们有 终止 看起来是这样的:

[((1, 2), (2, 5), (1, 2), (4, 8)), ((4, 5), (3, 7)), ((2, 4), (8, 9))]

这种方法不太好的原因是功能 find_tuple_index_with_slope() 需要迭代中的所有元素 终止 查找要附加到的正确值。这增加了代码的时间复杂性,当你可以使用字典进行查找时,速度会快得多,尤其是如果你有很多点和很多不同的斜率值。

一个更好的方法是:用一个新的字典替换查找函数,其中键是斜率的值,值是中的索引 终止 其中存储对应的元组。

lookup = dict()
end = []
for item in start:
    p1 = item[0][0]
    slope = item[0][1]
    p2 = item[1]
    
    # Find the index of the tuple for `slope` using the lookup
    slope_index = lookup.get(slope, None)
    if slope_index is None:
        # If it doesn't exist, add an item to end 
        end.append((p1, p2))
        # And add that index to lookup
        lookup[slope] = len(end) - 1
    else:
        end[slope_index] = (*end[slope_index], p1, p2)

代码看起来几乎和以前一样,但使用字典而不是列表查找可以节省时间。