order-matching-engine icon indicating copy to clipboard operation
order-matching-engine copied to clipboard

Use sorted dict for orders

Open ridulfo opened this issue 5 years ago • 0 comments

By using a sorted dictionary the same sorted quality would exist, but with the added benefit of being able to cancel an order in O(log(n)) (sortedcontainers have that time complexity for deletion for some reason...) From http://www.grantjenks.com/docs/sortedcontainers/_modules/sortedcontainers/sorteddict.html

def __delitem__(self, key):
        """Remove item from sorted dict identified by `key`.

        ``sd.__delitem__(key)`` <==> ``del sd[key]``

        Runtime complexity: `O(log(n))` -- approximate.

        >>> sd = SortedDict({'a': 1, 'b': 2, 'c': 3})
        >>> del sd['b']
        >>> sd
        SortedDict({'a': 1, 'c': 3})
        >>> del sd['z']
        Traceback (most recent call last):
          ...
        KeyError: 'z'

        :param key: `key` for item lookup
        :raises KeyError: if key not found

        """
        self._dict_delitem(key)
        self._list_remove(key)

Currently I believe it is O(nLog(n)):

for order in self.bids:
   if incomingOrder.order_id == order.order_id:
      self.bids.discard(order)
      break

ridulfo avatar Mar 24 '20 06:03 ridulfo