python - 按顺序插入嵌套列表

Question

假设我有一个这样的嵌套列表:

nested_list=[[123,'Aaron','CA'],[124,'Bob','WY'],[125,'John','TX']]
insert_me=[122,'George','AL']

列表当前按每个子列表的中间值排序(按字母顺序)，我想将值 insert_me 添加到嵌套列表中的正确位置。为了保持字母顺序，需要在包含“Bob”和“John”的列表之间添加它。我知道 bisect 通常会用于这样的列表任务，但不明白我如何将 bisect 用于这样的嵌套列表。

Answer 1

参见 bisect 的 Python 文档中的示例:

Unlike the sorted() function, it does not make sense for the bisect() functions to have key or reversed arguments because that would lead to an inefficient design (successive calls to bisect functions would not “remember” all of the previous key lookups).

Instead, it is better to search a list of precomputed keys to find the index of the record in question:

>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
>>> data.sort(key=lambda r: r[1])
>>> keys = [r[1] for r in data]         # precomputed list of keys
>>> data[bisect_left(keys, 0)]
('black', 0)
>>> data[bisect_left(keys, 1)]
('blue', 1)
>>> data[bisect_left(keys, 5)]
('red', 5)
>>> data[bisect_left(keys, 8)]
('yellow', 8)

所以在你的情况下:

nested_list = [[123,'Aaron','CA'],[124,'Bob','WY'],[125,'John','TX']]
insert_me = [122,'George','AL']                                
keys = [r[1] for r in nested_list]
nested_list.insert(bisect.bisect_left(keys,insert_me[1]),insert_me)
[[123, 'Aaron', 'CA'],
 [124, 'Bob', 'WY'],
 [122, 'George', 'AL'],
 [125, 'John', 'TX']]

为避免每次都重建keys，将新值也插入keys:

keys.insert(bisect_left(keys,insert_me[1]),insert_me[1])

---

更新:

在 insert/bisect、append/sorted 和 heapq 解决方案之间做了一些性能比较:

# elements  heapq   insert/bisect  append/sorted
10,000      0.01s   0.08s           2.43s         
20,000      0.03s   0.28s          10.06s
30,000      0.04s   0.60s          22.81s