Python：将新元素插入到字典的排序列表中

Question

我有一个已经按 key 排序的字典列表id。

y = [{'id': 0, 'name': 'Frank'},
     {'id': 5, 'name': 'Hank'},
     {'id': 8, 'name': 'Fred'},
     {'id': 30, 'name': 'Jill'}]

我想在列表中插入一个新元素。

y.append({'id': 6, 'name': 'Jenkins'})

添加新元素后，如何避免按如下​​方式再次对列表进行排序？

y = sorted(y, key=lambda x: x['id'])

理想的结果是：

y = [{'id': 0, 'name': 'Frank'},
     {'id': 5, 'name': 'Hank'},
     {'id': 6, 'name': 'Jenkins'},
     {'id': 8, 'name': 'Fred'},
     {'id': 30, 'name': 'Jill'}]

编辑：

使用bisect.insort(y, {'id': 6, 'name': 'Jenkins'})仅适用于第一个键，如果字典按名称排序，则会失败。

Answer 1

由于无论如何在列表中插入都是 O(n) 的，所以任何聪明的二分算法都没有那么有用，所以你可以简单地循环列表以找到应该插入的位置，然后插入它。就像是：

new_value = {'id': 6, 'name': 'Jenkins'}

for index, value in enumerate(y):
    # Assuming y is in increasing order.
    if value['id'] > new_value['id']:
        y.insert(index, new_value)
        break

Answer 2

我建议将您的 dict 更改为类，重载比较运算符，然后使用 bisect.insort()。我不建议按照其他回复中的建议迭代所有项目来查找插入位置。从理论上讲，复杂度仍然是 O(n)，但是，搜索该项目比插入新元素花费的时间要长得多。我猜插入只会执行一些内存副本，而对于搜索，您必须比较每个元素。

从我的示例来看，迭代查找位置，然后插入大约需要 2 分钟才能完成。使用 bisect.insert() 相同的数据大约需要 10 秒。