Самый быстрый способ разделить перекрывающиеся диапазоны дат - PullRequest
Новая
       72

Самый быстрый способ разделить перекрывающиеся диапазоны дат

9 голосов
/ 19 апреля 2011

У меня есть данные диапазона дат в таблице БД SQL, в которой есть три (только соответствующие) столбца:

  • ID (внутренний идентификатор)
  • RangeFrom (только дата)
  • RangeTo (только дата)

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

Условия

  1. Каждая запись с более высоким ID (более новая запись) имеет приоритет над более старыми записями, которые могут перекрываться (полностью или частично)
  2. Диапазоны не менее 1 дня (RangeFrom и RangeTo отличаются на один день)

Таким образом, для данного диапазона дат (не более 5 лет) мне нужно

  1. получить все записи диапазона, попадающие в этот диапазон (полностью или частично)
  2. разбить эти перекрытия на непересекающиеся диапазоны
  3. вернуть эти новые не перекрывающиеся диапазоны

Мой взгляд на это

Поскольку существует много сложных данных, связанных с этими диапазонами (много соединений и т. Д. И т. Д.), И поскольку мощность процессора + памяти намного более эффективна, чем у механизма SQL DB, я решил вместо этого загружать перекрывающиеся данные из DB в мой уровень данных и делать диапазон измельчения / расщепления в памяти. Это дает мне гораздо больше гибкости, а также скорости с точки зрения разработки и исполнения.

Если вы считаете, что это лучше обрабатывать в БД, дайте мне знать.

Вопрос

Я хотел бы написать самый быстрый и, если это вообще возможно, алгоритм преобразования не голодных ресурсов. Поскольку я получаю множество этих записей, и они относятся к разным пользователям, я должен запустить этот алгоритм для каждого пользователя и его набора данных перекрывающихся диапазонов.

Каков наиболее эффективный (быстрый и не требующий ресурсов) способ разделения этих перекрывающихся диапазонов?

Пример данных

У меня есть записи от ID=1 до ID=5, которые визуально перекрываются таким образом (даты на самом деле не имеют значения, я могу лучше показать эти совпадения следующим образом): 

       6666666666666
                44444444444444444444444444         5555555555
          2222222222222            333333333333333333333            7777777
11111111111111111111111111111111111111111111111111111111111111111111

Результат должен выглядеть следующим образом: 

111111166666666666664444444444444444444444333333333555555555511111117777777

Результат на самом деле выглядит так, как если бы мы смотрели на эти перекрытия сверху, а затем получали идентификаторы, которые мы видим из этого вид сверху.

Результат фактически преобразуется в новые записи диапазона, поэтому старые идентификаторы становятся неактуальными. Но будут использоваться их значения RangeFrom и RangeTo (вместе со всеми связанными данными): 

111111122222222222223333333333333333333333444444444555555555566666667777777

Это, конечно, только пример перекрывающихся диапазонов. Это может быть что угодно от 0 записей до X для любого заданного диапазона дат. И как мы видим, диапазон ID = 2 полностью перезаписан на 4 и 6, поэтому он полностью устарел.

Ответы [ 4 ]

4 голосов
/ 19 апреля 2011

Как насчет массива обнуляемых целых чисел

У меня возникла собственная идея:

  1. для заданного диапазона дат, который я бы создал вмассив памяти целых чисел с таким количеством элементов, сколько дней в диапазоне.

  2. заполнить массив значениями null.Все они.

  3. упорядочить записи по идентификатору в обратном порядке

  4. сгладить перекрывающиеся диапазоны путем перебора упорядоченных записей и выполнить следующие действия для каждого элемента:

    1. получить элемент
    2. вычислить начальное и конечное смещение для массива (разность дней)
    3. установить все значения массива между этими двумя смещениями в ID элемента, но только когда значениеis null
    4. переходите к шагу 4.1

  5. в итоге вы получите массив сглаженных диапазонов и заполненный идентификаторами записей

  6. создать новый набор записей и создавать каждую новую запись при изменении идентификатора в массиве.Каждая запись должна использовать данные, связанные с идентификатором записи, как установлено в массиве

  7. Повторить все это для следующего человека и его набора перекрывающихся диапазонов (не забудьте повторно использовать тот же массив),= вернуться к шагу 2.

И это все в принципе.

Для диапазона дат на 10 лет требуется массив прибл.3650 целых чисел, которые, как мне кажется, занимают довольно мало места в памяти (каждое целое занимает 4 байта, но я не знаю, сколько места занимает целое число, которое может иметь значения int и bool, но давайте предположим, что 8 байтов составляют3650 * 8 = 28,52к) и может легко и довольно быстро манипулировать в памяти.Так как я не сохраняю диапазоны дат, расщепление или что-то подобное, это всего лишь операции присваивания с условием if, которое проверяет, было ли уже установлено значение.

10-летний диапазон дат является редким преувеличением.75% диапазонов дат будут в течение 3 месяцев или четверти года (90 дней * 8 байт = 720 байт), а 99% будут попадать в диапазон целого года (365 * 8 = 2920 байт = 2,85 тыс.)

Я считаю, что этот алгоритм более чем уместен для сглаживания перекрывающихся диапазонов дат.

Чтобы уменьшить объем памяти, я мог бы использовать int вместо int? и установить -1 вместо null.

Возможность преждевременного прерывания цикла итерации

Я мог бы также вести подсчет дней, которые не установлены, и когда он достигнет 0, я могу легко разорвать цикл, потому что все остальные диапазоныполностью перекрываются, следовательно, они не будут устанавливать больше значений в массиве.Так что это даже немного ускорит процесс, когда у меня будет много записей диапазона (что будет довольно редко).

2 голосов
/ 09 июня 2011

