Эффективный способ найти минимальное и максимальное значение изменяющегося набора в python

Эффективной реализацией с точки зрения сложности является обертка python set (который использует хэш-таблицу) и сохранение пары атрибутов maxElement и minElement в объекте и их соответствующее обновление при добавлении или удалении элементов. Это сохраняет каждый запрос существования, минимум и максимум O (1). Однако операция удаления будет O(n) в худшем случае с простейшей реализацией (поскольку вам нужно найти следующий за минимальным элемент, если вам случится удалить минимальный элемент, и то же самое происходит с максимальным).

При этом реализация C++ использует сбалансированное дерево поиска, которое имеет O(log n) проверок существования, операций удаления и вставки. Вы можете найти реализацию этого типа структуры данных в пакете bintrees.

Я бы не стал использовать только heapq, как это предлагается в комментариях, поскольку куча - это O (n) для проверки существования элементов (я думаю, основная точка установленной структуры данных, которая, как я полагаю, вам нужна).

Вы можете использовать две очереди приоритетов для поддержания минимального и максимального значений в наборе соответственно. К сожалению, heapq библиотеки stdlib не поддерживает удаление записей из очередь в O(log n) раза из коробки. Предлагаемый обходной путь — просто пометить записи как удаленные и отбрасывать их, когда вы выталкиваете их из очереди (хотя во многих сценариях это может быть нормально). Ниже приведен класс Python, реализующий этот подход:

from heapq import heappop, heappush

class MinMaxSet:
    def __init__(self):
        self.min_queue = []
        self.max_queue = []
        self.entries = {}  # mapping of values to entries in the queue

    def __len__(self):
        return len(self.entries)

    def add(self, val):
        if val not in self.entries:
            entry_min = [val, False]
            entry_max = [-val, False]

            heappush(self.min_queue, entry_min)
            heappush(self.max_queue, entry_max)

            self.entries[val] = entry_min, entry_max

    def delete(self, val):
        if val in self.entries:
            entry_min, entry_max = self.entries.pop(val)
            entry_min[-1] = entry_max[-1] = True  # deleted

    def get_min(self):
        while self.min_queue[0][-1]:
            heappop(self.min_queue)
        return self.min_queue[0][0]

    def get_max(self):
        while self.max_queue[0][-1]:
            heappop(self.max_queue)
        return -self.max_queue[0][0]

Демо:

>>> s = MinMaxSet()
>>> for x in [1, 5, 10, 14, 11, 14, 15, 2]:
...     s.add(x)
... 
>>> len(s)
7
>>> print(s.get_min(), s.get_max())
1 15
>>> s.delete(1)
>>> s.delete(15)
>>> print(s.get_min(), s.get_max())
2 14

С 2020 года bintrees пакетов устарели и должны быть заменены на sortedcontainers.

Пример использования:

import sortedcontainers

s = sortedcontainers.SortedList()
s.add(10)
s.add(3)
s.add(25)
s.add(8)
min = s[0]      # read min value
min = s.pop(0)  # read and remove min value
max = s[-1]     # read max value
max = s.pop()   # read and remove max value

Помимо SortedList у вас также есть SortedDict и SortedSet. Вот документация по API.

numpy min max в два раза быстрее собственного метода

import time as t
import numpy as np

def initialize():
    storage.reset()

def tick():

    array = data.btc_usd.period(250, 'close')

    t1 = t.time()

    a = min(array)
    b = max(array)

    t2 = t.time()

    c = np.min(array)
    d = np.max(array)

    t3 = t.time()

    storage.t1 = storage.get('t1', 0)
    storage.t2 = storage.get('t2', 0)
    storage.t1 += t2-t1
    storage.t2 += t3-t2


def stop():

    log('python: %.5f' % storage.t1)
    log('numpy: %.5f' % storage.t2)
    log('ticks: %s' % info.tick)

урожаи:

[2015-11-06 10:00:00] python: 0.45959
[2015-11-06 10:00:00] numpy: 0.26148
[2015-11-06 10:00:00] ticks: 7426

но я думаю, что вы ищете что-то вроде этого:

import time as t
import numpy as np

def initialize():
    storage.reset()

def tick():

    storage.closes = storage.get('closes', [])
    if info.tick == 0:
        storage.closes = [float(x) for x in data.btc_usd.period(250, 'close')]
    else:
        z = storage.closes.pop(0) #pop left
        price = float(data.btc_usd.close)
        storage.closes.append(price) #append right
    array = np.array(storage.closes)[-250:]

    # now we know 'z' just left the list and 'price' just entered
    # otherwise the array is the same as the previous example

    t1 = t.time()
    # PYTHON METHOD
    a = min(array)
    b = max(array)

    t2 = t.time()
    # NUMPY METHOD
    c = np.min(array)
    d = np.max(array)

    t3 = t.time()
    # STORAGE METHOD
    storage.e = storage.get('e', 0)
    storage.f = storage.get('f', 0)
    if info.tick == 0:
        storage.e = np.min(array)
        storage.f = np.max(array)
    else:
        if z == storage.e:
            storage.e = np.min(array)
        if z == storage.f:
            storage.f = np.max(array)
        if price < storage.e:
            storage.e = price
        if price > storage.f:
            storage.f = price

    t4 = t.time()

    storage.t1 = storage.get('t1', 0)
    storage.t2 = storage.get('t2', 0)
    storage.t3 = storage.get('t3', 0)    
    storage.t1 += t2-t1
    storage.t2 += t3-t2
    storage.t3 += t4-t3


def stop():

    log('python: %.5f'  % storage.t1)
    log('numpy: %.5f'   % storage.t2)
    log('storage: %.5f' % storage.t3)
    log('ticks: %s'     % info.tick)

урожаи:

[2015-11-06 10:00:00] python: 0.45694
[2015-11-06 10:00:00] numpy: 0.23580
[2015-11-06 10:00:00] storage: 0.16870
[2015-11-06 10:00:00] ticks: 7426

что приводит нас примерно к 1/3 нативного метода с 7500 итерациями против списка из 250