Я подозреваю, эта задача элементарно решается статистическими методами, но что-то не соображу как...
Суть вот в чем.
Есть набор чисел. Можно считать, что случайных. Без повторов.
И есть некое число N.
Задача состоит в том, чтобы найти число X. Такое, чтобы в диапазон [X, X+N] попало наибольшее возможное количество чисел из заданного набора.
Здравствуйте, Kerk, Вы писали:
K>Задача состоит в том, чтобы найти число X. Такое, чтобы в диапазон [X, X+N] попало наибольшее возможное количество чисел из заданного набора.
Ну так сортировка и вперед двумя итераторами. Можешь построить сглаженную гистограмму, чтобы грубо определить район поиска.
Здравствуйте, denisko, Вы писали:
D>Ну так сортировка и вперед двумя итераторами. Можешь построить сглаженную гистограмму, чтобы грубо определить район поиска.
Такое решение "в лоб" я держу в уме, конечно. Но чисел много, а производительность критична. Хочется верить, что есть какие-то другие варианты.
Здравствуйте, Kerk, Вы писали:
K>Я подозреваю, эта задача элементарно решается статистическими методами, но что-то не соображу как...
Кажется, что статистические решения хорошо работают, если вероятность попасть в около-максимум случайным выбором большая. То есть если в максимуме 1% точек, мы делаем 1000 проб, то хотя бы одна из них скорее всего попадёт (можно посчитать вероятность, не сложно). А если в максимуме 0.01% точек, то его искать уже гораздо дольше.
Чтобы из проб найти максимум надо посмотреть какое-нибудь окно, типа [X — N/2, X + N/2].
Здравствуйте, Kerk, Вы писали:
K>Я подозреваю, эта задача элементарно решается статистическими методами, но что-то не соображу как...
K>Суть вот в чем.
K>Есть набор чисел. Можно считать, что случайных. Без повторов.
Случайных равномерно? Или есть какой-то закон распределения все-таки?
K>Есть набор чисел. Можно считать, что случайных. Без повторов. K>И есть некое число N. K>Задача состоит в том, чтобы найти число X. Такое, чтобы в диапазон [X, X+N] попало наибольшее возможное количество чисел из заданного набора.
Если это стрим и мы не можем просто взять и отсортировать массив, то можно найти не точное решение — заводим массив, чем больше тем точнее ответ, далее, с помощью reservoir sampling забиваем его элементами, сортируем, с некоторым приближением получаем распределение, которое может быть использовано для решения задачи. Если массив заранее не отсортирован, то сделать быстрее чем за линейное время нельзя, нам придется пробежать по массиву хотя бы один раз.
Здравствуйте, Kerk, Вы писали:
K>Я подозреваю, эта задача элементарно решается статистическими методами, но что-то не соображу как...
K>Суть вот в чем.
K>Есть набор чисел. Можно считать, что случайных. Без повторов. K>И есть некое число N. K>Задача состоит в том, чтобы найти число X. Такое, чтобы в диапазон [X, X+N] попало наибольшее возможное количество чисел из заданного набора.
N и X — это значения или индексы?
Если значения, то X = MAX — N, где MAX — максимальное значение элементов коллекции.
Если индексы, то X = длина_коллексии — N.
Что означает "плотный диапазон"? Без прóпусков? Т.е. числа целые?
Здравствуйте, Kerk, Вы писали: K>Есть набор чисел. Можно считать, что случайных. Без повторов. K>И есть некое число N. K>Задача состоит в том, чтобы найти число X. Такое, чтобы в диапазон [X, X+N] попало наибольшее возможное количество чисел из заданного набора.
ну в случае действительно большого кол-ва чисел X можно брать любым (пока x+n влазит в диапазон, конечно)
но я так понимаю, что либо чисел мало и тогда решается в лоб, либо все-таки есть какое-то неизвестное распределение, тогда, скорее всего, стоит искать матожидание как примерную середину искомого интервала.
В общем, при прямо такой постановке задач я бы взял какое-то из средних
Здравствуйте, Kerk, Вы писали:
K>Я подозреваю, эта задача элементарно решается статистическими методами, но что-то не соображу как...
K>Суть вот в чем.
K>Есть набор чисел. Можно считать, что случайных. Без повторов. K>И есть некое число N. K>Задача состоит в том, чтобы найти число X. Такое, чтобы в диапазон [X, X+N] попало наибольшее возможное количество чисел из заданного набора.
1. Очевидно, что X будет принадлежать набору чисел, любые другие числа будут непрактичны, ибо для них всегда можно найти число из набора, которое даст большую оценку (плотность).
2. Если набор чисел отсортирован, то просто считаем плотность для каждого числа из набора чисел -> профит.
3. Если набор чисел не отсортирован, то сортируем / либо используем промежуточный результат сортировки. Например: если для набора чисел применима сортировка подсчетом — то достаточно массива подсчета совпадающих элементов. -> считаем плотность для каждого числа из набора чисел -> профит.
