30 000 точек данных, найдите наибольшее изменение за 2 недели

Я имею:

- 30,000 data points
- each data point is a measurement of type float
- each measurement is associated with a date
- each date has only one measurement
- no dates are without measurements
- the data comes in the form of a text file: 30,000 lines in this form:
    - YYYY-MM-DD I,F (e.g. 1977-02-08 20.74)
- measurement appearing in the source file are already sorted by date

Я нуждаюсь:

- a time-interval T with boundaries (s,e) /* start, end */
- (s - e = 14 days) the time-interval *must* be 2 weeks
- define min as the lowest value in the interval T
- define max as the greatest value in the interval T
- the chosen T needs to have the greatest distance btwn max and min of all possible Ts
- break ties among intervals T by choosing the most recent (with the greatest s value)
- the chosen T must consider all jumps in the 14 days, not just the values @ s and e
- if the overall "variance" in the interval is great but the jump 
  |max-min| is not the greatest in absolute value, T is not the right choice,
  even if it's an "exciting" interval

Я спрашиваю:

- which algorithm to employ, considering algorithms are not my specialty
- which data structure to use to keep track of the subtotals

Замечания:

- an answer in pseudo code would be preferred, "prose" is fine if pressured for time
- an answer in Python would be... splendid :)

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

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

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

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

 sarnold15 июн. 2012 г., 04:15
Это скользящее двухнедельное окно или фиксированное две недели?
 nhahtdh15 июн. 2012 г., 04:54
Сколько раз вы будете запускать алгоритм? Кажется, что лучше кэшировать результаты прошлого и обрабатывать новые данные каждый день, чем запускать их для всех данных каждый раз, когда вы хотите получить текущую максимальную разницу.
 Loren Pechtel15 июн. 2012 г., 04:20
Это O (n), если вы просто смотрите на 14 значений каждый раз. Внутренний цикл выполняется 420 000 раз. Если здесь не происходит что-то еще, это не так уж важно.
 steveha15 июн. 2012 г., 04:26
Может ли быть когда-либо более одной выборки в день, или установлено, что каждая отметка времени будет приходиться на другой день?
 Robottinosino15 июн. 2012 г., 04:36
@steveha: один образец в день - & gt; каждый день с одним образцом, без дня больше одного или ноль

Ответы на вопрос(2)



    30 000 различных упорядоченных значений данных. Заказ происходит по дате, но это не имеет значения.

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


    Принимая это очень медленно:

    1) прочитайте ваши 30000 точек данных в массив размером 30000.

    2) выделить массив размером 29 986. Назовите этот массив «Потенциальные победители».

    3) заполнить массив потенциальных победителей путем сканирования каждого 14-точечного подмножества, временно удерживая максимальное значение и минимальное значение, обнаруженное в подмножестве. Когда эти два значения находятся под рукой, сохраните (Макс-Мин) в месте индекса - в начальной точке - в Потенциальных Победителях. Не пытайтесь оптимизировать скользящие окна; увидеть ниже.

    4) Выполните линейное сканирование потенциальных победителей, сохранив значение и (что важно) индекс, в котором оно находится.

    Кстати, что вы делаете, если нет одного победителя? Если все точки данных имеют одинаковое значение, вы получите 29 986 кандидатов-победителей, все с одинаковым значением.

    5) Оптимизация: не выделяйте и не заполняйте потенциальных победителей; инициализировать Current Winner для кортежа (значение, индекс) как (0, -1). Вычислите значение каждого 14-точечного подмножества, как указано выше, но сохраните только лучшее значение среди {Current Winner, & quot; значение, которое я получаю из этого текущего подмножества & quot;}

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

Причина: хорошо, вычислите значение первых 14 баллов; получить мин и макс, и получить интервал между ними. Но подождите, нам нужны минимальные и максимальные значения для использования в следующем окне. Теперь сдвиньте окно на одну позицию вверх. Значение на левом конце исчезло; но был ли это минимум, максимум или между ними? Предположим, это была минута, а теперь ее нет. Какое значение является вторым самым низким мин? У нас нет этой информации.

    Чтобы сохранить скользящее окно, вам нужно отсортировать каждую подпоследовательность с 14 точками данных и запомнить позицию индекса всех значений. Затем, когда вы скользите, вы можете узнать, было ли значение, которое выпало слева, было либо старым min или old max, и будет ли новое значение, появившееся справа, новым min или новым max. Но это не стоит усилий.

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



