Python中的搜索优化

Question

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循环"是责任，但我不确定有任何其他方法来执行我的步骤。

Answer 1

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有一个内置的总和，我认为这对你的问题来说是多余的。

Answer 2

这是另一个解决方案:

通过使用堆栈可以很容易地找到谷。

1. 对于每个相同类型的新路径("D"或"U")将其推入堆栈
2. 在push之前，检查最后一个项目，如果它们是相反的，然后从堆栈中删除它(if(stack[-1]!=path[i]): stack.pop())并记住(last_path=path[i])
3. 如果堆栈是空的，那么它意味着有和海平面切割(山谷或山)。如果最后一个路径是"U"所以这意味着它是一个谷，所以我们计数它(if(len(stack)==0): if(last_path=='U'): valleys+=1)。
4. 有可能在路径的末端与海平面切割，所以我们需要在环路之外处理它(if(len(stack)==0 and last_path=='U'): valleys+=1)。

代码如下:

def countingValleys(steps, path):
stack=[]
valleys=0
last_path=None
for i in range(len(path)):
if(len(stack)==0):
if(last_path=='U'):
valleys+=1
stack.append(path[i])
else:
if(stack[-1]!=path[i]):
stack.pop()
last_path=path[i]
else:
stack.append(path[i])
if(len(stack)==0 and  last_path=='U'):
valleys+=1
return valleys
print(countingValleys(12,"DUDUDUUUUDDDDU"))