CODEWITHSUNDEEP
pythonpython-3.x
Tennis Tubbies
Tennis Tubbies

Reputation: 15

Adding to a list and sorting based on price then timestamp

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

Upvotes: 1

Views: 333

Answers (2)

Marko
Marko

Reputation: 382

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

Upvotes: 0

blhsing
blhsing

Reputation: 106768

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.

Upvotes: 1

Related Questions