Pythonのマージソート関数を最適化する

Question

このマージソート関数を最適化する方法はありますか？

入力は次のようなリストです：[[（1、 'i'）、（3、 'i'）、（5、 'i'）、（8、 'i'）]、[ （9、 'v'）]、[（10、 'n'）]、[（4、 't'）、 『イニシアチブ』

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 

Answer 1

私は考えることができる1つの最適化があります：内部ループの前del[0]とdel[1]の両方を逆にしてlist.pop(0)（an O(n) operationを変更）list.pop()に（これはE '）]]、および出力が単語でありますO（1）に）。反転もO（n）ですが、ループ内でpop(0)を実行するので、実際にはO(n^2)です。

Answer 2

単純にリストを平坦化してから、タプルを自然にソートするだけです。

from itertools import chain, imap 
from operator import itemgetter 

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

• from_iterable各タプル
• itemgetter(1)の整数最初の要素は、lambda x: x[1]
• imap適用の効率的な実装であることにより、ネストされたリスト
• sortedは、自然に平坦化シーケンス内のタプルをソート平坦化sortedによって返されたリストへのアクセス関数は、文字を抽出する
• "".joinは少し少ない「機能的」なスタイルで抽出された文字

から新しい文字列を構築しますsortedではなく、より一般的なイテレータの、とにかくリストを返すので、理にかなって、リストの内包表記を使用することです。

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

はまた、各ネストされたリストは、既に単純に平らにリストをソートするのではなく、ソートされているという事実を利用するheapqモジュールのmerge機能を、使用することができます。ところで全くの運で働く0 '

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