Минимум и максимум из последних 1000 значений изменяющегося списка

Question

Я создаю итерационный алгоритм (метод Монте-Карло). Алгоритм возвращает значение на каждой итерации, создавая поток значений.

Мне нужно проанализировать эти значения и остановить алгоритм, когда, скажем, 1000 возвращенные значения не соответствуют некоторым epsilon.

Я решил реализовать вычисление max и min значений последних 1000 значений, а затем вычислить error по этой формуле (max-min)/min и сравнить с epsilon: error<=epsilon , И если это условие выполнено, остановите итерации и верните результат.

1. Первая заяц-идея заключалась в том, чтобы использовать новые значения list и append, вычисляя значения max и min для последних значений 1000 после каждого добавления. .

2. Тогда я решил, что нет смысла хранить более 10 * последних значений. Итак, я вспомнил о deque. Это была очень хорошая идея, поскольку сложность добавления и удаления на обоих концах deque объекта равна O(1). Но это не решило проблему необходимости проходить все последние 1000 значений на каждой итерации для вычисления min и max.

3. Тогда я вспомнил, что есть heapq модуль . Он хранит данные таким образом, чтобы в любой момент эффективно возвращать наименьшее значение. Но мне нужны как самые маленькие, так и самые большие. Кроме того, мне нужно сохранить порядок элементов, чтобы я мог сохранить 1000 последних возвращенных элементов алгоритма, и я не вижу, как я могу добиться этого с heapq.

Имея в виду все эти мысли, я решил спросить здесь:

Как я могу решить эту задачу наиболее эффективно?

Answer 1

Если вы свободны / желаете изменить свое определение error, вы можете рассмотреть возможность использования variance вместо (max-min)/min.

Вы можете вычислить дисперсию постепенно .Правда, используя этот метод, вы не удаляете никакие значения из вашего потока - разница будет зависеть от всех значений.Ну и что?При достаточном количестве значений первые несколько не будут иметь большого значения для дисперсии, и дисперсия среднего значения, variance/n, станет маленькой, когда достаточное количество значений сгруппируется вокруг некоторого фиксированного значения.

Итак, выможете остановить, когда variance/n < epsilon.

Answer 2

В качестве уточнения отличной идеи @ unutbu, вы можете рассмотреть возможность использования экспоненциально-взвешенной движущейся дисперсии.Он может быть вычислен за O(1) времени на одно наблюдение, требует O(1) пространства и имеет преимущество в том, что автоматически уменьшает вес наблюдения по мере его старения.

В следующей статье приведены соответствующие формулы: ссылка .См. Уравнения (140) - (143) там.

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

Answer 3

Как насчет numpy?

Просто для сравнения скорости:

import numpy as np
a = range(1000)
b = np.arange(1000)

max(a) # 29.7us
b.max() # 7.29us

и вы можете писать в этот массив бесконечно:

i = 0
b = np.empty([1000]) + np.nan

your loop:
    b[i % 1000] = value
    i += 1

Значения старше, чем1000 итераций будут перезаписаны.Вы получаете минимум / максимум с np.nanmin(b) и np.nanmax(b).

Идея nan состоит в том, что вы инициализируете этот массив с 1000 нанометрами и перезаписываете их один за другим.Методы nanmin и nanmax игнорируют эти наны.

Answer 4

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

Сохраните ваши 1000элементы в очереди FIFO.Держите указатели на самые большие и самые маленькие элементы в очереди.Если один из них покидает очередь, выполните поиск в очереди нового наибольшего / наименьшего (амортизированная стоимость зависит от ваших данных).Если новое наибольшее / наименьшее значение входит в очередь, просто обновите указатель (O (1)).Предполагая, что ваши данные сходятся, это должно работать хорошо.

Answer 5

Вы можете использовать две кучи Фибоначчи .Добавление значений в O (1), удаление в O (log (n)).В своем вопросе вы уже предлагаете модуль heapq.Я не уверен, какую кучу он предоставляет, но нормальная тоже будет работать очень гладко.

Проблема, заключающаяся в том, что вы можете извлечь минимум из одной кучи, но не максимум, может быть решена путем сохранения двух куч.Поскольку я не знаю модуль heapq, вы либо можете предоставить ему свою собственную функцию сравнения, либо вы можете просто использовать -value вместо value для ключа второй кучи.

Answer 6

Создание подкласса deque, который имеет свойства minvalue и maxvalue. При добавлении или удалении записей сравнивайте их с текущими значениями min и max - тогда вам нужно всего лишь повторно сканировать деку на min / max, если удаляемое значение является текущим min или max. А при добавлении просто сравните новое значение с текущими минимальными и максимальными значениями и обновите соответственно. Это оптимизирует сканирование вашего бланка для минимальных / максимальных значений.