Python列表和字典优化

Question

我参加了几次黑客马拉松。我开始明白写代码并不足够，还需要优化代码。这就带来了我的问题。以下是我遇到的两个问题。

def pairsum(numbers, k)
    """Write a function that returns two values in numbers whose sum is K"""
    for i, j in numbers:
        if i != j:
            if i+j == k
                return i, j

我写了这个函数。但我在优化方面遇到了困难。

下一个问题。

string = "ksjdkajsdkajksjdalsdjaksda"

def dedup(string):
    """ write a function to remove duplicates in the variable string"""
    output = []
    for i in string:
        if i not in output:
            output.append(i)

这是我写的两个非常简单的程序。但是在优化后，我卡住了。更多关于此问题的信息，当我们优化代码时，复杂度如何降低？任何指针都将有所帮助。提前致谢。

- user2459905

---

你能告诉我你对复杂性分析的了解吗？然后我会尽力补充一下。 - 2rs2ts

谢谢！我理解，如果列表需要被访问一次，那么复杂度是O(n)，如果需要两次迭代，那么复杂度就是O(n^2)。我对编程还很陌生。 - user2459905

基本上就是这样。O()符号表示“最坏情况”。如果你要在“abcdefg”中找到“g”，如果你从开头开始，那么需要7次检查，即该字符串的长度。复杂度也适用于内存 - 如果我告诉你要反转“abcdefg”，你可能会倒序迭代字符串并将每个字符附加到一个新字符串中，但这将在内存中占用O(n)（线性增长），因为你复制了一次字符串...每次复制都会增加n（字节）的内存。原地完成则是O(1)（常数空间），因为你不会进行任何复制。 - 2rs2ts

让我来给你一些代码优化建议并尝试解释它们，但我鼓励你使用像timeit这样的模块来衡量性能。 - 2rs2ts

理论上，我完全理解。但你能否展示一下在最坏情况下如何优化上述代码？太棒了！ - user2459905

Answer 1

了解最有效的Python习惯用法以及设计可以减少迭代次数并提早得出答案的代码是优化的重要部分。以下是一些示例：

列表推导式和生成器通常是最快的：

使用简单的嵌套方法，生成器比for循环更快：

def pairsum(numbers, k):
    """Returns two unique values in numbers whose sum is k"""
    return next((i, j) for i in numbers for j in numbers if i+j == k and i != j)

这个方法可能平均更快，因为它最多只进行一次迭代，并且只有在 k-i！=i 时才检查可能的结果是否 在numbers中：

def pairsum(numbers, k):
    """Returns two unique values in numbers whose sum is k"""
    return next((k-i, i) for i in numbers if k-i != i and k-i in numbers)

输出：

>>> pairsum([1,2,3,4,5,6], 8)
(6, 2)

注意：由于文档字符串未提及元组，我假设数字是一个平面列表，并且这使问题更加困难，这也是我在比赛中所期望的。

对于第二个问题，如果您要创建自己的函数而不仅仅使用“''.join(set(s))”，那么您已经接近成功了。

def dedup(s):
    """Returns a string with duplicate characters removed from string s"""
    output = ''
    for c in s:
        if c not in output:
            output += c
    return output

提示：不要使用 string 作为名称

您也可以这样做：

def dedup(s):
    for c in s:
        s = c + s.replace(c, '')
    return s

或者更快的递归版本：

def dedup(s, out=''):
    s0, s = s[0], s.replace(s[0], '')
    return dedup(s, n + s0) if s else out + s0

但对于没有大量重复字符串的情况，它的速度不如set快：

def dedup(s):
    return ''.join(set(s))

注意：set()方法不会保留其余字符的顺序，而其他方法将根据第一次出现的顺序保留顺序。

- dansalmo

Answer 2

你的第一个程序有点模糊。我假设“numbers”是一些元组的列表或类似的东西？比如[(1,2), (3,4), (5,6)]? 如果是这样，从复杂性的角度来看，你的程序还不错——它是O(n)的。也许你想要更多Pythonic的解决方案？最简洁的方法是将条件合并在一起：

