为了插入到嵌套列表

说我有一个嵌套列表，像这样：为了插入到嵌套列表

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

列表当前排序（按字母顺序排列）由每个子表的中间值，我想补充的价值insert_me在嵌套列表的正确位置。为了保持字母顺序，需要在列表中添加'Bob'和'John'列表。我知道bisect通常会用于像这样的列表任务，但不明白我可以如何使用bisect作为嵌套列表。

来源

2013-03-22 user1789376

最终，如果您要执行大量插入操作，则树可能是更好的数据结构。 – mgilson 2013-03-22 19:52:40

见例如Python文档在bisect：

不像排序（）函数，它没有任何意义的平分线（）功能具有关键或逆转的论点，因为这会导致效率低下的设计（连续调用平分函数不会 “记住”以前的所有键查找）。

相反，它是更好的搜索预先计算的键的列表中找到问题的指数的纪录：

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

更新：

难道插入/开张，追加/排序，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

来源

2013-03-22 19:47:17 isedev

问题在于，每次插入*时都需要重新构建密钥，这会破坏O（logn）效率。（当然，'insert'已经是O（n）所以...这已经比你想要的更糟了......） – mgilson 2013-03-22 19:49:45

但是不能每次重新构建密钥的列表只是按顺序缓存保持O（nlogn）效率？ – user1789376 2013-03-22 19:55:29

您可以随后使用bisect_left插入到键中以及... so 2O（n）。但是我同意mgilson - 如果要插入许多插入，树结构可能更适合。 – isedev 2013-03-22 19:55:42

你可以按字母顺序排列使用sorted()列表。

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

nested_list.append(insert_me) 
nested_list=sorted(nested_list, key=lambda x:x[1])

Sorted()

来源

2013-03-22 19:50:47 Jroosterman

这将会非常低效 - 在每次插入后排序列表...此外，使用'operator.getitem（1）'而不是lambda表达式更清晰（IMO）。 – isedev 2013-03-22 20:00:38

的确如此，我确实考虑过这一点。然而，其目的是重复将新的子列表插入到嵌套列表中，并且必须在每次插入后对列表进行排序，这会严重影响效率。 – user1789376 2013-03-22 20:01:16

是的，它可能会有点麻烦。如果只在需要查看列表内容时才会更好。 – Jroosterman 2013-03-22 20:02:54

我会用一个heap的专业化您的问题。从this answer采用堆类，你的代码将是：

import heapq 

class MyHeap(object): 
    def __init__(self, initial=None, key=lambda x:x): 
     self.key = key 
     if initial: 
      self._data = [(key(item), item) for item in initial] 
      heapq.heapify(self._data) 
     else: 
      self._data = [] 

    def push(self, item): 
     heapq.heappush(self._data, (self.key(item), item)) 

    def pop(self): 
     return heapq.heappop(self._data)[1] 

h = MyHeap([[123,'Aaron','CA'],[124,'Bob','WY'],[125,'John','TX']], key=lambda x:x[1]) 
h.push([122,'George','AL']) 
for _ in xrange(4): 
    print h.pop()

您使用push添加会以相对于第二个元素（我们在构造函数中的参数key=lambda x:x[1]控制）每个列表。您通过呼叫pop逐个获取元素。

来源

2013-03-22 20:05:16 halex

+1为基于树的方法 – isedev 2013-03-22 20:09:53

为了插入到嵌套列表

回答

相关问题