时间戳

首页 > 解决方案 > Python中的搜索优化

python-3.x - Python中的搜索优化

问题描述

def CountingVallys(PathsTaken):

    #Converts the Strings U and D into 1 and -1 respectively
    Separate_Paths = [i for i in PathsTaken]
    for index, i in enumerate(Separate_Paths):
        if i == "D":
            Separate_Paths[index] = -1
        else:
            Separate_Paths[index] = 1

    Total_travels = [sum(Separate_Paths[0:i+1]) for i in range(len(Separate_Paths))]

    #ValleyDistance shows the indexes where the traveller is below sea level and Valley Depth shows the depth at those
    #Indexes
    ValleyDistance = []
    ValleyDepth = []
    for Distance, Depth in enumerate(Total_travels):
        if Depth < 0:
            ValleyDistance.append(Distance)
            ValleyDepth.append(Depth)


    #Checks the distance between each index to shows if the valley ends (Difference > 1)
    NumberOfValleys = []
    DistanceOfValleys = []
    TempDistance = 1
    for index, Distance in enumerate(ValleyDistance):

        # Check if final value, if so, check if the valley is distance 1 or 2 and append the final total of valleys
        if ValleyDistance[index] == ValleyDistance[-1]:
            if ValleyDistance[index] - ValleyDistance[index - 1] == 1:
                TempDistance = TempDistance + 1
                DistanceOfValleys.append(TempDistance)
                NumberOfValleys.append(1)
            elif ValleyDistance[index] - ValleyDistance[index - 1] > 1:
                DistanceOfValleys.append(TempDistance)
                NumberOfValleys.append(1)

        #For all indexes apart from the final index
        if ValleyDistance[index] - ValleyDistance[index-1] == 1:
            TempDistance = TempDistance + 1
        elif ValleyDistance[index] - ValleyDistance[index-1] > 1:
            DistanceOfValleys.append(TempDistance)
            NumberOfValleys.append(1)
            TempDistance = 1

    NumberOfValleys = sum(NumberOfValleys)

    return NumberOfValleys



if __name__ == "__main__":
    Result = CountingVallys("DDUDUUDUDUDUD")
    print(Result)

狂热的徒步旅行者会仔细记录他们的徒步旅行。远足总是在海平面开始和结束，每一步向上 (U) 或向下 (D) 代表高度的一个单位变化。我们定义以下术语：

山谷是低于海平面的一系列连续台阶，从海平面下降开始，到海平面上升结束。

查找并打印穿过的山谷数量。

在这个问题中，由于执行时间过长，我被标记了，我想知道是否可以进行任何明确的优化以使其更快。我相信使用“for-loops”是罪魁祸首，但我不确定执行我的步骤的任何其他方式。

标签： python-3.x

解决方案

Total_travels = [sum(Separate_Paths[0:i+1]) for i in range(len(Separate_Paths))]

在上面的代码中，为什么要重复已经执行的计算？sum(Separate_Paths[0:i+1]) = sum(Separate_Paths[0:i] + Separate_Paths[i+1]

您可以有效地制作列表 Total_travels。这应该可以解决程序执行时间过长的问题。

>>> a
[2, 6, 4, 9, 10, 3]
>>> cumulative_sum = []
>>> sum_till_now = 0
>>> for x in a:
...     sum_till_now += x
...     cumulative_sum.append(sum_till_now)
... 
>>> cumulative_sum
[2, 8, 12, 21, 31, 34]
>>>

numpy 有一个内置的cumsum，我认为这对你的问题来说太过分了。

推荐阅读