python - 我的 Python 代码 TimeLimitExceeded。如何优化和减少代码中的操作数量？

Question

这是我的代码：

def seperateInputs(inp):
    temp = inp.split()
    n = int(temp[0])
    wires = []
    temp[1] = temp[1].replace('),(', ') (')
    storeys = temp[1][1:len(temp[1])-1].split()
    for each in storeys:
        each = each[1:len(each)-1]
        t = each.split(',')
        wires.append((int(t[0]), int(t[1])))
    return n, wires


def findCrosses(n, wires):
    cross = 0
    for i in range(len(wires)-1):
        for j in range(i+1, len(wires)):
            if (wires[i][0] < wires[j][0] and wires[i][1] > wires[j][1]) or (wires[i][0] > wires[j][0] and wires[i][1] < wires[j][1]):
                cross += 1
    return cross

def main():
    m = int(input())
    for i in range(m):
        inp = input()
        n, wires = seperateInputs(inp)
        print(findCrosses(n, wires))
main()

问题问：

我还测试了我自己的示例输入，这让我得到了正确的输出：

Sample input:
3
20 [(1,8),(10,18),(17,19),(13,16),(4,1),(8,17),(2,10),(11,0),(3,2),(12,3),(18,14),(7,7),(19,5),(0,6)]
20 [(3,4),(10,7),(6,11),(7,17),(13,9),(15,19),(19,12),(16,14),(12,8),(0,3),(8,15),(4,18),(18,6),(5,5),(9,13),(17,1),(1,0)]
20 [(15,8),(0,14),(1,4),(6,5),(3,0),(13,15),(7,10),(5,9),(19,7),(17,13),(10,3),(16,16),(14,2),(11,11),(8,18),(9,12),(4,1)]

Sample output:
38
57
54

然而，虽然小输入有效，但中到大输入给了我 TimeLimitExceeded 错误：

我该如何优化呢？有没有办法比我已经拥有的操作少得多？TIA。

标签： pythonperformance

Answer 1

您可以做一些事情。

首先，如果您首先按左侧建筑物对列表进行排序，则事情会更容易计算。这需要一些前期成本，但在处理过程中会使事情变得更容易和更快，因为您只需要比较到目前为止看到的较低秒数元素。代码很好也很简单：

l =  [(3,4),(10,7),(6,11),(7,17),(13,9),(15,19),(19,12),(16,14),(12,8),(0,3),(8,15),(4,18),(18,6),(5,5),(9,13),(17,1),(1,0)]

def count_crossings(l):
    s = sorted(l, key=lambda p: p[0])
    endpoints = []
    count = 0
    for i, j in s:
        count += sum(e > j for e in endpoints)
        endpoints.append(j)
    return count

count_crossings(l)
# 57

这有点低效，因为您正在循环遍历endpoints每个点。如果你也可以保持endpoints 排序，你只需要计算小于给定右手沸腾底的数字。每当您想要对列表进行排序时，您都应该考虑使用令人惊叹的内置库bisect。这将使事情快一个数量级：

import bisect

def count_crossings_b(l):
    s = sorted(l, key=lambda p: p[0])
    endpoints = []
    count = 0
    for i, j in s:
        bisect.insort_left(endpoints, j)
        count += len(endpoints) - bisect.bisect_right(endpoints, j) 

    return count

count_crossings_b(l)
# 57

我的笔记本电脑上的各种时间如下所示：

l = [(random.randint(1, 200), random.randint(1, 200)) for _ in range(1000)]

%timeit findCrosses(l) # original
# 179 ms ± 1.69 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%timeit count_crossings(l)
# 38.1 ms ± 2.03 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

%timeit count_crossings_b(l)
# 1.08 ms ± 22.1 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)