Надеюсь это поможет...

 15 июн. 2012 г., 07:14
+1. По крайней мере, упомянуть вещи правильно.
 15 июн. 2012 г., 08:52
-1 за недопонимание раздвижных окон.

сохраняя два стека (возможно, это немного вводит в заблуждение, так как это, вероятно, лучше всего реализовать в виде очереди с двойным окончанием). Держать стекаminstack и стек называетсяmaxstack, Суть алгоритма в том, что minstack должен быть строгоnon-decreasing и maxstack должен быть строгоnon-increasing во всех точках слайда. Итак, как мы это делаем?

Сначала добавьте первые 14 очков в стек. Давайте определимadd(point) как:

Сделайте это для minstack:

While the point is smaller than the top element of minstack, remove the top element of minstack. Add the point to minstack.

Аналогично для maxstack:

While the new point is larger than the top element of maxstack, remove the top element of maxstack. Add the point to maxstack.

Из-за описанного выше свойства минимальные и максимальные значения первых 14 элементов должны быть нижними элементами minstack и maxstack. Теперь сдвиньте окно. Мы просто должны отметить, что если левая точка все еще "жива" в любом из стеков это теперь обязательно нижняя точка. Следовательно, это должно быть легко, просто:

slide():
    add(new_point)
    if (left_point == bottom(minstack)) remove_bottom(minstack)
    if (left_point == bottom(maxstack)) remove_bottom(maxstack)

Делайте это, пока ваши очки не будут исчерпаны. Интервал, который вы ищете, - это тот, в которомbottom(maxstack) - bottom(minstack) был крупнейшим.

Обратите внимание, что любая точка входит в minstack / maxstack не более одного раза, и каждая точка также выходит из стеков не более одного раза, поэтому для каждой точки выполняется не более 4 операций независимо от размера желаемого интервала.

РЕДАКТИРОВАТЬ: я только заметил, что вы хотели реализацию в Python. Я действительно не хотел анализировать данные, поэтому функция принимает в качестве входных данных список значений и выводит индексы (s, e) в этом массиве:

import collections

def add(x, minstack, maxstack):
    while minstack and x < minstack[-1]: minstack.pop()
    while maxstack and x > maxstack[-1]: maxstack.pop()
    minstack.append(x)
    maxstack.append(x)

def get_largest_interval(points):
    minstack = collections.deque()
    maxstack = collections.deque()

    best_diff = -1
    best_interval = None

    for index, elem in enumerate(points):
        add(elem,minstack,maxstack)
        if index >= 14:
            if minstack[0] == points[index-14]: minstack.popleft()
            if maxstack[0] == points[index-14]: maxstack.popleft()

        if index >= 13:
            this_diff = maxstack[0]-minstack[0]
            if best_diff == -1 or this_diff >= best_diff:
                best_interval = (index-13, index)
                best_diff = this_diff

    return best_interval


print get_largest_interval([0, 2, 2,2,2,2,2,2,2,2,2,2,2,2,3])
 15 июн. 2012 г., 07:17
@nhahtdh Это то, что & quot; если индекс & gt; = 14 & quot; часть существует, она удаляет самую левую точку в окне, если она все еще находится в стеке.
 15 июн. 2012 г., 07:12
Кажется, что когда x наименьшее, x будет оставаться в minstack навсегда, что неверно, так как мы рассматриваем только окна в 14 дней.
 15 июн. 2012 г., 07:30
кажется, что currmin может выйти из-под контроля. Вероятно, вы должны вытолкнуть стек вместо того, чтобы увеличивать его. Подумав немного, общая идея кажется мне подходящей.
 15 июн. 2012 г., 07:33
@nhahtdh имеет смысл, исправлено.

Ваш ответ на вопрос