Adding to a list and sorting based on price then timestamp

Question

I am starting with a list of orders, each order has a price and a timestamp amongst other things. The list starts off empty, and I can amend, remove and insert into the list.

The list needs to always remain sorted based on price and then timestamp, so orders of the same price will be given priority based on the time they were received.

I am just trying to find a more efficient way to do this

        my_list.append(order)
        my_list.sort(key=lambda k: (k.price, k.timestamp))

I was looking at bisect but it doesn't seem to be able to do this on a key. I'm trying to keep my_list sorted as efficiently as possible

Does this link provide a working implementation? [link](https://stackoverflow.com/questions/1109804/does-python-have-a-sorted-list) — Marko, Nov 26 '20 at 07:48
not really. my list is a bunch of orders. I have defined my order class, which is ID, quantity, price, timestamp — Tennis Tubbies, Nov 26 '20 at 07:59
"Always"? Will the sortedness matter for some reason between each insertion? — Karl Knechtel, Nov 26 '20 at 08:25
No, it's just price, then time. If you want 10 and I want 2, and I got there first and there's only 10 available, I get 2, and you get 8 — Tennis Tubbies, Nov 26 '20 at 08:54

blhsing · Accepted Answer · 2020-11-26T08:20:31.440

An easy approach to sorting objects by a key without using a key function is to sort the objects by a tuple order, where each tuple consists of all the relevant keys and the object itself:

import bisect
from collections import namedtuple

Order = namedtuple('Order', ('item', 'price', 'timestamp'))
orders = [
    Order('banana', 2, 5),
    Order('apple', 4, 3),
    Order('orange', 2, 4),
    Order('mango', 1, 7),
    Order('guava', 3, 1)
]
my_list = []
for count, order in enumerate(orders, 1):
    print(f'Insertion #{count}')
    bisect.insort_right(my_list, (order.price, order.timestamp, order))
    for _, _, order in my_list:
        print(order)
    print()

This outputs:

Insertion #1
Order(item='banana', price=2, timestamp=5)

Insertion #2
Order(item='banana', price=2, timestamp=5)
Order(item='apple', price=4, timestamp=3)

Insertion #3
Order(item='orange', price=2, timestamp=4)
Order(item='banana', price=2, timestamp=5)
Order(item='apple', price=4, timestamp=3)

Insertion #4
Order(item='mango', price=1, timestamp=7)
Order(item='orange', price=2, timestamp=4)
Order(item='banana', price=2, timestamp=5)
Order(item='apple', price=4, timestamp=3)

Insertion #5
Order(item='mango', price=1, timestamp=7)
Order(item='orange', price=2, timestamp=4)
Order(item='banana', price=2, timestamp=5)
Order(item='guava', price=3, timestamp=1)
Order(item='apple', price=4, timestamp=3)

So that each insertion takes only an average time complexity of O(n) as opposed to O(n log n) if you had used the sort method.

Marko · Answer 2 · 2020-11-26T11:21:48.510

Edit: better use next to get to the index

Maybe this does the trick: look for the first item greater than you want to insert, get the index, and use it for the insert:

def insert_val(lst, val):
    try:
        index = next( i for i, x in enumerate(lst) 
                  if (x.price, x.timestamp) > (val.price, val.timestamp))
    except StopIteration:      # greater item not found 
        lst.append(val)
    else:
        lst.insert(index, val) # insert val on the index of the found item

Adding to a list and sorting based on price then timestamp

2 Answers2