how to sort date strings in a dictionary

Question

How to get the first key after a certain date?

What is the best solution when date_table is getting larger?

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

You'll have to sort then filter, as well as parse all the dates in your structure:

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)

Demo:

>>> 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'

The alternative is to filter all dates that come after and is closest to your search date:

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)

Demo:

>>> 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'

You really want to rethink your structure, and use something like a heap queue or btree to keep your data structure more accessible for this kind of access.

Even a sorted list with parsed (datetime, key) tuples would perform much better, as the bisect module would let you find your 'next' value in O(log n) time as opposed to O(n log n) for sorting or O(n) for the complex min() filter.

You can quickly turn your structure into such a list with:

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()

then find your next match with:

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

and you use bisect.insort() to keep the list sorted.