时间戳

首页 > 解决方案 > 为什么这些优化看起来明显变慢了？

python - 为什么这些优化看起来明显变慢了？

问题描述

我正在学习 Python（我有一些其他语言的背景，尤其是 C 等），并且我正在尝试编写一些简单的函数来加强我在 Python 教程中所读到的内容。特别是，这是我对确定数字是否为合数的函数的尝试：

def isComposite(n):
    """Straight loop."""
    for x in range(2, int(math.sqrt(n)) + 1):
        if n % x == 0:
            return x
    return False

_PrimeList = [2]

def isCompPL(n):
    """Recursive version."""
    for x in _PrimeList:
        if n % x == 0:
            if n == x:
                return False
            return x
    for x in range(_PrimeList[-1], int(math.sqrt(n)) + 1):
        if not isCompPL(x):
            if x > _PrimeList[-1]:
                _PrimeList.append(x)
            if n % x == 0:
                return x
    return False

def isCompSR(n):
    """Serialized recursive version."""
    l = [n]
    while (math.sqrt(l[0]) > _PrimeList[-1]):
        l.insert(0, int(math.sqrt(l[0])))
    l.insert(0, _PrimeList[-1] + 1)
    while (len(l) > 2):
        q = l.pop([0])
        for x in range(q, l[0]):
            for y in _PrimeList:
                if x % y == 0:
                    break
            else:
                _PrimeList.append(x)
    return isCompPL(n)

isComposite(n)比任何一个isCompPL(n)或开始isCompSR(n)时都快几个数量级。当包含直到 的平方根的所有素数时，两者和都赶上 并且可能比 快，但不是很明显。更令我震惊的是，如果我调用，后续调用仍然比调用慢得多，第一次调用后没有清除。_PrimeList[2]_PrimeListnisCompPL(n)isCompSR(n)isComposite(n)isCompSR(511111111111)isCompSR(1111111111111)isComposite(1111111111111)_PrimeListisCompSR

Python中的列表操作是否隐藏了一些东西，使这些尝试在优化方面不成功，或者只是我添加了很多额外的主要测试并且我需要以某种方式减少那部分？

标签： pythonrecursionoptimization

解决方案

两位主要评论者（@alexis、@juanpa.arrivillaga）对我编写的代码都有正确的评估（评估太多数字，以低效的方式使用列表数据类型），并且在两个方面都进行了改进，更新了“序列化递归”功能总体上要快得多，并且_PrimeList在初始化时比“直接循环”版本快得多。当前版本isCompSR(n)如下所示：

def isCompSR(n):
    """Serialized recursive version."""
    for x in _PrimeList:
        if n % x == 0:
            return x
    l = [n]
    while (math.sqrt(l[-1]) > _PrimeList[-1]):
        l.append(int(math.sqrt(l[-1])))
    l.append(_PrimeList[-1] + 1)
    while (len(l) > 2):
        q = l.pop()
        for x in range(q, l[-1]):
            if n % x == 0:
                return x
            for y in _PrimeList:
                if x % y == 0:
                    break
            else:
                _PrimeList.append(x)
    return False

请注意，此代码现在将在第一个除数处“退出”，n而不是像以前一样继续处理所有数字math.sqrt(n)。此外，l现在通过调用.appendand.pop()而不是在开头插入和弹出来更合适地使用列表。

推荐阅读