嵌套元组的压缩列表

Question

我有一个作业已使用 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 的坐标，则第一个元组将包含那些额外的坐标，包括重复的。请注意，'start' 中的嵌入斜率被丢弃。

defaultdict(list) 使这非常简单。我将键设为斜率，然后合并值（坐标）。

我似乎无法解决如何使用此必需结构将 'start' 转换为 'end'。

Answer 1

我不确定“我必须使用上面详述的结构”是什么意思。你有 start，你想要 end，所以在某些时候结构会发生变化。您的意思是根本不允许您使用字典或列表吗？您的导师如何期望您在不使用任何其他东西的情况下从 start 升至 end？这是一种仅使用元组（以及 start 和 end 列表）的方法。

end 将是一个元组列表。我们将在单独的列表中跟踪斜率。期望 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)

现在，我们 end 看起来像这样：

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

这种方法不是很好的原因是函数 find_tuple_index_with_slope() 需要遍历 end 中的所有元素以查找要追加的正确元素。这增加了代码的时间复杂度，当您可以使用字典来执行此查找时，速度会快得多，尤其是当您有很多点和很多不同的斜率值时。

更好的方法：用新字典替换查找函数，其中键是斜率的值，值是end中存储相应元组的索引。

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)

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

嵌套元组的压缩列表

Condense list of nested tuples

tuples

python-3.x