”工欲善其事,必先利其器。“—孔子《论语.录灵公》
首页 > 编程 > 您可以将计算斐波那契数列的程序优化到什么程度?

您可以将计算斐波那契数列的程序优化到什么程度?

发布于2024-08-23
浏览:284

您可以将计算斐波那契数列的程序优化到什么程度?

介绍

我学Python的时候,老师给我们布置了一个作业——计算斐波那契数列的第N个数。

我觉得很简单,所以我写了这段代码:

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n - 1)   fib(n - 2)

后来我知道这种解决方案太费时间了。

优化程序

我将解决方案更改为迭代。

def fib(n):
    ls = [1,1]
    for i in range(2,n):
        ls.append(ls[i-1] ls[i-2])

    return ls[n-1]

我用matplotlib绘制它花费的时间:

import time
import matplotlib.pyplot as plt


def bench_mark(func, *args):
    # calculate the time
    start = time.perf_counter()
    result = func(*args)
    end = time.perf_counter()

    return end - start, result  # return the time and the result

def fib(n):
    ls = [1,1]
    for i in range(2,n):
        ls.append(ls[i-1] ls[i-2])

    return ls[n-1]

mark_list = []

for i in range(1,10000):
    mark = bench_mark(fib,i)
    mark_list.append(mark[0])
    print(f"size : {i} , time : {mark[0]}")

plt.plot(range(1, 10000), mark_list)
plt.xlabel('Input Size')
plt.ylabel('Execution Time (seconds)')
plt.title('Test fot fibonacci')
plt.grid(True)
plt.show()

结果在这里:

How Far You Can Optimize a Program to Compute the Fibonacci Sequence?

花费的时间很短。

但是我写了 fib(300000),花费了 5.719049899998936 秒。它太长了。

长大后,我学会了CACHE,所以我改变解决方案,使用dict来存储结果。

from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
    if n 



或者我们可以自己写CACHE。

def fib(n, cache={}):
    if n in cache:
        return cache[n]
    elif n 




          

            
        
