python - 如何对字典中的日期字符串进行排序

Question

如何在特定日期后获取第一个 key ？

当 date_table 越来越大时，最好的解决方案是什么？

def get_first():
    date_table = {
        'this is example 1': '01:20 2013-08-07',
        'this is example 2': '11:45 2012-03-23',
        'this is example 3': '19:00 2013-12-01', 
    }
    certain_date = '12:14 2013-06-23'
    # TODO: sort, filter

print get_first()
>> 'this is example 1'

Answer 1

您必须排序然后过滤，以及解析结构中的所有日期:

from datetime import datetime

certain_date = datetime.strptime(certain_date, '%H:%M %Y-%m-%d')
match = next((k for v, k in sorted((datetime.strptime(v, '%H:%M %Y-%m-%d'), k) for k, v in date_table.iteritems()) if v >= certain_date), None)

演示:

>>> certain_date = datetime.strptime(certain_date, '%H:%M %Y-%m-%d')
>>> next((k for v, k in sorted((datetime.strptime(v, '%H:%M %Y-%m-%d'), k) for k, v in date_table.iteritems()) if v >= certain_date), None)
'this is example 1'

另一种方法是过滤所有在您搜索日期之后且最接近您的搜索日期的日期:

from datetime import datetime, timedelta

parse = lambda d: datetime.strptime(d, '%H:%M %Y-%m-%d')
certain_date = parse(certain_date)
match = min(date_table, key=lambda k: parse(date_table[k]) - certain_date if parse(date_table[k]) > certain_date else timedelta.max)

演示:

>>> min(date_table, key=lambda k: parse(date_table[k]) - certain_date if parse(date_table[k]) > certain_date else timedelta.max)
'this is example 1'

您真的想重新考虑您的结构，并使用堆队列或 btree 之类的东西来使您的数据结构更易于进行此类访问。

即使是带有已解析的(datetime, key) 元组的排序列表也会好得多，因为bisect module会让您在 O(log n) 时间内找到您的“下一个”值，而不是 O(n log n) 用于排序或 O(n) 用于复杂的 min() 过滤器。

您可以使用以下方法快速将您的结构变成这样的列表:

from functools import total_ordering

@total_ordering
class Entry(object):
    def __init__(dt, key):
        self.dt = dt
        self.key = key

    def __eq__(self, other):
        if not isinstance(other, type(self)): return NotImplemented
        return self.dt == other.dt and self.key == other.key

    def __lt__(self, other):
        if not isinstance(other, type(self)): return NotImplemented
        if self.dt < other.dt:
            return True
        return self.dt == other.dt and  self.key < other.key

date_list = [Entry(datetime.strptime(v, '%H:%M %Y-%m-%d'), k) for v, k in date_table.iteritems()]
date_list.sort()

然后找到你的下一场比赛:

import bisect
match = date_list[bisect.bisect(date_list, Entry(current_date, None))]

并且您使用 bisect.insort() 来保持列表排序。