根据日期范围查找价格的有效方法

Question

我正在尝试将能源使用数据导入 Python，并且我正在尝试找出一种进行价格查找的好方法。

单位能源价格每年会变化几次，因此我有日期范围和单价，例如：

start_date     end_date       unit_cost
----------     --------       ---------
2023-01-01     2023-03-31     0.2384
2023-04-01     2023-09-30     0.2761
2023-10-01     2024-01-31     0.2566

可以安全地假设日期范围是连续的，因此可能可以简化为每个单价的开始日期。

然后，我检索每日单位消耗值列表，并希望将其乘以该日期的适当单位成本。

显然有很多愚蠢、暴力的方法可以做到这一点；迭代数据结构并检查当前日期是否在开始日期和结束日期之间……但我认为必须有一种聪明的、Pythonic 的方法来做到这一点。我对简短、清晰的代码意义上的效率感兴趣，而不是原始性能，但快速算法也可能是相关的！

是否有适用于该用例的数据结构和/或模块？

Answer 1

标准库中没有一种神奇的方法可以用一行代码解决您的问题。您可以使用 pandas 等第三方库，但我更喜欢 KISS 原则，并避免为如此简单的任务引入大量依赖项。因此，我实现了一个使用二分搜索方法来完成您的任务的解决方案。您可以使用

add

方法将新日期添加到历史记录中，并使用

find

方法查找特定日期的单位成本。我还假设您不需要结束日期，因为您的开始日期始终在上一个间隔结束后的第二天。

from datetime import datetime
from bisect import bisect_right

class PriceHistory:
    def __init__(self):
        self.dates = []
        self.prices = []

    def add(self, start_date, unit_cost):
        start_date = datetime.strptime(start_date, '%Y-%m-%d')

        self.dates.append(start_date)
        self.prices.append(unit_cost)

    def find(self, date):
        date = datetime.strptime(date, '%Y-%m-%d')
        if date < self.dates[0]:
            raise ValueError('Date is out of range')
        index = bisect_right(self.dates, date) - 1
        return self.prices[index]

# Usage:
price_history = PriceHistory()
price_history.add('2023-01-01', 0.2384)
price_history.add('2023-04-01', 0.2761)
price_history.add('2023-10-01', 0.2566)

print(price_history.find('2023-01-30'))

对于有连续日期列表的情况，您可以进一步优化此代码。在这种情况下，您可以使用二分搜索来查找第一个索引，然后采用双指针方法来查找后续日期的单位成本。

这是示例：

    def find_sequence(self, dates):
        # Convert the dates to datetime objects for comparison
        dates = [datetime.strptime(date, '%Y-%m-%d') for date in dates]

        # Find the index of the first date using binary search
        first_index = bisect_right(self.dates, dates[0]) - 1

        # Use a two-pointer approach to find the prices for the rest of the dates
        prices = []
        date_index = 0
        for i in range(first_index, len(self.dates)):
            while date_index < len(dates) and dates[date_index] < self.dates[i]:
                prices.append(self.prices[i])
                date_index += 1
            if date_index == len(dates):
                break

        return prices

在查找日期序列的价格时，算法的计算复杂度将是

O(log(n) + m)

而不是

O(m*log(n))

。这是由于使用了双指针方法，它取代了对每个日期进行二分搜索的需要。