Сводный список словаря в бинах путем применения средневзвешенного значения в Python

Question

У меня есть список словарей, который выглядит так:

_input = [{'cumulated_quantity': 30, 'price': 7000, 'quantity': 30},
         {'cumulated_quantity': 80, 'price': 7002, 'quantity': 50},
         {'cumulated_quantity': 130, 'price': 7010, 'quantity': 50},
         {'cumulated_quantity': 330, 'price': 7050, 'quantity': 200},
         {'cumulated_quantity': 400, 'price': 7065, 'quantity': 70}]

Я бы хотел сгруппировать словарь в ячейках с количеством 100, где цена рассчитывается как средневзвешенное значение. Результат должен выглядеть так:

result = [{'cumulated_quantity': 100, 'price': 7003, 'quantity': 100},
          {'cumulated_quantity': 200, 'price': 7038, 'quantity': 100},
          {'cumulated_quantity': 300, 'price': 7050, 'quantity': 100},
          {'cumulated_quantity': 400, 'price': 7060.5, 'quantity': 100}]

Средневзвешенные значения в словаре результатов рассчитываются следующим образом:

7003 = (30*7000+50*7002+20*7010)/100 
7038 = (30*7010+70*7050)/100
7050 = 100*7050/100
7060.5 = (30*7050+70*7065)/100

Мне удалось получить результат, используя кадры данных pandas, однако их производительность слишком низкая (около 0,5 секунды). Есть ли быстрый способ сделать это в Python?

Answer 1

BIN_SIZE = 100

cum_quantity = 0
value = 0.
bin_quantity = 0
bin_value = 0
results = []

for record in _input:
    price, quantity = record['price'], record['quantity']
    while quantity:
        prior_quantity = bin_quantity
        bin_quantity = min(BIN_SIZE, bin_quantity + quantity)
        quantity_delta = bin_quantity - prior_quantity
        bin_value += quantity_delta * price
        quantity -= quantity_delta
        if bin_quantity == BIN_SIZE:
            avg_price = bin_value / float(BIN_SIZE)
            cum_quantity += BIN_SIZE
            bin_quantity = bin_value = 0  # Reset bin values.
            results.append({'cumulated_quantity': cum_quantity,
                            'price': avg_price,
                            'quantity': BIN_SIZE})


# Add stub for anything left in remaining bin (optional).
if bin_quantity:
    results.append({'cumulated_quantity': cum_quantity + bin_quantity,
                    'price': bin_value / float(bin_quantity),
                    'quantity': bin_quantity})

>>> results
[{'cumulated_quantity': 100, 'price': 7003.0, 'quantity': 100},
 {'cumulated_quantity': 200, 'price': 7038.0, 'quantity': 100},
 {'cumulated_quantity': 300, 'price': 7050.0, 'quantity': 100},
 {'cumulated_quantity': 400, 'price': 7060.5, 'quantity': 100}]

Answer 2

Не используя панд, это почти мгновенно, если вы делаете это самостоятельно:

result = []
cumulative_quantity = 0
bucket = {'price': 0.0, 'quantity': 0}
for dct in lst:
    dct_quantity = dct['quantity']  # enables non-destructive decrementing
    while dct_quantity > 0:
        if bucket['quantity'] == 100:
            bucket['cumulative_quantity'] = cumulative_quantity
            result.append(bucket)
            bucket = {'price': 0.0, 'quantity': 0}
        added_quantity = min([dct_quantity, 100 - bucket['quantity']])
        bucket['price'] = (bucket['price'] * bucket['quantity'] + dct['price'] * added_quantity) / (bucket['quantity'] + added_quantity)
        dct_quantity -= added_quantity
        bucket['quantity'] += added_quantity
        cumulative_quantity += added_quantity
if bucket['quantity'] != 0:
    bucket['cumulative_quantity'] = cumulative_quantity
    result.append(bucket)

Придает

>>> result
[{'cumulative_quantity': 100, 'price': 7003.0, 'quantity': 100}, 
 {'cumulative_quantity': 200, 'price': 7038.0, 'quantity': 100}, 
 {'cumulative_quantity': 300, 'price': 7050.0, 'quantity': 100}, 
 {'cumulative_quantity': 400, 'price': 7060.5, 'quantity': 100}]

Это может быть сделано линейно, как O (p), где p - количество частей (эквивалентно O (n * k), где k - среднее количество частей, на которые должен быть разбит каждый дикт (в вашем примере k = 1.6)).