Python在一次传递函数中完成搜索 [英] Python complete search in one pass function

问题描述

我正在编写一个程序，其中列出了奶牛挤奶的开始和结束时间列表，并确定了> = 1头奶牛挤奶的最长时间和没有奶牛正在挤奶的最长时间。

I am writing a program that takes in a list of start and end times for farmers milking cows and determines both the longest time where >=1 cow is being milked and the longest time where no cows are being milk.

在其中，我尝试过使用此功能。这是一个关于完整搜索的练习，但是当有大量数据时，这还不够快（我认为因为有n ^ 2次迭代）。

In it, I've tried using this function. It's an exercise on complete search, but this isn't fast enough when there's a lot of data (I think because there are n^2 iterations).

timesIS 只是增加开始顺序的时间列表，而 timesDE 是减少结束的相同时间的列表。 timeIndex 是开始的位置。对于最长的挤奶间隔，我的程序稍后会为每个索引执行此操作并返回最长的间隔。

timesIS is simply a list of the times in increasing start order, and timesDE is a list of the same times by decreasing end. timeIndex is the position from which to start. For the longest interval of milking, my program later does this for every index and returns the longest interval.

虽然仍然保持完整的搜索，但我怎样才能使这个更多效率（切换到接近n次传递的东西，或许）？

While still keeping to a complete search, how can I make this more efficient (switch to something closer to n passes, perhaps)?

def nextCease(TimesIS, timesDE, timeIndex):
    latestTime = TimesIS[timeIndex][1]
    for j in range (0, len(timesDE)):
        for i in range (0, len(timesDE)):
            if timesDE[i][0]<=latestTime and timesDE[i][1]>=latestTime:
                latestTime = timesDE[i][1]
        if latestTime == timesDE[0][1]:
            return latestTime
            break
    return latestTime

这是一个小块数据输入（第一行只是农民数量）：

Here's a small piece of data input (first line is just the number of farmers):

6
100 200
200 400
400 800
800 1600
50 100
1700 3200

我想这是一个最小，完整且可验证的示例：

I think this is a minimal, complete, and verifiable example:

from operator import itemgetter
times = [[100,200], [200,400], [400,800], [800,1600], [50,100], [1700,3200]

def nextCease(TimesIS, timesDE, timeIndex):
    latestTime = TimesIS[timeIndex][1]
    for j in range (0, len(timesDE)):
        for i in range (0, len(timesDE)):
            if timesDE[i][0]<=latestTime and timesDE[i][1]>=latestTime:
                latestTime = timesDE[i][1]
        if latestTime == timesDE[0][1]:
            return latestTime
            break
    return latestTime

timesIS = sorted(times[:], key=itemgetter(0)) #increasing starttimes
timesDE = sorted(times[:], key=itemgetter(1), reverse=True) #decreasing endtimes

longestIntervalMilk = 0
for i in range (0, len(times)):
    interval = nextCease(timesIS, timesDE, i) - timesIS[i][0]
    if interval > longestIntervalMilk:
        longestIntervalMilk = interval

longestIntervalNoMilk = 0
latestFinish = 0
for i in range (0, len(times)):
    latestFinish = nextCease(timesIS, timesDE, i)
    timesIS2 = timesIS[:]
    while(timesIS2[0][0] < latestFinish):
        nextStartExists = True
        del timesIS2[0]
        if timesIS2 == []:
            nextStartExists = False
            break
    if nextStartExists == True:
        nextStart = timesIS2[0][0]
        longestIntervalNoMilk = nextStart - latestFinish

print(str(longestIntervalMilk) + " " + str(longestIntervalNoMilk) + "\n"))

编辑：与此同时，我写了这篇文章。它为很长的列表提供了错误的输出（它是1001行所以我不会在这里重新打印，但你可以在 http://train.usaco.org/usacodatashow?a=iA4oZAAX7KZ ）我很困惑为什么：

