在Python中優化合並排序功能

優化此合併排序功能的任何想法？輸入是這樣一個列表：[[（1，'i'），（3，'i'），（5，'i'），（8，'i'）]，[（2 ，'（'，''）]，[（4，'t'），（7，'t'）]，[（6，'a'）]，[ E'）]，並且輸出就是兩個字：‘主動性’在Python中優化合並排序功能

def merge(decks): 
    while len(decks) > 1: 
     del1 = decks.pop(0) 
     del2 = decks.pop(0) 
     total = list() 
     while (len(del1) and len(del2)) > 0: 
      if del1[0] < del2[0]: 
       total.append(del1.pop(0)) 
      else: 
       total.append(del2.pop(0)) 
     total.extend(del1) 
     total.extend(del2) 
     decks.append(total) 

    word = "" 
    for kort in decks[0]: 
     word += kort[1] 
    return word

來源

2017-08-29 Sander B

'（LEN（DEL1）和len（DEL2））> 0'僥倖得來的工作BTW :) –

你可以進行一些小的優化，但是這更多的是對話題對於http：//代碼審查。 stackexchange.com –

@ Jean-FrançoisFabre你是什麼意思？ –

有一個優化我能想到的：內環前反向既del[0]和del[1]，改變list.pop(0)（an O(n) operation）到list.pop()（這是在O（1））。反轉也是O（n），但是由於你在循環內部做了pop(0)，所以它實際上是O(n^2)。

來源

2017-08-29 18:31:22 L3viathan

爲什麼要'pop（0）'有'O（n）'和'pop（）'不？ pop的C實現不包含循環 –

當從前面彈出（使用'pop（0）'）時，'list.pop'方法確實是'O（n）'。這是因爲它需要在刪除彈出的值後移動它。這發生在['list_ass_slice']（https://github.com/python/cpython/blob/631fdee6e61b4ba8ce800f827fecdd536bfb04f3/Objects/listobject.c#L580），這是'pop'實現調用的。該函數有幾個循環，但我們特別關心的是在第654行調用'memmove'，它將列表中的所有值複製到一個空格中。它可能已經被編譯器很好的優化了，但它仍然是'O（n）'。 – Blckknght

請參閱Python wiki上的[TimeComplexity]（https://wiki.python.org/moin/TimeComplexity）。 – L3viathan

更簡單的是簡單地扁平化列表，然後自然排序元組。

from itertools import chain, imap 
from operator import itemgetter 

def merge(decks): 
    return "".join(imap(itemgetter(1), 
        sorted(chain.from_iterable(decks)))

from_iterable變平嵌套列表
sorted排序的元組扁平序列在天然中，每個元組的整數第一元件
itemgetter(1)是一種有效的實施lambda x: x[1]
imap適用對sorted返回的列表的訪問函數，提取字母
"".join建立在風格所提取的字母

略少於「功能」一個新的字符串將使用列表理解，這是有道理的，因爲反正sorted返回一個列表，而不是一個更一般的迭代器。

def merge(decks): 
    return "".join(x[1] 
        for x in sorted(chain.from_iterable(decks)))

您也可以使用heapq模塊的merge函數，該函數的事實，即每個嵌套列表已經排序，而不是簡單的分揀扁平列表的優勢。

import heapq 
def merge(decks): 
    return "".join(x[1] for x in heapq.merge(*decks))

來源

2017-08-29 21:01:33 chepner

在Python中優化合並排序功能

回答

相關問題