«Бегущий» средневзвешенный

Question

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

• сохраняя список и вычисляя средневзвешенному каждый раз, когда он получает доступ/изменений (мой текущий подход)
• просто следить за текущие средневзвешенные и сумму все веса и изменить вес и средневзвешенное значение для каждого действия добавления/снятия

Я бы предпочел второй вариант, но меня беспокоят «ошибки с плавающей запятой», вызванные постоянным сложение/вычитание. Каков наилучший способ справиться с этим?

Answer 1

Вот ответ, который сохраняет с плавающей точкой для хранения нарастающего итога - я думаю, что средневзвешенные требует только два текущих итогов:

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

Теперь вам нужно вычислить сумму массива N. Рассматриваем массив как полное двоичное дерево, как в heapsort, поэтому смещение 0 является корнем, 1 и 2 - его дочерними, 3 и 4 - детски en 1, 5 и 6 - дети 2 и т. д. - дети i находятся в 2i + 1 и 2i + 2.

Для каждого внутреннего узла храните сумму всех записей на уровне или ниже этого узла в дереве. Теперь, когда вы изменяете запись, вы можете пересчитать сумму значений в массиве, проработав свой путь от этой записи до корня дерева, исправляя частичные суммы, когда вы идете - это стоит вам O (log N), где N - длина массива.

Answer 2

Попробуйте сделать это целыми числами? Python bignums должен сделать рациональный аргумент для рациональных чисел (извините, уже поздно ... действительно жаль на самом деле).

Это действительно зависит от того, сколько терминов вы используете и каков ваш весовой коэффициент, как погода, вы будете испытывать большой дрейф с плавающей запятой. Вы получаете только 53 бит точности, вам может не понадобиться так много.

Если ваш весовой коэффициент меньше 1, ваша ошибка должна быть ограничена, так как вы постоянно уменьшаете ее. Скажем, ваш вес 0.6 (ужасно, потому что вы не можете представить это в двоичном формате). То есть 0.00110011... представлено как 0.0011001100110011001101 (округлено в последнем бите). Таким образом, любая ошибка, которую вы вводите из этого округления, будет затем уменьшена после повторного умножения. Ошибка в самом текущем члене будет доминировать.

Не делайте окончательного разделения, пока вам не понадобится. Еще раз учитывая 0,6 в качестве вашего веса и 10 условий, ваши весовые коэффициенты будут 99.22903012752124 на первый срок до 1 на последний срок (0.6**-t). Умножьте свой новый термин по 99.22..., добавить его к текущей сумме и вычесть срок косого из, затем разделить на 246.5725753188031 (sum([0.6**-x for x in range(0,10)])

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