In the meantime, I wrote up this. It gives the wrong output for a very long list (it's 1001 lines so I won't reprint it here, but you can find it at http://train.usaco.org/usacodatashow?a=iA4oZAAX7KZ) and I'm confused as to why:

times = sorted(times[:], key=itemgetter(0))

def longestMilkInterval(times):
    earliestTime = times[0]
    latestTime = times[0][1]
    interval = 0
    for i in range (1, len(times)):
        if times[i][1] > latestTime and times[i][0] <= latestTime:
            if times[i][1] - earliestTime[0] > interval:
                interval = times[i][1] - earliestTime[0]
                latestTime = times[i][1]
        else:
            earliestTime = times[i]
            latestTime = times[i][1]
            print(earliestTime)
    return interval

def longestNoMilkInterval(times):
    earliestTime = times[0][1]
    interval = 0
    for i in range (0, len(times)):
        if times[i][0] >= earliestTime:
            if times[i][0] - earliestTime > interval:
                interval = times[i][0] - earliestTime
                break
        else:
            earliestTime = times[i][1]
    return interval

输出应为 912 184 （> = 1牛， 0牛）。

Output should be 912 184 (>=1 cow, 0 cow).

推荐答案

这是一个非常简单的方法，它在一次通过中完成，包括排序，所以复杂性会是 O（n * logn）。

Here is a very straightforward approach which does it in one pass, including a sort, so the complexity would be O(n*logn).

# Part 1: transform to tuples (start_time, typ)
items = []
for start, end in times:
    items += [(start, 's'), (end, 'e')]
items = sorted(items)

# Part 2: compute max durations where 0 or 1+ cows are being milked
max_0_cows = max_1plus_cows = 0

last_intersection_time = items[0][0] # starting with first cow milk time
nof_cows_milked = 1

for i, (start_time, typ) in enumerate(items[1:], 1):
    if items[i-1][0] == start_time and items[i-1][1] != typ:
        continue
    if i+1 < len(items) and items[i+1][0] == start_time and items[i+1][1] != typ:
        continue

    if typ == 's':
        nof_cows_milked += 1
    elif typ == 'e':
        nof_cows_milked -= 1

    # check if we cross from 1+ -> 0 or 0 -> 1+
    if (typ, nof_cows_milked) in (('e', 0), ('s', 1)):
        duration = start_time - last_intersection_time
        if nof_cows_milked == 1:
            max_0_cows = max(max_0_cows, duration)
        if nof_cows_milked == 0:
            max_1plus_cows = max(max_1plus_cows, duration)
        last_intersection_time = start_time

print("Max time 0 cows: {}, Max time 1+ cows: {}".format(max_0_cows, max_1plus_cows))

1. 构建项：它将开始/结束itervals放入元组列表中（start_time ，典型）所以我们可以遍历列表，如果我们看到一个 s 一头新牛正在挤奶， e 然后一头奶牛停止挤奶。通过这种方式，我们可以随时获得一个 nof_cows_milked 的计数器，这是获得最长时间0牛奶挤奶和最长时间1+牛挤奶的基础


2. 实际最长时间查找器检查从0 - > 1+奶牛挤奶或1头奶牛的所有过渡 - > 0头奶牛挤奶。在前4行中，它筛选出两个相邻的itervals（一个农民在另一个农民开始时停止）的情况。它用 last_intersection_time 跟踪这些时间，并将持续时间与 max_0_cows 和 max_1_plus_cows 的最长持续时间。再说一遍，这部分不是很漂亮，也许还有更优雅的方法来解决这个问题。

1. Building of items: It puts the start/end itervals into a list of tuples (start_time, typ) so we can traverse the list and if we see a s a new cow is being milked and e then a cow is stopped being milked. This way we can have a counter nof_cows_milked at any time which is the basis for getting the "max time 0 cows milked" and "max time 1+ cows milked"
2. The actual longest-time-finder checks for all the transitions from 0 -> 1+ cows milked or 1+ cows -> 0 cows milked. In the first 4 lines it filters out the cases when two adjacent itervals (one farmer stops when the other farmer starts) It keeps track of those times with last_intersection_time and compares the duration to the max duration of max_0_cows and max_1_plus_cows. Again, this part is not very pretty, maybe there are more elegant ways to solve that.

[我的算法]给出错误的输出[...]我很困惑为什么

[my algorithm] gives the wrong output [...] and I'm confused as to why

你的算法基本上只是检查单个元组的最长间隔，但不检查重叠或相邻的元组。

Your algorithm basically just checks for the longest interval of a single tuple, but doesn't check for overlapping or adjacent tuples.

将这些间隔视为可视示例：

Take these intervals as an visual example:

您的代码只找到间隔GH，而您需要找到CF.在某个地方需要跟踪并行挤奶的奶牛数量，因此您至少需要 nof_of_cows_milked 计数器，如我的代码示例所示。

Your code just finds the interval G-H, whereas you need to find C-F. You somewhere need to keep track of how many cows are milked in parallel, so you need at least the nof_of_cows_milked counter as in my code example.

这篇关于Python在一次传递函数中完成搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！