Бесплатная библиотека периодов времени для .NET включает в себя инструмент TimePeriodIntersector , который пересекает различные перекрывающиеся временные диапазоны.

Алгоритм использует временную шкалу и перечисляет все моменты в пределах временного диапазона (считая начальную / конечную точки за момент): 

// ----------------------------------------------------------------------
public void TimePeriodIntersectorSample()
{
  TimePeriodCollection periods = new TimePeriodCollection();

  periods.Add( new TimeRange( new DateTime( 2011, 3, 01 ), new DateTime( 2011, 3, 10 ) ) );
  periods.Add( new TimeRange( new DateTime( 2011, 3, 05 ), new DateTime( 2011, 3, 15 ) ) );
  periods.Add( new TimeRange( new DateTime( 2011, 3, 12 ), new DateTime( 2011, 3, 18 ) ) );

  periods.Add( new TimeRange( new DateTime( 2011, 3, 20 ), new DateTime( 2011, 3, 24 ) ) );
  periods.Add( new TimeRange( new DateTime( 2011, 3, 22 ), new DateTime( 2011, 3, 28 ) ) );
  periods.Add( new TimeRange( new DateTime( 2011, 3, 24 ), new DateTime( 2011, 3, 26 ) ) );

  TimePeriodIntersector<TimeRange> periodIntersector =
                    new TimePeriodIntersector<TimeRange>();
  // calculate intersection periods; do not combine the resulting time periods
  ITimePeriodCollection intersectedPeriods = periodIntersector.IntersectPeriods( periods, false );

  foreach ( ITimePeriod intersectedPeriod in intersectedPeriods )
  {
    Console.WriteLine( "Intersected Period: " + intersectedPeriod );
  }
  // > Intersected Period: 05.03.2011 - 10.03.2011 | 5.00:00
  // > Intersected Period: 12.03.2011 - 15.03.2011 | 3.00:00
  // > Intersected Period: 22.03.2011 - 24.03.2011 | 2.00:00
  // > Intersected Period: 24.03.2011 - 26.03.2011 | 2.00:00
} // TimePeriodIntersectorSample

Отображение идентификатора должно быть легкой задачей.

1 голос
/ 19 апреля 2011

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

  • преобразовать отображение таблицы из [ID-> диапазон] - [дата-> список идентификаторов].

(сортировка по дате, каждая дата - неважно, начало или конец, является началом диапазона времени, достигающего до следующей даты.) Чтобы ваша таблица выглядела следующим образом: 

        |666|666666|6666|
        |   |      |4444|444|444444444444|4444444|         |55555|55555|
        |   |222222|2222|222|            |3333333|333333333|33333|     |       |7777777
 1111111|111|111111|1111|111|111111111111|1111111|111111111|11111|11111|1111111|

 1234567|890|123456|7890|123|4


 1 -> 1
 8 -> 1,6
 11 -> 6,2,1
 17 -> 6,4,2,1
 21 -> 4,2,1
 24 -> 4,1
 ...
  • выберите самый большой элемент в каждом списке
  • объедините следующие записи с одинаковым наибольшим значением.

Поскольку в вашей окончательной базе данных у вас будут дубликаты идентификаторов (в вашем примере «1» будет разделен на два сегмента), в конце концов предпочтительным будет сохранение базы данных в формате date-> ID, а не в диапазоне ID->.

Теперь для очевидной оптимизации - конечно, не храните список идентификаторов с каждой записью даты.Просто заполните таблицу date-> ID пустыми идентификаторами, и, заполняя ее окончательными записями, замените значение самой большой найденной записью:

  • создайте таблицу всех записей даты, [date ->ID]
  • для каждой записи в исходной таблице:
    • выберите даты в диапазоне от-до,
    • , если любая из них имеет значение идентификатора, равное нулю или ниже, чем текущий проверенный идентификатор записи,заполните текущим идентификатором.
  • Затем объедините - если следующая запись имеет тот же идентификатор, что и предыдущая, удалите следующую.
  • в конце вы можете захотеть немного денормализоватьзамените извлечение двух последовательных записей для диапазона с [date -> ID, length] или [date -> ID, end_date]

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

0 голосов
/ 19 апреля 2011

Эффективно, вы хотите сложить данные и выбрать максимум из стека.Мне приходилось реализовывать что-то похожее на это раньше, и подход, который мы использовали, который дал нам немного больше гибкости, чем вам требуется, поэтому может быть неуместным сделать это:

Есть объект для управления записямии добавьте каждую запись к этому объекту.при добавлении записи создайте новый диапазон дат и свяжите значение записи с диапазоном.Затем проверьте, перекрывает ли диапазон какой-либо другой существующий диапазон.Если он перекрывается, то создайте новый диапазон для каждого перекрытия и свяжите все значения на обоих / всех (в зависимости от того, делаете ли вы это при добавлении каждого диапазона или за один проход) перекрывающихся диапазонов с новым диапазоном.,Это можно сделать либо при добавлении данных, либо за один проход после добавления всех данных.

В конце у вас есть объект, который содержит уникальные диапазоны, с каждым из которых связан набор значений.с этим, немного как ваша картина выше.

       |666|666666|6666|
       |   |      |4444|444|444444444444|4444444|         |55555|55555|
       |   |222222|2222|222|            |3333333|333333333|33333|     |       |7777777
1111111|111|111111|1111|111|111111111111|1111111|111111111|11111|11111|1111111|

Затем можно предоставить классу функцию выравнивания (возможно, с использованием шаблона стратегии), которая преобразует уникальные диапазоны с коллекциями значений в уникальные диапазоны с одним значением, что, очевидно, объединит диапазоны, которыев конечном итоге с тем же значением.

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

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

...