Given a list of sell offers and a list of buy offers for an item I want to determine how many units to trade for maximum profit.
Each offer consists of a price and a maximum amount of units being traded. Offers can be partially fulfilled (i.e. if a buyer/seller wants to trade 100 units, it's ok to trade only 10). However, buy orders can have a minimum amount, which means that the buyer will buy at least this amount of units or none at all.
# sell offers sell = [Order(price=7.0, amount=120, min_amount=np.nan), Order(price=20.0, amount=80, min_amount=np.nan)] # buy offers buy = [Order(price=30.0, amount=100, min_amount=100), Order(price=15.0, amount=200, min_amount=50), Order(price=10.0, amount=20, min_amount=1)]
In this example 120 units are being sold at a price of 7.0 and 80 units at a price of 20.0. Buyers are willing to buy exactly 100 units for 30.0, between 50 and 200 units for 15.0, and up to 20 units for 10.0.
My code determines how many units to trade for maximum profit. It loops over the amount of units traded and computes the optimal buy and sell prices in each iteration. The idea is to get the item as cheaply as possible from sell orders and to sell them as expensively as possible to buy orders.
The optimal sell order price is relatively trivial to obtain. Get as many units as possible from the cheapest offer, and if that is exhausted advance to the next cheapest.
The minimum amount on buy orders makes computation of the optimal buy price more complicated. For example, when trading less than 100 units they cannot be sold as expensively than when trading more than 100 units.
This works reasonably well in the example, but is horribly inefficient when dealing with larger amounts (thousands-millions of units). I could certainly get better performance by using Cython or implementing in C, but I hope for a algorithmic optimization first.
Is there a better (faster) way to find the optimal profit?
import numpy as np import matplotlib.pyplot as plt from collections import namedtuple Order = namedtuple('Order', ['price', 'amount', 'min_amount']) if __name__ == '__main__': # sell offers sell = [Order(price=7.0, amount=120, min_amount=np.nan), Order(price=20.0, amount=80, min_amount=np.nan)] # buy offers buy = [Order(price=30.0, amount=100, min_amount=100), Order(price=15.0, amount=200, min_amount=50), Order(price=10.0, amount=20, min_amount=1)] max_n = 201 sell = np.asarray(sell) buy = np.asarray(buy) # vectorized computation of sell prices amounts = np.zeros(1 + sell.shape) prices = np.zeros(1 + sell.shape) amounts[1:] = np.cumsum(sell[:, 1]) prices[1:] = np.cumsum(sell[:, 1] * sell[:, 0]) sellprices = np.interp(np.arange(max_n), amounts, prices) # performance hog: computation of buy prices buyprices =  for n in range(max_n): price = 0 remaining = n for unit_price, amount, min_amount in buy: if remaining < min_amount: continue if remaining > amount: remaining -= amount price += amount * unit_price else: price += remaining * unit_price break buyprices.append(price) sellprices = np.array(sellprices) buyprices = np.array(buyprices) profits = buyprices - sellprices k = np.argmax(profits) plt.plot(sellprices, 'r', label='sell offers') plt.plot(buyprices, 'b', label='buy offers') plt.plot(profits, 'k', label='profit') plt.plot(k, profits[k], 'ko', label='optimum') plt.legend(loc='best') plt.xlabel('amount traded') plt.ylabel('price') plt.show()