如何预分配包含元组的Python列表？

Question

我还在弄明白Python中的元组。如果我想创建一个元组的列表，而不能通过列表推导式来做，我应该先给这个列表分配一些空间吗？还是说我可以在过程中一个一个地添加元组？我现在的代码是：

def get_priorities(words):
    priorities = [0]*len(words)

    for idx, word in enumerate(words):

        # ...calculate priority using word...

        priorities[idx] = (word, priority)

    return set(priorities)

我应该把 [0]*len(words) 替换成 []，然后在循环中为每个项目添加一个元组吗？哪种方式更快呢？我想编译器在这两种情况下都需要重新分配存储空间。

Answer 1

一组元组其实就是一个列表。用法和处理字符串、整数或者更复杂的数据结构（比如列表、字典或对象）没有什么不同。想了解更多关于列表和列表推导式的内容（还有例子），可以看看这里。

从你给出的例子来看，你想做的是建立一个字典，里面存放单词和它们在列表中某个位置的优先级。我不太明白你为什么在完成后还要把所有东西转换成集合（因为在列表中，逻辑上不可能有两个单词在同一个位置，所以没有必要去除重复项）。

我不知道你提到的代码的具体用途，但看起来你用字典会更好，字典的键是单词，值是优先级。这样也可以避免重复（字典不允许有多个相同的键），而且在根据单词获取优先级时也会很方便。

Answer 2

你可以使用这两种方法。
如果你想用索引来操作（比如 priorities[idx] = (word, priority)），那么你必须先创建一个包含 n 个元素的列表。不过，使用空列表（priorities = []）然后用 append() 方法添加元素会显得更好一些。我觉得这两种方法在速度上没有明显的差别。
顺便提一下，这个问题和元组没有关系。你可以用这种方式来处理任何其他元素的列表。

Answer 3

我可能不太明白你具体的情况，但我觉得你不一定需要提前分配什么。你这样做是不是也能得到同样的结果呢？

return set((word, calc_priority(word)) for word in words)

（当然，前提是calc_priority()这个函数是已经定义好的）。

Answer 4

为此，我将使用来自Python网站的时间复杂度信息：https://wiki.python.org/moin/TimeComplexity

使用 append

def get_priorities(words):
    priorities = []
    for idx, word in enumerate(words):
        ...
        priorities.append(word, priority)
    return set(priorities)

这样做可以省去预先分配数组的时间，这个过程需要 O(nk) 的时间，也就是在这个例子中是 1 * len(words)，但你用追加的方式替代了这个过程，根据Python的文档，追加的平均时间复杂度是 O(1)，这应该让你的 for 循环的时间复杂度变成 O(n)，其中 n 是单词的长度。

另一方面，使用 yield 可以节省内存，避免重复读取，同时保持相同的 O(n) 复杂度（Python中的“yield”关键字有什么作用？）：

def get_priorities(words):
    for idx, word in enumerate(words):
        ...
        yield (word, priority)  

我会推荐第二种方法，因为你不需要为优先级列表分配内存，也不用担心追加的成本。不过，由于你使用了 set，我想你是想消除重复的情况？使用 set 会让你的运行时间增加一个 n，所以在第一种情况下是 O(2n)，而使用 yield 的话是 O(n)，不过 O(2n) 实际上也可以看作是 n 的运行时间。无论如何，第一种情况下分配 priorities 的成本是 O(1)，如果你把它作为一个空列表来分配的话。