Re: [問題] 合併兩個List

看板Python作者uranusjr (←這人是超級笨蛋)時間13年前 (2012/10/20 18:21)推噓4(4推 0噓 1→)

留言5則, 5人參與討論串2/2 (看更多)

※ 引述《Arim (Arim5566)》之銘言： : 各位版友好 : 如果我想把兩個list合併成一個list : a=[1,2] : b=[2,5] : 可以合併成c=[1,2,2,5] : 作法是 : a.extend(b) : 但是這個要花O(n)的時間 : 或者是 : a+b : 用+號這個operator做出來的效果跟extend一模一樣 : 但是我不清楚這個operator是不是也是O(n) ? a + b 會創造出一個新的 list, 裡面包含 a 和 b 的所有元素而用 extend 則是 in-place 的, a.extend(b) 會把 b 的所有元素加入 a 中這兩個 operation 複雜度基本一樣不過我用 timeit 實測好像 + 會快一點點（Python 2.7.2, Mac OS X 10.8.2）猜測是記憶體 reallocation 的問題吧, 不是什麼有意義的差距就是了哪個比較好我想也是看狀況而定 : 如果也是O(n)的話 : 不知道有沒有O(1)的作法? : 我的想法是 : 直接用a.append(b) : 這樣就變成O(1) : 不過這樣子還要在拆兩層以上的list,感覺就麻煩了一點 : 所以想請問有沒有比較快的作法(讓所有的element都在同一層) : 謝謝如果你用 list 的話, O(n) 已經是最快的了因為需要把 b 裡面的每個 reference 都拷貝到 a 裡面當然是 O(n), 沒可能是 O(1) 的如果可以接受用 iterator 的話, 倒是可以用 itertools a = [1, 2, 3] b = [4, 5, 6] from itertools import chain c = chain.from_iterable([a,b]) for i in c: print i, # 1 2 3 4 5 6 因為只是產生 iterator, 沒有拷貝資料, 基本上是 O(1) 不過這只能用來 walkthrough, 沒辦法 random access 如果你一定要 random access, 或者可能可以做這種東西 class chain(object): def __init__(self): super(object, self).__init__() self._lists = [] def __getitem__(self, i): toBreak = False for l in self._lists: if toBreak: break elif len(l) <= i: i -= len(l) else toBreak = True return l[i] def add(self, l): self._lists.append(list(l)) 速度當然是比不上 itertools.chain, 不過比直接運算要快多了走訪和 random access 的速度都是 O(len(_lists))（和各 list 本身的長度無關） Nested lists 的遞迴跟其他 list 需要的東西就交給你自己完成了不知道有沒有現成的 module 有類似功能 -- 「我最想要的同伴嘛，首先是要笑口常開，其次是我們能永遠不會發生誤會。如果這些都能辦到的話，嗯，如果他是世界上第一流的橋手，也還不錯。」 -- 班尼多‧加羅素，前義大利藍隊成員 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.32.81.146 ※ 編輯: uranusjr 來自: 114.32.81.146 (10/20 18:26)