пятница, 13 июня 2014 г.

Парсим DateTime

  В Интернете уже довольно много скопилось вопросов по поводу того, как парсить DateTime. Проблема не именно в разборе, конечно, а в его скорости. И есть полно примеров, какие параметры нужно передавать в TryParse, чтобы побыстрее выполнялся разбор. Обычно ответы сходятся к колдованием над IFormatProvider и DateTimeStyles. Я хочу предложить свое решение.


  В разборе даты немаловажную роль играют сами данные, которые нужно обработать. Если возник вопрос о быстродействии приложения, и приходится относить этот вопрос к разбору DateTime, то скорее всего приложение обрабатывает много данных.
  Небольшой пример, который проще объяснит подход. Нужно загрузить из файлов большое количество счетов. Каждый счет содержит дату оплаты дату выставления. Даты оплаты и выставления скорее всего не содержат указаний времени. Если счета выставляются и оплачиваются раз в месяц, то в идеале приложению нужно разобрать максимум 31 дату. Если раз в год - 366.
  Решение напрашивается само собой - сделать кеш разобранных дат. В качестве основы кеша для быстрого поиска я буду использовать бинарное дерево. Можно, конечно, выбрать какой-нибудь хеш. Но балансировка небольшого количества элементов (31/366) это пустяки по сравнению с over9000 поисками с использованием хешей. Да и не доверял я хешам никогда :-)
  Для ведения индекса в списке связанных данных придется делать новый тип - ассоциация исходных данных и результата разбора.

  1. public class DateTimePair  
  2. {  
  3.   public string Original { getset; }  
  4.   public DateTime Parsed { getset; }  
  5. }  

  Сам кеш выполним в виде списка

  1. public List<DateTimePair> parsedDates = new List<DateTimePair>();  

  Для того, чтобы бинарное дерево знало точное правило сравнения с узлами, нужно реализовать интерфейс сравнимости ассоциаций.

  1. public class DateTimePair: IComparable<DateTimePair>  
  2. {  
  3.   //...  
  4.   public int CompareTo(DateTimePair other)  
  5.   {  
  6.     return Original.CompareTo(other.Original);  
  7.   }  
  8. }  

  Осталось теперь только научиться пользоваться этим кешем - правильно искать в нем и заполнять его.

  1. var dt = "12.06.2014";  
  2.   
  3. var pair = new DateTimePair { Original = dt };  
  4. var position = parsedDates.BinarySearch(dt);  
  5. if (position < 0)  
  6. {  
  7.   // В кеше нет такой даты - будем парсить  
  8.   DateTime res;  
  9.   if (DateTime.TryParse(dt, out res))  
  10.   {  
  11.     pair.Parsed = res;  
  12.     parsedDates.Insert(~position, pair);  
  13.     return res;  
  14.   }  
  15.   else  
  16.   {  
  17.     // Разобрать дату не смогли  
  18.   }  
  19. }  
  20. else  
  21. {  
  22.   // В кеше дата найдена - берем оттуда  
  23.   return parsedDates[position].Parsed;  
  24. }  

  Тут должно быть все предельно ясно.

  UPD. Как справедливо в комментариях заметил hazzik, лучше использовать просто Dictionary. Там поиск будет быстрее. К тому же будет не совсем честно говорить, что я использовал бинарное дерево. Ведь тут нет ни листьев, ни разворотов. Правильней будет - бинарный поиск по сортированному массиву.

16 комментариев:

  1. В чем суть этого поста? Я не понял:(

    ОтветитьУдалить
    Ответы
    1. Суть в том, что парсить одинаковые даты не нужно. Делаем кеш и используем его.

      Удалить
    2. А у вас только даты или даты со временем? Если только даты и ограниченный их промежуток, то да, есть смысл кешировать результат. Но, если у вас даты со временем и в разных форматах, то я думаю будет очень много промахов.

      Удалить
    3. Только даты, конечно. Если будет еще и время, то нет смысла кешировать.

      Удалить
  2. Во-первых, я бы советовыл использовать HashSet/Dictionary, вместо List, так поиск будет быстрее. И алгоритм сведется к тому, чтобы просто положить разобранную дату, если ее там нет.

    ОтветитьУдалить
    Ответы
    1. Хмм, разве двоичный поиск в сортированном списке медленней, чем поиск в словаре?

      Удалить
    2. Я написал в посте про хеши - там скорость поиска будет намного ниже.
      Чтобы положить разобранную дату, нужно ее разобрать. А тут как раз и есть узкое место производительности. Парсить строку для даты - это очень долгая операция.

      Удалить
    3. Артём, давай проверим.

      Мурад, чем плох Dictionary? Разбирать нужно только то, чего нет в словаре.

      Удалить
    4. Вот вам результаты распарсивания 100000 случайных дат:

      Binary Search: 458
      Dictionary: 73
      Binary Search: 447
      Dictionary: 47
      Binary Search: 467
      Dictionary: 61
      Binary Search: 410
      Dictionary: 53
      Binary Search: 415
      Dictionary: 57
      Binary Search: 409
      Dictionary: 50
      Binary Search: 430
      Dictionary: 46
      Binary Search: 402
      Dictionary: 49
      Binary Search: 413
      Dictionary: 52
      Binary Search: 429
      Dictionary: 54
      ========
      Dictionary: 54.2, Min: 46, Max: 73
      Binary Search: 428, Min: 402, Max: 467
      ========

      Удалить
    5. https://gist.github.com/hazzik/8e060c732896a0a33d23 -- вот код.

      Теперь учитывая, что поиск по словарю работает в 10 раз быстрее, и занимает меньше кода. Объясните мне смысл этого поста?

      Удалить
    6. Смысл данного поста в использовании кеша при парсинге дат. А реализацию кеша да, надо бы поменять :)

      Удалить
    7. Ага, поглядел Dictionary. Там используется оптимизация с корзинами. Это делает поиск на небольшом (хм, насколько небольшое?) количестве данных практически мгновенным. Спасибо, hazzik, за просвещение :-)

      Удалить
    8. http://msdn.microsoft.com/en-us/library/xfhwa508.aspx
      The Dictionary generic class provides a mapping from a set of keys to a set of values. Each addition to the dictionary consists of a value and its associated key. Retrieving a value by using its key is very fast, close to O(1), because the Dictionary class is implemented as a hash table.

      Это явно быстрее бинарного поиска при любом раскладе.

      Удалить
    9. Да, так и есть. Примерно O(1) только лишь потому, что Hash % Length могут у нескольких элементов совпасть. Соответственно, если задать емкость, близкую к действительности, то средняя сложность будет O(1).

      Удалить
    10. Эх, коряво написал :-) Имел ввиду, что будет очень близко к O(1). Насколько - зависит от Hash % Length.

      Удалить