python-3.x - 列表和字典：哪个更快

问题描述

我有以下代码通过交换元素对来对列表进行排序：

# Complete the minimumSwaps function below.
def minimumSwaps(arr):
    counter = 0
    val_2_indx = {val: arr.index(val) for val in arr}
    for indx, x in enumerate(arr):
        if x != indx+1:
            arr[indx] = indx+1
            s_indx = val_2_indx[indx+1]
            arr[s_indx] = x

            val_2_indx[indx+1] = indx
            val_2_indx[x] = s_indx
            counter += 1
    return counter

def minimumSwaps(arr):
    temp = [0] * (len(arr) + 1)
    for pos, val in enumerate(arr):
        temp[val] = pos
    swaps = 0
    for i in range(len(arr)):
        if arr[i] != i+1:
            swaps += 1
            t = arr[i]
            arr[i] = i+1
            arr[temp[i+1]] = t
            temp[t] = temp[i+1]
            temp[i+1] = i
    return swaps

第二个函数比第一个函数工作得快得多。但是，有人告诉我字典比列表快。这是什么原因？

标签： python-3.x

列表是一种数据结构，字典是一种数据结构。说一个比另一个“快”是没有意义的，就像你说一个苹果比一个橙子快一样。一个可能会长得更快，你可能会更快地吃掉另一个，当你放下它们时，它们可能会以相同的速度落到地上。不是水果更快，而是你用它做什么。

如果您的问题是您有一个字符串序列，并且您想知道给定字符串在序列中的位置，请考虑以下选项：

您可以将序列存储为列表。使用该方法查找给定字符串的位置.index需要线性搜索，在 O(n) 时间内遍历列表。
您可以将字典映射字符串存储到它们的位置。查找给定字符串的位置需要在 O(1) 时间内在字典中查找。

所以使用字典解决这个问题会更快。但还要注意，在您的第一个函数中，您正在使用列表的.index方法构建字典 - 这意味着在 O(n) 时间内进行 n 次线性搜索，在 O(n^2) 时间内构建字典，因为您使用的是列表对于某些东西列表很慢。如果您在不进行线性搜索的情况下构建字典，则将花费 O(n) 时间：

    val_2_indx = { val: i for i, val in enumerate(arr) }

但现在考虑一个不同的问题。你有一个数字序列，它们恰好是按某种顺序从 1 到 n 的数字。您希望能够在序列中查找数字的位置：

您可以将序列存储为列表。找到给定数字的位置需要在 O(n) 时间内再次进行线性搜索。
您可以像以前一样将它们存储在字典中，并在 O(1) 时间内进行查找。
您可以将逆序列存储在列表中，以便lst[i]保存原始序列中值的位置。i这是有效的，因为每个排列都是可逆的。现在获得的位置i是一个简单的列表访问，在 O(1) 时间内。

这是一个不同的问题，因此可能需要不同的时间来解决。在这种情况下，列表和字典都允许在 O(1) 时间内得到解决方案，但事实证明使用列表更有效。在字典中按键获取比在列表中按索引获取更长的常数时间，因为在字典中按键获取需要计算散列，然后探测数组以找到正确的索引。（从列表中获取只需要访问已知索引处的数组。）

第二个问题是您的第二个功能中的一个。请参阅此部分：

    temp = [0] * (len(arr) + 1)
    for pos, val in enumerate(arr):
        temp[val] = pos

这将创建一个列表temp，temp[val] = pos无论何时arr[pos] == val。这意味着列表temp是的逆排列arr。在后面的代码中，temp仅用于通过索引获取这些位置，这是一个 O(1) 操作，并且恰好比在字典中查找键更快。

python-3.x - 列表和字典：哪个更快

问题描述

解决方案

推荐阅读