版本声明 本文转载于:https://dev.to/mengqinyuan/how-far-can-you-optimize-a-program-to-compute-the-fibonacci-sequence-oa2?1如有侵犯,请联系[email protected]删除
最新教程 更多>
  • 为什么不使用CSS`content'属性显示图像?
    为什么不使用CSS`content'属性显示图像?
    在Firefox extemers属性为某些图像很大,&& && && &&华倍华倍[华氏华倍华氏度]很少见,却是某些浏览属性很少,尤其是特定于Firefox的某些浏览器未能在使用内容属性引用时未能显示图像的情况。这可以在提供的CSS类中看到:。googlepic { 内容:url(&#...
    编程 发布于2025-04-08
  • 如何使用Python理解有效地创建字典?
    如何使用Python理解有效地创建字典?
    在python中,词典综合提供了一种生成新词典的简洁方法。尽管它们与列表综合相似,但存在一些显着差异。与问题所暗示的不同,您无法为钥匙创建字典理解。您必须明确指定键和值。 For example:d = {n: n**2 for n in range(5)}This creates a dicti...
    编程 发布于2025-04-08
  • Java是否允许多种返回类型:仔细研究通用方法?
    Java是否允许多种返回类型:仔细研究通用方法?
    在Java中的多个返回类型:一种误解类型:在Java编程中揭示,在Java编程中,Peculiar方法签名可能会出现,可能会出现,使开发人员陷入困境,使开发人员陷入困境。 getResult(string s); ,其中foo是自定义类。该方法声明似乎拥有两种返回类型:列表和E。但这确实是如此吗...
    编程 发布于2025-04-08
  • 您可以使用CSS在Chrome和Firefox中染色控制台输出吗?
    您可以使用CSS在Chrome和Firefox中染色控制台输出吗?
    在javascript console 中显示颜色是可以使用chrome的控制台显示彩色文本,例如红色的redors,for for for for错误消息?回答是的,可以使用CSS将颜色添加到Chrome和Firefox中的控制台显示的消息(版本31或更高版本)中。要实现这一目标,请使用以下模...
    编程 发布于2025-04-08
  • 为什么PYTZ最初显示出意外的时区偏移?
    为什么PYTZ最初显示出意外的时区偏移?
    与pytz 最初从pytz获得特定的偏移。例如,亚洲/hong_kong最初显示一个七个小时37分钟的偏移: 差异源利用本地化将时区分配给日期,使用了适当的时区名称和偏移量。但是,直接使用DateTime构造器分配时区不允许进行正确的调整。 example pytz.timezone(...
    编程 发布于2025-04-08
  • 如何配置Pytesseract以使用数字输出的单位数字识别?
    如何配置Pytesseract以使用数字输出的单位数字识别?
    Pytesseract OCR具有单位数字识别和仅数字约束 在pytesseract的上下文中,在配置tesseract以识别单位数字和限制单个数字和限制输出对数字可能会提出质疑。 To address this issue, we delve into the specifics of Te...
    编程 发布于2025-04-08
  • 如何使用FormData()处理多个文件上传?
    如何使用FormData()处理多个文件上传?
    )处理多个文件输入时,通常需要处理多个文件上传时,通常是必要的。 The fd.append("fileToUpload[]", files[x]); method can be used for this purpose, allowing you to send multi...
    编程 发布于2025-04-08
  • 如何将来自三个MySQL表的数据组合到新表中?
    如何将来自三个MySQL表的数据组合到新表中?
    mysql:从三个表和列的新表创建新表 答案:为了实现这一目标,您可以利用一个3-way Join。 选择p。*,d.content作为年龄 来自人为p的人 加入d.person_id = p.id上的d的详细信息 加入T.Id = d.detail_id的分类法 其中t.taxonomy =...
    编程 发布于2025-04-08
  • 如何正确使用与PDO参数的查询一样?
    如何正确使用与PDO参数的查询一样?
    在pdo 中使用类似QUERIES在PDO中的Queries时,您可能会遇到类似疑问中描述的问题:此查询也可能不会返回结果,即使$ var1和$ var2包含有效的搜索词。错误在于不正确包含%符号。通过将变量包含在$ params数组中的%符号中,您确保将%字符正确替换到查询中。没有此修改,PDO...
    编程 发布于2025-04-08
  • 为什么不````''{margin:0; }`始终删除CSS中的最高边距?
    为什么不````''{margin:0; }`始终删除CSS中的最高边距?
    在CSS 问题:不正确的代码: 全球范围将所有余量重置为零,如提供的代码所建议的,可能会导致意外的副作用。解决特定的保证金问题是更建议的。 例如,在提供的示例中,将以下代码添加到CSS中,将解决余量问题: body H1 { 保证金顶:-40px; } 此方法更精确,避免了由全局保证金重置引...
    编程 发布于2025-04-08
  • Android如何向PHP服务器发送POST数据?
    Android如何向PHP服务器发送POST数据?
    在android apache httpclient(已弃用) httpclient httpclient = new defaulthttpclient(); httppost httppost = new httppost(“ http://www.yoursite.com/script.p...
    编程 发布于2025-04-08
  • 找到最大计数时,如何解决mySQL中的“组函数\”错误的“无效使用”?
    找到最大计数时,如何解决mySQL中的“组函数\”错误的“无效使用”?
    如何在mySQL中使用mySql 检索最大计数,您可能会遇到一个问题,您可能会在尝试使用以下命令:理解错误正确找到由名称列分组的值的最大计数,请使用以下修改后的查询: 计数(*)为c 来自EMP1 按名称组 c desc订购 限制1 查询说明 select语句提取名称列和每个名称...
    编程 发布于2025-04-08
  • 如何在Java的全屏独家模式下处理用户输入?
    如何在Java的全屏独家模式下处理用户输入?
    Handling User Input in Full Screen Exclusive Mode in JavaIntroductionWhen running a Java application in full screen exclusive mode, the usual event ha...
    编程 发布于2025-04-08
  • 如何使用“ JSON”软件包解析JSON阵列?
    如何使用“ JSON”软件包解析JSON阵列?
    parsing JSON与JSON软件包 QUALDALS:考虑以下go代码:字符串 } func main(){ datajson:=`[“ 1”,“ 2”,“ 3”]`` arr:= jsontype {} 摘要:= = json.unmarshal([] byte(...
    编程 发布于2025-04-08
  • 为什么使用Firefox后退按钮时JavaScript执行停止?
    为什么使用Firefox后退按钮时JavaScript执行停止?
    导航历史记录问题:JavaScript使用Firefox Back Back 此行为是由浏览器缓存JavaScript资源引起的。要解决此问题并确保在后续页面访问中执行脚本,Firefox用户应设置一个空功能。 警报'); }; alert('inline Alert')...
    编程 发布于2025-04-08

免责声明: 提供的所有资源部分来自互联网,如果有侵犯您的版权或其他权益,请说明详细缘由并提供版权或权益证明然后发到邮箱:[email protected] 我们会第一时间内为您处理。

Copyright© 2022 湘ICP备2022001581号-3