减少执行时间Python(Reducing execution time Python)

减少执行时间Python(Reducing execution time Python)

因为我有这样的列表（河流排放树）：字符串类型（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)

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

given that I have a list like this (river discharge tree): String type (11 elements).

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

If you imagine it as a tree, it should be like (direction from top to bottom):

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

I just want to expand the list so I would have all the combinations like

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

There must be connection in the tree and the order must be from top to bottom.

What is the best way to do this? I wrote a code for this but this would take me about 6 days of executing for 6000 rows.

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)

Could you check my code and give me some advices? Thank you very much!

最满意答案

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

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']

So the key to doing this efficiently is ensuring we don't have to revisit nodes over and over again. We can do this by starting with the output and working our way back:

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)

If the rivers list is sorted properly, this is O(n), if it's not sorted (or, in the worst case, reverse sorted), it's O(n**2). "Sorted properly", in this case, means they are sorted from root to leaf in our upside down tree... as our processing order is: 4, 5, 3, 6, 7, 2, 9, 10, 8, 1

The final result is:

{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]}

Which can be converted to your final format via:

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']