在python中优化合并排序函数

Question

有什么办法优化这个合并排序功能吗？你知道吗

输入是这样一个列表：[（1，'i'），（3，'i'），（5，'i'），（8，'i'），[（2，'n'），[（4，'t'），（7，'t'），[（6，'a'），[（9，'v'），[（10，'e'）]]，输出是单词：“主动”

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

我可以想到一个优化：在内环之前同时反转del[0]和del[1]，并将list.pop(0)（an O(n) operation）更改为list.pop()（在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展平嵌套列表
• 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))