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

Question

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

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

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

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

Answer 1

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

Answer 2

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

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

oooo0oooo

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

Answer 3

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

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

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

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

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

Answer 4

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