减少Python的执行时间

Question

鉴于我有一个这样的列表（河流排放树）：字符串类型（11个元素）。

From;To
 1;2
 2;3
 5;4
 3;4
 4;-999
 9;6
 6;5
 10;7
 8;7
 7;5

如果你把它想象成一棵树，它应该是（从上到下的方向）：

1   9  8  10
|   |   \/
2   6   7
|    \ /
3    5
|  /
4
|

我只是想扩展列表，所以我会有所有的组合，如

From;To
 1;2
 2;3
 5;4
 3;4
 4;-999
 9;6
 6;5
 10;7
 8;7
 7;5
 1;3
 1;4
 6;4
 9;4
 9;5
 7;4
 8:4
 8:5
 10:5
 10:4

树中必须有连接，顺序必须从上到下。

做这个的最好方式是什么？我为此编写了一个代码，但这将花费我大约6天的6000行执行。

should_restart = False
for b in range(1, lengthchange):
    row1 = str(tree[b])
    position2 = row1.find(delimeter)
    position3 = row1.find(end)
    from1 = (row1[0:position2])
    to1 = row1[position2+1:position3]
    for c in range(1, lengthchange):
        row2 = str(tree[c])
        position4 = row2.find(delimeter)
        position5 = row2.find(end)
        from2 = (row2[0:position4])
        to2 = row2[position4+1:position5]
        if to1 == from2 and not to2 == "-999":
            append1 = str(from1)+";"+str(to2)+"\n"
            seen = set(tree)
            if append1 not in seen:
                seen.add(append1)
                tree.append(append1)
                should_restart = True
                count_test = count_test+1
                print(count_test)
                lengthchange = len(tree)

你能查一下我的代码并给我一些建议吗？非常感谢你！

Answer 1

因此，有效地做到这一点的关键是确保我们不必一遍又一遍地重新访问节点。我们可以通过从输出开始并回过头来做到这一点：

crivers = rivers[:]  # copy the rivers list, as this process is destructive
ckeys = set(river.split(";")[0] for river in crivers)  # make a set for O(1) lookup
result = {}
while crivers:
    for river in crivers[:]:
        key, value = river.split(";")
        if value in ckeys:
            continue  # skip rivers that are flowing into unprocessed rivers
        result[int(key)] = [int(value)] + result.get(int(value), [])
        ckeys.remove(key)
        crivers.remove(river)

如果rivers列表正确排序，则为O（n），如果未排序（或者，在最坏的情况下，反向排序），则为O（n ** 2）。在这种情况下，“正确排序”意味着它们在我们的颠倒树中从根到叶排序......因为我们的处理顺序是：4, 5, 3, 6, 7, 2, 9, 10, 8, 1

最终结果是：

{1: [2, 3, 4, -999], 
 2: [3, 4, -999], 
 3: [4, -999], 
 4: [-999], 
 5: [4, -999], 
 6: [5, 4, -999], 
 7: [5, 4, -999], 
 8: [7, 5, 4, -999], 
 9: [6, 5, 4, -999], 
10: [7, 5, 4, -999]}

可以通过以下方式转换为最终格式：

fmt_lst = []
for key in result:
    for val in result[key]:
        fmt_lst.append("%s;%s" % (key, val))

['1;2', '1;3', '1;4', '1;-999', 
 '2;3', '2;4', '2;-999', 
 '3;4', '3;-999', 
 '4;-999', 
 '5;4', '5;-999', 
 '6;5', '6;4', '6;-999', 
 '7;5', '7;4', '7;-999', 
 '8;7', '8;5', '8;4', '8;-999', 
 '9;6', '9;5', '9;4', '9;-999', 
 '10;7', '10;5', '10;4', '10;-999']