Блог

Итак, представьте, что у меня есть база данных с идентификаторами и меткой времени:

 ID.      Time_Stamp_Col

id1.     2017-10-16 17:54:28
id2.     2016-09-13 17:14:17
id3.     2019-10-01 19:30:37
id4.     2017-08-27 20:55:30
id5.     2017-11-19 10:56:15
id6.     2018-02-12 09:59:24
  

и произвольное количество временных меток (2 для этого примера):

 2018-02-12 09:55:29
2017-11-19 10:21:12
  

Как мне вернуть столбец, содержащий минимальный timestampdiff между Time_stamp_Col и произвольным количеством временных меток?

(Я использую python, поэтому я полностью согласен с созданием цикла для генерации повторяющегося текста в соответствии с произвольным количеством временных меток)

У меня это пока:

 SELECT 
    LEAST(DATEDIFF('2018-02-12 09:55:29',
                    b.Time_Stamp_Col),
            DATEDIFF('2017-11-19 10:21:12',
                    b.Time_Stamp_Col)),
FROM
    DataBaseInQuestion b
  

Но это так невероятно медленно. DataBaseInQuestion содержит 14 миллионов строк. Есть ли более быстрый способ?

Найдите «средний диапазон временных меток», который имеет минимальную итоговую разницу для заданного «произвольного количества временных меток».

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

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

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

Нам нужна не формула / теория, а практическое решение. Шаги:

1. У нас есть массив «временных меток данных». Допустим, это DTS [1..X], он содержит X временных меток.
2. У нас есть массив «произвольных временных меток». Допустим, это ATS[1..N], он содержит N временных меток.
3. Вычислите индексы двух медианных элементов в ATS (для массива с нечетным количеством это будет один и тот же элемент). N ₁ = (N 1) MOD 2 ; N ₂ = (N 2) MOD 2.
4. В DTS — найдите временную метку DTS [K ₁], ближайшую, но не выше ATS [N ₂], и временную метку DTS [K ₂], ближайшую, но не ниже ATS [N ₁].
5. Вычислите «суммарное расстояние» для DTS [K ₁] и DTS [K ₂].

Если суммы равны, то оба элемента и все элементы между ними (да, в этом случае они могут быть не смежными!) Являются решением.

Если они отличаются, то элемент с наименьшей суммой является решением. Кажется, что в этом случае не может быть пары решений (но вы можете проверить его соседей, чтобы убедиться).

Почему это должно работать?

Представьте, что AST содержит только 2 ts. Возьмите одно летнее время между ними, оно имеет некоторую сумму различий. Переместите его на 1 секунду влево. Расстояние до левого ATS уменьшается на 1 с, до правого — увеличивается на 1 с, а общая сумма не меняется. Переместите еще один, и снова … и сумма будет постоянной, пока мы не достигнем левого ATS. Когда мы пересечем его, сумма будет увеличиваться на 2 за каждый 1-й ход.

Теперь представьте, что у нас есть 3-элементный ATS. Снова возьмите одно летнее время и поместите его поверх среднего AST. Переместитесь влево или вправо на 1 секунду — частичная сумма для левых / правых точек не изменится, расстояние до середины увеличится на 1 секунду, общая сумма увеличится на 1 секунду. Двигайтесь дальше — когда мы пересекаем крайние точки, сумма будет увеличиваться на 3 для каждого шага…

Расширьте это до 4, 5, … элемента в ATS. Временная метка с минимальной суммой соответствует средней временной метке или среднему диапазону временных меток. Отклонение от него увеличивает сумму, пересечение метки времени увеличивает скорость увеличения.