if i != j and i + j == k:

但这只是增加可读性。我认为它可能还会增加一个布尔运算，所以它可能不是一种优化。

我不确定你是否打算让你的程序返回相加结果为k的第一对数字，但如果你想要满足此要求的所有配对，你可以编写一个理解式：

def pairsum(numbers, k):
    return list(((i, j) for i, j in numbers if i != j and i + j == k))

在这个例子中，我使用了一个生成器推导而不是列表推导，以节省资源 - 生成器是像迭代器一样的函数，这意味着它们可以通过仅在需要时提供数据来节省内存。这被称为惰性迭代。

您还可以使用过滤器，这是一个函数，仅返回谓词返回True的集合中的元素。（也就是说，满足某个要求的元素。）

import itertools
def pairsum(numbers, k):
    return list(itertools.ifilter(lambda t: t[0] != t[1] and t[0] + t[1] == k, ((i, j) for i, j in numbers)))

但据我看来，这样做可读性较差。

---

你的第二个程序可以使用set进行优化。如果你还记得在小学或大学学过的离散数学，那么集合就是一组独特元素的集合 - 换句话说，集合没有重复的元素。

def dedup(mystring):
    return set(mystring)

寻找集合中独特元素的算法通常在时间上是O(n^2)，如果在空间上是O(1)，你可以使用二叉搜索树来降低时间复杂度为O(n log n)，这很可能是Python集合的实现方式。

您的解决方案花费了O(n^2)的时间，但也需要O(n)的空间，因为您创建了一个新列表，如果输入已经是仅包含独特元素的字符串，则可能占用相同的空间 - 并且对于字符串中的每个字符，您都会遍历输出。这本质上是O(n^2)（虽然我认为它实际上是O(n*m)，但无论如何）。希望您能理解为什么会这样。阅读二叉搜索树文章以了解如何改进代码。我不想再次重新实现...大一时太辛苦了！

- 2rs2ts

---

哦，对了，不要使用 string 作为变量名... 最后忘记训斥你了 :) - 2rs2ts

set(s) 不会返回一个字符串。你需要使用 ''.join(set(s))。 - dansalmo

@dansalmo 我在看 OP 的累加器，而不是他的文档字符串。不过已经注意到了 - 虽然因为他的模糊性我不想编辑我的答案。 - 2rs2ts

我认为OP的意思是数字应该是一个数字列表，而不是元组对的列表。 - dansalmo

我同意@dansalmo的观点 - 不过，由于他没有明确说明，所以我只能根据他的代码来判断。当然，这也是我写下自己的假设的原因！ - 2rs2ts

我认为OP本来应该从数字列表中找到数字对，但他在最初的实现中搞砸了。一个“天真”的实现因此会有一个嵌套循环（O(n^2)），他需要通过将内部循环转换为查找来优化到O(n)。 - user4815162342

Answer 3

优化的关键在于找到一种方法，使代码执行的原始步骤总数尽可能少。使用嵌套循环等控制结构的代码会快速增加所需的原始步骤数量。因此，优化通常涉及用更聪明的东西替换迭代完整列表的循环。

我不得不稍微改变未经优化的pairsum()方法，以使其可用：

def pairsum(numbers, k):
    """
    Write a function that returns two values in numbers whose sum is K
    """
    for i in numbers:
        for j in numbers:
           if i != j:
              if i+j == k:
                 return i,j

这里我们看到了两个循环，一个嵌套在另一个内部。当描述像这样的方法的时间复杂度时，我们经常说它是O(n²)。因为当传入的数字数组的长度与n成比例增长时，原始步骤的数量也成比例增长到n²。具体来说，条件被评估了len(number)**2次。

我们在这里可以做的聪明之处是以O(n log(n))的代价对数组进行预排序，这样可以通过最多一次地评估已排序数组的每个元素来找到正确答案。

