3

我参加了几次黑客马拉松。我开始明白写代码是不够的。代码必须优化。这让我想到了我的问题。这是我遇到的两个问题。

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)

这是我编写的两个非常简单的程序。但在此之后我陷入了优化。更多关于这一点，当我们优化代码时，复杂性如何降低？任何指针都会有所帮助。提前致谢。

4

5 回答 5

4

了解最有效的 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)

平均而言，这可能更快，因为它最多只进行一次迭代，并且不检查可能的结果是否为in numbers，除非k-i != i：

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()不会保留剩余字符的顺序，而其他方法将保留基于第一次出现的顺序。

于 2013-06-29T00:35:01.760 回答
1

你的第一个程序有点模糊。我假设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(1)，则查找集合的唯一元素的算法通常在时间上为 O(n^2) - 如果您允许自己分配更多内存，则可以使用二叉搜索树将时间复杂度降低到 O(n log n)，这很可能是 Python 集合的实现方式。

您的解决方案花费了 O(n^2) 时间，但也花费了 O(n) 空间，因为您创建了一个新列表，如果输入已经是只有唯一元素的字符串，则该列表可以占用相同数量的空间 - 并且，对于字符串中的每个字符，您都迭代了输出。这本质上是 O(n^2)（虽然我认为它实际上是 O(n*m)，但无论如何）。我希望你明白这是为什么。阅读二叉搜索树文章，了解它如何改进您的代码。我不想再重蹈覆辙……大一那年太累了！

于 2013-06-29T00:26:14.007 回答
0

优化的关键基本上是想办法让代码做更少的工作，就需要执行的原始步骤的总数而言。使用嵌套循环之类的控制结构的代码会迅速增加所需的原始步骤的数量。因此，优化通常是用更聪明的方法替换遍历完整列表的循环。

我不得不稍微更改未优化的 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² 成正比增长。具体来说，i+j == k条件被精确地评估了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()方法还展示了另一个简单的优化技巧：将尽可能多的代码移出循环体。由于在and对象中查找add()andappend()成员需要时间，因此在循环体外部执行一次并将对成员的引用存储在循环体内部重复使用的变量中会更便宜。seenoutput

于 2013-06-29T01:02:09.307 回答
0

您的字符串一，顺序保留是最容易的，并且应该相当有效地写成：

from collections import OrderedDict
new_string = ''.join(OrderedDict.fromkeys(old_string))
于 2013-06-29T08:49:01.740 回答
0

要正确优化 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. 对于 small ns 来说这不是问题，但是一旦n进入数百个，嵌套循环就会明显变慢，一旦n进入数千个，它们就会变得无法使用。

numbers一种优化是识别内循环和外循环之间的差异：外循环恰好遍历一次，并且是不可避免的。然而，内部循环仅用于验证另一个数字（必须是k - i）是否实际存在。这只是一个查找，可以通过使用 dict 甚至更好的 set 来非常快速地进行查找：

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

这不仅通过常量更快，因为我们使用的是内置操作（设置查找）而不是 Python 编码的循环。它实际上做的工作更少，因为set它有一个更智能的查找算法，它在恒定时间内执行它。

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

于 2013-06-29T07:21:10.457 回答