爲了插入到嵌套列表

說我有一個嵌套列表，像這樣：爲了插入到嵌套列表

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

爲了插入到嵌套列表

回答

相關問題