def fast_pairsum(numbers, k):
    sortedints = sorted(numbers)
    low = 0
    high = len(numbers) - 1
    i = sortedints[0]
    j = sortedints[-1]
    while low < high:
        diff = i + j - k
        if diff > 0:
            # Too high, let's lower
            high -= 1
            j = sortedints[high]
        elif diff < 0:
            # Too low, let's increase.
            low += 1
            i = sortedints[low]
        else:
            # Just right
            return i, j

    raise Exception('No solution')

这些优化只有在问题规模变大时才真正开始发挥作用。在我的机器上，pairsum()和fast_pairsum()之间的平衡点是包含13个整数的数字数组。对于较小的数组，pairsum()更快，而对于较大的数组，fast_pairsum()更快。随着规模的增长，fast_pairsum()比未经优化的pairsum()快得多。

dedup()的聪明之处在于避免必须线性扫描输出列表以查找是否已经看到一个字符。这可以通过在集合中存储关于您已经看到哪些字符的信息来完成，其查找成本为O(log(n))，而不是常规列表的O(n)查找成本。

通过外部循环，总成本变为O(n log(n))，而不是O(n²)。

def fast_dedup(string):
    # if we didn't care about the order of the characters in the
    # returned string we could simply do
    # return set(string)

    seen = set()
    output = [] 
    seen_add = seen.add  
    output_append = output.append
    for i in string:
        if i not in seen:
            seen_add(i)
            output_append(i)

    return output

在我的机器上，dedup()和fast_dedup()之间的盈亏平衡点是字符串长度为30。

fast_dedup()方法还展示了另一个简单的优化技巧：尽可能将代码移出循环体。由于在seen和output对象中查找add()和append()成员需要时间，因此最好在循环体外部执行一次，并将对成员的引用存储在变量中，以便在循环体内重复使用。

- Rolf W. Rasmussen

---

我不确定您在哪里看到了二分查找的参与，但是我承认您的pairsum()实现更好地使用了Python惯用语，并且更加高效。 - Rolf W. Rasmussen

抱歉，我看到变量high和low后错误地将您的代码归类为二分查找。实际上，您的解决方案非常聪明，如果numbers列表已经排序，则可能是首选实现方式。（在生产环境中，出于简洁性和可读性的考虑，我可能仍然更喜欢我的版本，但这只是一个玩具示例。） - user4815162342

Answer 4

要正确地优化Python，需要找到一个好的算法来解决问题，并且使用接近该算法的Python习语。您的“pairsum”示例是一个很好的案例。首先，您的实现似乎是错误的——“numbers”很可能是一系列数字，而不是一系列数字对。因此，一个天真的实现看起来像这样：

def pairsum(numbers, k)
    """Write a function that returns two values in numbers whose sum is K"""
    for i in numbers:
        for j in numbers:
            if i != j and i + j != k:
                return i, j

这将执行n^2次迭代，其中n是numbers的长度。对于小的n来说，这不是问题，但一旦n达到几百，嵌套循环就会变得明显缓慢，一旦n达到数千，它们将变得无法使用。

优化的方法是识别内部和外部循环之间的差异：外部循环仅遍历numbers一次，并且是不可避免的。然而，内部循环仅用于验证另一个数字（必须为k-i）是否实际存在。这只是一个查找，可以通过使用字典或更好的集合来使其极快：

def pairsum(numbers, k)
    """Write a function that returns two values in numbers whose sum is K"""
    numset = set(numbers)
    for i in numbers:
        if k - i in numset:
            return i, k - i

这不仅因为我们使用了内置操作（集合查找）而比常数更快。实际上，它做的工作更少，因为set有更智能的算法来执行查找，它可以在常数时间内完成。

以类似的方式优化dedup留给读者作为练习。

- user4815162342

Answer 5

你的第一个字符串，保持顺序最容易且应该相当高效地编写为：

from collections import OrderedDict
new_string = ''.join(OrderedDict.fromkeys(old_string))

- Jon Clements