从元组列表中查找空间顺序的最有效方法(Python)
我有一个循环增长算法(带闭合链接的线增长)，在每次迭代时，在现有点之间添加新的点。
每个点的链接信息以元组形式存储在列表中。该列表是迭代更新的。
问题：
- 将这些点的空间顺序作为列表返回最有效的方法是什么？
- 我是否需要在每一次迭代中计算整个顺序，还是有一种方法将新的点以有序的方式累计地插入到列表中？
我能想到的只有以下几点：
tuples = [(1, 4), (2, 5), (3, 6), (1, 6), (0, 7), (3, 7), (0, 8), (2, 8), (5, 9), (4, 9)]
starting_tuple = [e for e in tuples if e[0] == 0][0]
## note: 'starting_tuple' could be either (0, 7) or (0, 8), starting direction doesn't matter
order = [starting_tuple[0], starting_tuple[1]]
## order will always start from point 0
idx = tuples.index(starting_tuple)
## index of the starting tuple
def findNext():
global idx
for i, e in enumerate(tuples):
if order[-1] in e and i != idx:
ind = e.index(order[-1])
c = 0 if ind == 1 else 1
order.append(e[c])
idx = tuples.index(e)
for i in range(len(tuples)/2):
findNext()
print order它正在工作，但既不优雅(非节奏曲)，也不高效。在我看来，递归算法可能更合适，但不幸的是，我不知道如何实现这样的解决方案。
另外，请注意，我使用的是Python 2，只能访问完整的python包(没有numpy)。
这个问题也是已发布关于SO的问题。
回答 1
Code Review用户
发布于 2019-01-18 00:07:55
不需要递归。您可能需要首先将元组转换为dict，以使其更具可读性。然后在dict上迭代以构造一个有序列表。
就效率(或时间/空间复杂性)而言，您的代码在时间上是O(n^3)，在辅助空间中是O(1)。请注意，idx = tuples.index(e)根本不是必要的，因为tuples.index(e) == i。利用这一点，您的代码就可以及时成为O(n^2)。最具时间效率的解决方案是O(n)，这也是所提出的解决方案涉及dict的时间复杂性。然而，该解决方案的辅助空间复杂度是O(n) --比您的原始方法要差。
如果要在获得新的tuples列表后更新顺序，可以保留dict并迭代新的tuples，并将其与dict中的值进行比较，查看是否有任何更改。但是，在大多数情况下，这种方法的效率可能比从头构建新的dict更糟糕。
from collections import defaultdict
def tuples_to_neighbors_dict(tuples):
"""
Covert `tuples` to a dict mapping each point to a list of its neighbors.
"""
neighbors = defaultdict(list)
for (a,b) in tuples:
neighbors[a].append(b)
neighbors[b].append(a)
return neighbors
def tuples_to_order(tuples, start=0):
"""
Covert `tuples` to a list of points.
"""
neighbors = tuples_to_neighbors_dict(tuples)
order = []
prev = None
current = start
while current != start or prev is None:
# add the current value to the list
order.append(current)
# move to the next -- pick the neighbor which we haven't visited yet
neigh = neighbors[current]
new = neigh[1] if neigh[0] == prev else neigh[0]
prev = current
current = new
return order编辑:我刚才看了一下SO问题，注意到有一个答案与我的几乎相同
https://codereview.stackexchange.com/questions/211723
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号