python - 获取时间段的值

Question

我正在用 Python3 编写一个程序，我需要的功能之一是通过引用两个日期时间值来计算一个值，如下所示。

假设一天被分成 8 个三小时的 block ，始终从 0000 UTC 开始。这些 block 中的每一个都有一个值 x，该值会因 block 而异，但不会在 block 本身内发生变化。

我需要向函数传递一个开始日期时间对象和一个结束日期时间对象，并让函数返回一个值，该值是 x 与开始日期时间对象和结束日期时间对象之间该 block 中的分钟数的乘积.

例如，如果开始时间是 0100 UTC，结束时间是 0200 UTC，0000 UTC 到 0300 UTC block 的 x 值是 20 那么这很容易，值为 60 * 20 = 1200。

如果开始时间为 0100 UTC，结束时间为 0400 UTC，0000 UTC 到 0300 UTC block 的 x 值为 20，0300 UTC 到 0600 UTC block 的 x 值为 30，则总和为是 (20 * 120) + (60 * 30) = 4200

开始时间和结束时间可以跨越多个 block 甚至几天。

我打算做的是设置一个字典的“day_list”，其中每个字典是 {"startchunk_time": #(e.g. 0000 UTC), "endchunk_time": #(e.g. 0300 UTC), "x": value }.那么伪代码将是:

def find_value(start_time, end_time):
    test_time = start_time
    while test_time < end_time:
        for item in day_list:
            if test_time > itemstartchunk_time and test_time < endchunk_time:
                #code to add the current x value and increase the test_time by one minute

因此，这涉及每次遍历整个“day_list”，即使已经找到相关值并且下一个值通常位于同一 block 中。

我的问题是:(i) 是否有一种方法可以在找到值后跳出 for 循环； (ii) 一般情况下是否有更有效的方法？

Answer 1

您的任务本质上是为分段常数函数 f(t) 求出 [a, b] 区间上的定积分。因此对应的不定积分F(t)是一个具有相同过渡点的分段线性函数。来自 calculus :

设 t[i] 是第 i 片段的开始时间(转换点)，f[i] 是相应的值。要查找给定时间段内的累计值，只需查找F(a) 和F(b)。 F[i] 过渡点中的值，您可以提前计算。因此，如果 i 已知，则操作的时间复杂度为 O(1)。

如果 t[i] 时间被排序，那么您可以在 O(log n) 时间使用二进制搜索(bisect 模块)。如果所有时隙都具有相同的持续时间，例如 3 小时，那么您可以分析地找到 i(在 O(1) 时间内):

assert s >= t[0]
i = (s - t[0]) // timedelta(hours=3)

假设:

• 同一时间段的值，例如，03..06 在不同的日子可能不同
• [a, b) 等输入时间段没有顺序，也不是等距的。

这是在恒定时间内计算 find_value() 的代码示例:

#!/usr/bin/env python3
from datetime import datetime, timedelta

slot_size = timedelta(hours=3)
slot_size_minutes = slot_size // timedelta(minutes=1)
f = [20, 30] # x values from the question
min_time = datetime(2015, 9, 29) # the time corresponding to f[0]
max_time = min_time + slot_size * len(f)

# compute F[i]
F = [0] * (len(f) + 1)
for i in range(len(f)):
    F[i+1] = F[i] + slot_size_minutes * f[i]

def find_value(start_time, end_time):
    return indefinite_integral(end_time) - indefinite_integral(start_time)

def indefinite_integral(t):
    if min_time <= t <= max_time:
        i = (t - min_time) // slot_size
        t_i = min_time + i * slot_size # i-th transition point
        minutes_in_ith_slot = (t - t_i) // timedelta(minutes=1)  # complete minutes
        return F[i] + f[i] * minutes_in_ith_slot if i < len(f) else F[i]
    else:
        raise ValueError('%r is not in [%s, %s] time range' % (
                         t, min_time, max_time))

示例用法:

def tt(hhmm):
    hour, minute = divmod(int(hhmm), 100)
    return min_time.replace(hour=hour, minute=minute)

assert find_value(tt("0100"), tt("0200")) == 1200
assert find_value(tt("0100"), tt("0400")) == 4200