码战中的码优化

Question

我用这个问题在codewars.com上练习python：

创建一个函数，该函数接受一个正整数，并返回可以通过重新排列其数字而形成的下一个更大的数字。例如：

12 ==> 21

513 ==> 531

2017年==> 2071

但是当我尝试我的解决方案时，它说它不够优化。

有人能说出为什么吗？

from itertools import permutations
def next_bigger(n):
    per = list(permutations(str(n)))
    result = []
    for j in per:
        result.append(int("".join(j)))
    for i in sorted(result):
        if i > n:
            return i

Answer 1

时间和内存复杂度

您的代码使用了大量的时间和内存。

使用d数字，您将大致得到d!不同的数字排列。list(permutations(str(n)))将使所有这些排列在一个列表d!元素中实现很长时间。

您获取这个列表，然后反复从列表中获取一个置换，将其转换为一个数字，将其添加到result列表的末尾，一次只生成一个元素。这可以是一个O(k^2)操作，因为在本例中，k是d!，因此具有O({d!}^2)时间复杂性。

接下来，获取这个列表，并对其进行排序，这是一个O(k \log k)操作，在本例中是O(d! \log {d!})。

最后，您接受这个排序列表，并遍历它，直到您发现第一个值大于起始值。

空间复杂性：O(d!).时间复杂度：O({d!}^2)。

删除O(k^2)

避免创建列表和重复追加操作(这可能导致对添加到的每个额外元素的所有先前元素的重新定位&副本)的最简单方法是提前分配一个大小正确的数组。

由于这是一个非常常见的操作，Python甚至为我们提供了一条捷径:列表理解。表格中的任何代码：

destination = []
for value in source:
    destination.append(func(value))

可重写为：

destination = [func(value) for value in source]

Python解释器(通过来自__length_hint__的PEP424)可以告诉您，它将分配一个新的len(container)元素列表，并可能预先分配该存储，然后开始填充该列表中的元素。

(注意: CPython、IronPython、Anaconda和其他大蛇可能在幕后实现不同的东西，可能会对附加到O(1)操作的个体进行摊销，并且可能使用__length_hint__，但重点仍然是使用列表理解总是比分配列表和一次重复添加元素更快。)

我们可以重写您的功能如下：

def next_bigger(n):
    per = list(permutations(str(n)))
    result = [int("".join(j)) for j in per]
    for i in sorted(result):
        if i > n:
            return i

空间复杂性：O(d!).时间复杂度：O(d! \log {d!})。

删除O(k \log k)

分拣是一项昂贵的操作。如果没有必要的话我们就不想做了。我们当然不需要这样做，因此我们只想要一个值。

您正在从比输入更大的值列表中寻找最小值。我们可以过滤掉所有不大于输入的值：

    candidates = [value for value in result if value > n]

然后返回所有候选人的最低人数：

    return min(candidates)

没有分类。空间复杂性：O(d!).时间复杂度：O({d!})。

消除O(d!)空间复杂度

没有理由存储任何中间结果。您可以生成排列列表，对于每个置换，将其转换回一个数字，丢弃任何不大于原始值的值，并记住传递的最小值。

def next_bigger(n):
    per = permutations(str(n))

    result = (int("".join(j)) for j in per)

    candidates = (i for i in result if i > n)

    return min(candidates)

permutations(...)是一个生成器函数，因此为per分配了一个生成器对象。我们使用这个生成器来构造我们自己的生成器，它将置换的数字转换为整数，并将该生成器存储在result中。我们使用这个生成器并创建另一个只产生比原始值更大的值的生成器，将生成器分配给candidates。

到目前为止，还没有建立任何排列。没有数字被加入，并转换为整数。也没有测试过它们是否比原始值更大。只创建了这些操作的生成器。

然后，我们将最后一个生成器传递给min(...)。min(...)函数向这个生成器请求一个值，然后请求另一个值并保存较小的值，然后请求另一个值并保存较小的值，以此类推。每一步都只保留最小的值。

没有创建列表。空间复杂性：O(1).时间复杂度：O({d!})。

可读性

我在“改进”中使用了您的变量名(n、per、result、j和i)。但是，阅读代码的人必须检查代码，以确定j是数字的元组，而i是对应的整数值。更好的变量名称对于更容易理解的代码有很大帮助。类型提示和"""docstrings"""也非常有用。

from itertools import permutations

def next_bigger(number: int) -> int:
    """
    For a positive integer, returns the next larger number that can
    be formed by rearranging its digits. For example:

    >>> next_bigger(12)
    21

    >>> next_bigger(513)
    531

    >>> next_bigger(2017)
    2071
    """

    permuted_values = (int("".join(permuted_digits))
                       for permuted_digits in permutations(str(number)))
        
    return min(value for value in permuted_values if value > number)

if __name__ == '__main__':
    import doctest
    doctest.testmod(verbose=True)

当然，对于代码战争提交，您会删除docstring，doctest，键入提示以追求速度。

--一个更好的算法

以上是对现有算法的一些小改进。正如评论和其他帖子所指出的，有一个更好的算法。

Answer 2

如果您考虑到数字和需求，您将能够找出一些数字的属性，您可以使用这些属性来提高解决方案的效率。

您的解决方案很简单，但效率不高，正如注释中所说的那样，因为例如，它创建了所有的排列并对它们进行排序。如果你有一个数字10位长，你有很多排列，你创建和排序。这被称为“蛮力”解决方案，对于许多类型的问题来说，这通常是最容易想出的，但远不是有效的。

例如，如果数字中的最后一个数字大于第二个数字，那么翻转它们就会给出一个更大的数字，这是一个很好的候选答案，甚至不用看其他数字。这是一个这样的属性，允许您减少潜在解决方案的搜索空间。现在我们可能只看一个候选人，或者如果我们研究最后三个数字，我们可能会看到大约10个排列，而不是1000's。

您需要编写的代码将更大，因为您需要对各种特殊情况进行编程。但是运行时间会更短，因为程序不需要查看所有的排列，您可以不用尝试就排除其中的大多数数字。