Thread-safe algorithm to make trades based on moving window of prices

Question

Here is problem to be solved

TradingAlgorithm employs a trading algorithm which, based on the prices it receives, will return a trade to execute. The trading algorithm must implement the following interface:

public interface TradingAlgorithm {  
    Trade buildTrades(Price price);  
}  

A Price is made up of a product name and a numerical price.
A Trade is made up of a product name, a direction (buy or sell), a numerical price and a quantity.
Write an implementation of the TradingAlgorithm interface that satisfies the following:
Accepts an array of product names (String[]) at the time of construction. These are the products that can be traded. Returns a buy trade for a quantity of 1000 at the newest price, if the simple average of the last 4 prices is greater than the oldest price in that collection of 4 prices e.g. {1,2,3,4} will result in a trade, as will {4,5,6,4} but {9,4,2,1} will not. In other words a trade will be made when the simple average of a moving window of prices has an upward trend. The implementation should be thread-safe, and performant.

Here is my implementation.

public class Price {
    private String product;
    private BigDecimal price;
    // getters and setters
}

---

public class Trade {
    private String product;
    private String direction;
    private BigDecimal price;
    private Integer quantity;
    // getters and setters
}

---

public class DirectionAlgorithmImpl implements DirectionAlgorithm {

    private static final int PRICE_SAMPLES_SIZE = 4;
    private static final String DIRECTION_BUY = "buy";
    private static final String DIRECTION_SELL = "sell";
    private final Queue<BigDecimal> priceQueue = new LinkedList<>();
    private BigDecimal movingSum = BigDecimal.ZERO;
    private final Object lock = new Object();

    @Override
    public String getDirection(BigDecimal newPrice) {
        synchronized (lock) {

            priceQueue.add(newPrice);
            movingSum = movingSum.add(newPrice);

            if (priceQueue.size() > PRICE_SAMPLES_SIZE) {
                BigDecimal removedPrice = priceQueue.remove();
                BigDecimal oldestPrice = priceQueue.peek();

                movingSum = movingSum.subtract(removedPrice);
                BigDecimal sma = movingSum.divide(BigDecimal.valueOf(PRICE_SAMPLES_SIZE));

                return getDirection(sma, oldestPrice);
            } else if (priceQueue.size() == PRICE_SAMPLES_SIZE) {
                BigDecimal oldestPrice = priceQueue.peek();

                BigDecimal sma = movingSum.divide(BigDecimal.valueOf(PRICE_SAMPLES_SIZE));

                return getDirection(sma, oldestPrice);
            }

            return null;
        }
    }

    private String getDirection(BigDecimal sma, BigDecimal oldestPrice) {
        return sma.compareTo(oldestPrice) > 0 ? DIRECTION_BUY : DIRECTION_SELL;
    }

}

---

public class TradingAlgorithmImpl implements TradingAlgorithm {

    private static final Integer TRADE_QUANTITY = 1000;
    private final ConcurrentMap<String, DirectionAlgorithm> productToDirectionAlgoMap = new ConcurrentHashMap<>();

    public TradingAlgorithmImpl(String[] productNames) {
        if (productNames == null || productNames.length == 0) {
            throw new IllegalArgumentException("product names cannot be null or empty");
        }
        for (String productName : productNames) {
            productToDirectionAlgoMap.put(productName, new DirectionAlgorithmImpl());
        }
    }

    @Override
    public Trade buildTrades(Price price) {
        String product = price.getProduct();
        BigDecimal newPrice = price.getPrice();

        // time complexity: O(1)
        DirectionAlgorithm directionAlgorithm = productToDirectionAlgoMap.get(product);
        if (directionAlgorithm != null) {
            // time complexity: O(1)
            String direction = directionAlgorithm.getDirection(newPrice);
            if (direction != null) {
                return new Trade(product, direction, newPrice, TRADE_QUANTITY);
            }
        }
        return null;
    }

}

Questions

1. Is this code thread-safe?
2. Is there any way its time complexity can be improved?

Answer 1

Is this code thread-safe?

Yes.

Is there any way its time complexity can be improved?

No, the algorithmic time complexity is probably as low as can be.

Overall impression: This is pretty good code.

There are ways to make the code more performant in terms of instructions executed:

• BigDecimal.valueOf(PRICE_SAMPLES_SIZE) is recalculated each time; you can extract this into a static constant.

• BigDecimal multiplication is less involved than division. Rather than dividing the sum, multiply oldestPrice.

It could be argued that an ArrayList would perform better than a LinkedList despite this really being the LinkedList's turf. This is because we're talking about small amounts of data and a predictable amount of it (4); arraycopy-ing has good cache locality in this case, and won't take extra allocations. (*)

Code duplication? You branch on the size of priceQueue in getDirection, but the code is very similar.

Fewer than 4 elements: It is still possible to calculate an average and have an oldest pricing when the window is not full. The window can not be empty, because the relevant methods are called with a new price as parameter.

Whether this is desirable depends on the expectations of who will be evaluating the solution, but I find it helpful to limit the number of null-pointers in circulation. It also allows for some code merging.

Putting it together: Squeaking these changes into place cut wall time to about 25% in my local measurements.

@Override
public String getDirection(BigDecimal newPrice) {
    synchronized (lock) {
        priceQueue.add(newPrice);
        movingSum = movingSum.add(newPrice);

        if (priceQueue.size() > PRICE_SAMPLES_SIZE) {
            BigDecimal removedPrice = priceQueue.remove();
            movingSum = movingSum.subtract(removedPrice);
        }

        BigDecimal oldestPrice = priceQueue.peek();
        oldestPrice = oldestPrice.multiply(BIGDECIMAL_PRICE_SAMPLES_SIZE);

        return getDirection(movingSum, oldestPrice);
    }
}

---

(*) This is purely in terms of processing speed. LinkedList has the better algorithmic complexity for these operations. ArrayList has the speed advantage in these circumstances.