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

Question

我有一个已经按键 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

因为a insertion in a list is in O(n)反正再聪明的bisect算法也没什么用，所以可以简单的循环list找到应该插入的位置，然后插入。类似于：

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

我建议将您的字典更改为 class，重载比较运算符，然后使用 bisect.insort()。我不建议遍历所有项目以找到其他答复中建议的插入位置。从理论上讲，复杂度仍然是 O(n)，但是，搜索项目花费的时间比插入新元素要长得多。我想插入只会做一些内存复制，而对于搜索你必须比较每一个元素。

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

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

Python: insert new element into sorted list of dictionaries

python-2.7

sorting

dictionary

python-2.6