添加到列表中并根据价格进行排序，然后根据时间戳进行排序。

Question

我从一个订单列表开始，每个订单都有一个价格和一个时间戳等等。列表从空开始，我可以修改、删除并插入到列表中。

列表需要始终保持按价格排序，然后按时间戳排序，因此相同价格的订单将根据收到的时间优先排序。

我只是想找个更有效率的方法

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

我看到的是均分，但它似乎不能做到这一点的关键。我正努力使my_list尽可能高效地排序

Answer 1

在不使用键函数的情况下，按键对对象进行排序的一种简单方法是按照元组顺序对对象进行排序，其中每个元组由所有相关键和对象本身组成：

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()

这一产出如下：

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)

因此，如果您使用了sort方法，那么每次插入的平均时间复杂度仅为O(n)，而不是O(n log )。

Answer 2

编辑:最好使用next访问索引

也许这样做有好处:查找第一项大于要插入的项，获取索引，并将其用于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