Есть ли хороший алгоритм для проверки изменений данных за определенный период времени?

Question

У нас есть около 7 тыс. Финансовых продуктов, цены закрытия которых теоретически должны двигаться вверх и вниз в пределах определенного процентного диапазона в течение определенного периода времени (например, в течение одной недели или месяца).

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

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

Существуют ли какие-либо установленные алгоритмы, позволяющие сделать это за разумное время вычислений?

Answer 1

Нет никакого способа сделать это, не глядя на каждый день.

Предположим, что данные выглядят так:

oooo0oooo

С этим однодневным шипом посередине. Вы не поймете это, если не проверите день, когда произошел всплеск - другими словами, вы должны проверять каждый день.

Answer 2

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

Answer 3

Если вы можете добавить данные в kdb (т. Е. Вы не ограничены доступом для чтения), вы можете рассмотреть возможность добавления «количества дней с момента последнего изменения цены» в качестве нового набора данных (т. Е. Одно число на финансовый инструмент).Затем ежедневное задание будет получать сегодняшнюю и вчерашнюю отметку и обновлять сохраненные числа.Точно так же вы можете поддерживать недавние (в прошлом месяце, в прошлом году) максимумы и минимумы в kdb.Вам нужно будет выполнить задание по большому набору данных для первоначального сложения значений, но тогда ваши ежедневные обновления будут включать гораздо меньше данных.

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

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

РЕДАКТИРОВАТЬ

Я бы исследовал usng kdb + / Q дляреализовать обработку сигналов, а не извлекать необработанные данные в приложение Java.Как вы говорите, он очень эффективен.

Answer 4

Вы можете сделать это, если вы можете отслеживать минимальное и максимальное значение цены в течение временного интервала - это предполагает, что временной интервал не изменяется постоянно. Один из способов отслеживания минимальных и максимальных значений изменяющегося набора предметов - две кучи, помещенные «спина к спине» - вы можете сохранить это и некоторые указатели, необходимые для поиска и удаления старых предметов в одном или двух массивах в вашем магазине. , Идея поместить две кучи спиной к спине содержится в книге Кнута «Искусство компьютерного программирования», том 3, как упражнение 31, раздел 5.2.3. Кнут называет такого рода зверя приоритетной очередью, и это, похоже, доступно для поиска. Мин и макс доступны по постоянной стоимости. Стоимость его изменения при получении новой цены равна log n, где n - количество сохраненных элементов.