Есть маленький массив флоатов, скажем, 15 значений, не больше. Надо очень быстро выбрать из него все значения, которые отличаются друг от друга на величину не более некого лимита, скажем, не более 5% и усреднить их, остальные отбросить. Первое, что приходит в голову — отсортировать, но это дорого. Может есть более изящные решения? Да, массив при этом является очередью, то есть, одна итерация добавляет новое значение и забывает старое. На каждой итерации надо определять самую мощную усредненную моду и в идеале — давать оценку ее мощности, типа если все числа в пределах процентного лимита — мощность 1.0, Половина чисел в пределах лимита — мощность 0.5. Диапазон чисел довольно большой, скажем, от 2 до 4000.

Первое, что приходит в голову — сразу построить частотную гистограмму. При удалении числа — вычитаем 1 из соответствующего значения, при добавлении — прибавляем. Так как она будет разреженной, то можно взять что-нибудь типа std::map

Здравствуйте, McSeem2, Вы писали:

MS>Есть маленький массив флоатов, скажем, 15 значений, не больше. Надо очень быстро выбрать из него все значения, которые отличаются друг от друга на величину не более некого лимита, скажем, не более 5%

От чего 5% считать? Вдруг случится так, что половина чисел будут в районе 20, а другая половина — в районе 200?

Здравствуйте, Edge, Вы писали:

E>От чего 5% считать? Вдруг случится так, что половина чисел будут в районе 20, а другая половина — в районе 200?

Требуется найти главную моду. Вот та самая половина чисел в районе 20 должна быть плюс-минус 5 процентов. Если есть две или более равнозначные моды, то можно взять первую попавшуюся. То есть напрашивается гистограмма, при помощи нее одна-две моды определяются тривиально. Но поскольку диапазон большой, числа плавающие и их мало, и надо быстро, то гистограмма не катит.

Здравствуйте, McSeem2, Вы писали:

Можно нестрогим методом. Есть массив флоатов и есть набор групп у которых сохраняется сумма и количество элементов, упорядоченных по среднему. Для каждого нового элемента находится ближайшая группа как расстояние до среднего, и если оно в 5%, то добавляется, суммируется с суммой, инкриментится количество. Для каждого удаляемого также находится ближайшая группа, вычитается из суммы, уменьшается количество. Упорядоченность средних групп нарушаться из за этого не должна, если удаляются те элементы которые были вставлены.

Здравствуйте, McSeem2, Вы писали:

MS>Есть маленький массив флоатов, скажем, 15 значений, не больше. Надо очень быстро выбрать из него все значения, которые отличаются друг от друга на величину не более некого лимита, скажем, не более 5% и усреднить их, остальные отбросить. Первое, что приходит в голову — отсортировать, но это дорого. Может есть более изящные решения? Да, массив при этом является очередью, то есть, одна итерация добавляет новое значение и забывает старое. На каждой итерации надо определять самую мощную усредненную моду и в идеале — давать оценку ее мощности, типа если все числа в пределах процентного лимита — мощность 1.0, Половина чисел в пределах лимита — мощность 0.5. Диапазон чисел довольно большой, скажем, от 2 до 4000.
Зависит от задачи.
1) Если меняется медленно, то смесь гауссиян или неравномерная гистограмма (по приходу точки тебе надо будет проверять в 99% случаев один бин).
2) Если меняется очень быстро -- что-то типа Ransaca.

Здравствуйте, McSeem2, Вы писали:

MS>Есть маленький массив флоатов, скажем, 15 значений, не больше. Надо очень быстро выбрать из него все значения, которые отличаются друг от друга на величину не более некого лимита, скажем, не более 5% и усреднить их, остальные отбросить. Первое, что приходит в голову — отсортировать, но это дорого. Может есть более изящные решения?

О процессе что-нибудь известно? Фильтр Калмана (метод максимального правдоподобия), метод наименьших квадратов не годятся?

Здравствуйте, A.Lokotkov, Вы писали:

AL>О процессе что-нибудь известно? Фильтр Калмана (метод максимального правдоподобия), метод наименьших квадратов не годятся?

Пока не очень, я его как раз исследую. Чаще всего дисперсия очень мала — все значения очень близки к среднему, но иногда попадаются плохие, которые надо отбрасывать. Бывает еще переходный процесс, когда среднее значение меняется. Может меняться резко, может плавно. С фильтром Калмана подробно не разбирался, но интуитивно кажется, что не очень подходит.

Здравствуйте, denisko, Вы писали:

D>1) Если меняется медленно, то смесь гауссиян или неравномерная гистограмма (по приходу точки тебе надо будет проверять в 99% случаев один бин).
D>2) Если меняется очень быстро -- что-то типа Ransaca.

Может быстро, может медленно. В общем, по формальным признакам, RANSAC — то что надо. Однако, поскольку числел не много, то настоящий RANSAC кажется оверкилом. Думаю, что простая кластеризация на лету должна нормально сработать.