Оконный поиск top-k элементов

[Mihaylo]

Пусть есть последовательность вещественных чисел от 0 до 1 длины $n \geqslant 2$.

Алгоритм пробегается по последовательности окном шириной $w \geqslant 2, w \leqslant n$ и с шагом $s \geqslant 1, s \leqslant w$ и находит в каждом окне первые $k \geqslant 1, k \leqslant w$ из наибольших значений (top-k значения). Ещё есть параметр паддинга $p \geqslant 0, p \leqslant w - s$, который определяет величину расширения последовательности в конце, а именно: к концу последовательности добавляется $p$ дополнительных значений, которые просто повторяют последнее значение последовательности.

Нужно установить какие-то отношения между параметрами $n$, $w$, $s$, $k$, $p$, чтобы обеспечить разнообразие выходных значений.

Задача открытая, то есть точной формулировки нет. В общем плохо, если в соседних окнах top-k значения повторяются почти полным составом. Что такое "разнообразие выходных значений" - это неясное нечто.

P.S. Можно считать для определённости распределение вероятностей равномерным или нормальным.

[slavav]

Сделайте $s$ сравнимым с $w$. Для маленьких $s$ можно доказать отсутствие разнообразия в каком-то смысле. Других критериев не вижу.

[Mihaylo]

Есть ещё одно ограничение $w \leqslant s$. Чем оно обусловлено? При $w > s$ окна будут пропускать некоторые числа, это возможная потеря важной информации. Да и при $w \approx s$ не будут складываться некоторые "паттерны" - особые сочетания top-k чисел. То, что некоторое число из последовательности поучаствует в некоторых соседних окнах как число из top-k, это не есть плохо. Главное, чтобы эти сочетания top-k были разные. Я не знаю, если k=10 и только одно-два числа поменялись - это скорее плохо. Может придумать метрику для сравнения соседних окон по значениям top-k чисел?

[slavav]

Из $k$ вычтите количество чисел общих для двух выборок.

[mihaild]

Mihaylo в сообщении #1722481 писал(а):

Есть ещё одно ограничение $w \leqslant s$.

Точно в эту сторону неравенство?

[Mihaylo]

mihaild в сообщении #1722495 писал(а):

Точно в эту сторону неравенство?

Да, ошибся. В первом сообщении же правильно написал. Спасибо, что заметили.

-- 16.04.2026, 20:09 --

slavav в сообщении #1722488 писал(а):

Из $k$ вычтите количество чисел общих для двух выборок.

Всё же кажется, что первый из top-k важнее, чем последующие. Если первый сменился, например, путём сдвига второго-третьего на первое-второе место, то это сильно другое сочетание.

-- 16.04.2026, 20:17 --

Давайте уточню, что top-k чисел не упорядочиваются по возрастанию или убыванию. Это важно. Сочетание сохраняет порядок top-k чисел тот, который был в исходной последовательности. Например, 0.87, 0.76, 0.45 в первом окне, потом в следующем окне имеем 0.76, 0.45, 0.81 - это сильно другой паттерн! А если 0.87, 0.76, 0.45 сменился на 0.87, 0.76, 0.56, то это нечто близкое, малоотличимое, но в тоже время 0.87, 0.76, 0.45 и 0.87, 0.76, 0.91 - имеют существенную разницу.

-- 16.04.2026, 20:35 --

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