Как отсортировать строки даты в словаре

Question

Как получить первый ключ после определенной даты?

Какое оптимальное решение при увеличении даты_таблицы?

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) 

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' 

Вы действительно хотите пересмотреть свою структуру, и использовать что-то вроде очереди кучи или ВТКЕЕ, чтобы сохранить структуру данных более доступными для этого вида доступа.

Даже отсортированный список с разбираемых (datetime, key) кортежей будет выполнять гораздо лучше, как bisect module позволит вам найти свой «следующий» значение в O (журнал N) время, в отличие от O (N журнал 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() сохранить список отсортирован.

Answer 2

Вы можете использовать datetime модуль и min здесь:

>>> from datetime import datetime, timedelta 
>>> certain_date = '12:14 2013-06-23' 
>>> c_d = datetime.strptime(certain_date, "%H:%M %Y-%m-%d") 
>>> def func(x): 
     d = datetime.strptime(x[1], "%H:%M %Y-%m-%d") 
     delta = d - c_d if d > c_d else timedelta.max 
     return delta 
... 
>>> min(date_table.items(), key = func) 
('this is example 1', '01:20 2013-08-07') 
>>> min(date_table.items(), key = func)[0] 
'this is example 1' 

datetime.strptime преобразует дату в объект даты и времени, так c_d теперь выглядит примерно так:

>>> c_d 
datetime.datetime(2013, 6, 23, 12, 14) 

Сейчас внутри func:

delta = d - c_d if d > c_d else timedelta.max 

Это проверяет, является ли дата текущего элемента более новой, чем c_d, или нет, если да, то она возвращает их разницу, иначе она возвращает timedelta.max.

Где timedelta.max является:

>>> timedelta.max 
datetime.timedelta(999999999, 86399, 999999) 

Answer 3

Что является лучшим решением, когда date_table становится больше?

Словари не подходят для поиска диапазона (то есть, когда вы хотите получить диапазон значений на основе их ключей).Это связано с тем, что словари используют хеширование для хранения ключей и, следовательно, не могут гарантировать порядок сортировки, однако для этого компромисса они обеспечивают постоянный поиск времени для любого конкретного ключа.

Для получения наилучших результатов лучше использовать некоторую форму сбалансированного двоичного дерева поиска, я уверен, что для Python существует множество реализаций, если вы используете Google для одного. Это позволяет выполнять поиск диапазона в логарифмическом времени, который, очевидно, медленнее, чем постоянный, но определенно быстрее, чем линейный.

Если вы абсолютно точно знаете, что ваш словарь не будет развиваться за определенный небольшой размер, то вполне приемлемо использовать линейный поиск по ключам, поскольку разница в производительности будет незначительной.

Answer 4

Вы могли бы даже быть в состоянии обойтись без конвертирования строк в datetime объектов, вот вариант с использованием bisect:

from operator import itemgetter 
from bisect import bisect 

name, tds = zip(*sorted(((k, v.split()[::-1]) for k, v in date_table.iteritems()), key=itemgetter(1))) 
certain_date = '12:14 2013-06-23'.split()[::-1] 
print name[bisect(tds, certain_date)] 
# this is example 1