鱼C论坛

 找回密码
 立即注册
查看: 1884|回复: 6

[已解决]这个题是不是有点超范围了,没看明白

[复制链接]
发表于 2023-8-14 12:29:44 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
题目在图片里面
首先没有做任何修改的情况下为啥源代码运行不出来结果呢?
然后是不知道怎么修改使得其速度快10000倍
大神求教
import random
import timeit

haystack = [random.randint(1, 10000000) for i in range(10000000)]
needles = [random.randint(1, 1000) for i in range(1000)]

# 请在此处添加一行代码,使得查找过程的执行效率提高 10000 倍以上。


def find():
    found = 0
    for each in needles:
        if each in haystack:
            found += 1

    print(f"一共找到{found}个匹配。")

t = timeit.timeit("find()", setup="from __main__ import find", number=1)
print(f"查找过程一共消耗{t}秒。")
最佳答案
2023-8-14 12:30:24
首先,对于给定的代码,它的运行时间可能会非常长,因为在每次查找 needles 中的数值时,都需要遍历整个 haystack 列表。这种线性搜索的方式效率较低。

要使查找过程的执行效率提高 10000 倍以上,可以使用一种更高效的数据结构,例如集合(Set)。

以下是修改代码的示例:
import random
import timeit

haystack = set(random.randint(1, 10000000) for _ in range(10000000))
needles = [random.randint(1, 1000) for _ in range(1000)]

def find():
    found = 0
    for each in needles:
        if each in haystack:
            found += 1
    print(f"一共找到{found}个匹配。")

t = timeit.timeit("find()", setup="from __main__ import find", number=1)
print(f"查找过程一共消耗{t}秒。")

在这个修改后的代码中,我们将 haystack 列表转换为集合类型 set,这样就可以使用集合的高效查找功能。在集合中进行查找操作的平均时间复杂度为 O(1),远快于之前的线性搜索。

通过这种方式,您应该能够显著提高查找过程的执行效率。请注意,具体的性能提升取决于计算机的硬件和其他因素。

如果您有任何疑问,请随时提出。
如果问题已经解决,请设置最佳答案
题目.png
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2023-8-14 12:30:24 | 显示全部楼层    本楼为最佳答案   
首先,对于给定的代码,它的运行时间可能会非常长,因为在每次查找 needles 中的数值时,都需要遍历整个 haystack 列表。这种线性搜索的方式效率较低。

要使查找过程的执行效率提高 10000 倍以上,可以使用一种更高效的数据结构,例如集合(Set)。

以下是修改代码的示例:
import random
import timeit

haystack = set(random.randint(1, 10000000) for _ in range(10000000))
needles = [random.randint(1, 1000) for _ in range(1000)]

def find():
    found = 0
    for each in needles:
        if each in haystack:
            found += 1
    print(f"一共找到{found}个匹配。")

t = timeit.timeit("find()", setup="from __main__ import find", number=1)
print(f"查找过程一共消耗{t}秒。")

在这个修改后的代码中,我们将 haystack 列表转换为集合类型 set,这样就可以使用集合的高效查找功能。在集合中进行查找操作的平均时间复杂度为 O(1),远快于之前的线性搜索。

通过这种方式,您应该能够显著提高查找过程的执行效率。请注意,具体的性能提升取决于计算机的硬件和其他因素。

如果您有任何疑问,请随时提出。
如果问题已经解决,请设置最佳答案
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-8-14 12:31:08 | 显示全部楼层
运行不出来是因为他花了一分多钟来运行,你需要等待;
haystack = set(haystack)
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

发表于 2023-8-14 12:31:10 | 显示全部楼层
这个问题涉及到如何优化查找过程的执行效率。首先,我们来解决源代码不能运行出结果的问题。

源代码中的问题在于,没有定义 find() 函数内的变量 haystack 和 needles 为全局变量。因此,在 find() 函数内部无法访问到这两个变量,导致无法进行查找操作。为了解决这个问题,我们需要将 haystack 和 needles 定义为全局变量。

修改后的代码如下:
import random
import timeit

haystack = [random.randint(1, 10000000) for i in range(10000000)]
needles = [random.randint(1, 1000) for i in range(1000)]

def find():
    global haystack, needles
    found = 0
    for each in needles:
        if each in haystack:
            found += 1

    print(f"一共找到{found}个匹配。")

t = timeit.timeit("find()", setup="from __main__ import find", number=1)
print(f"查找过程一共消耗{t}秒。")

接下来,我们来解决如何使得查找过程的执行效率提高10000倍以上的问题。

在原始代码中,使用了简单的线性查找算法,每次都遍历 haystack 来查找是否存在匹配的元素。这种算法的时间复杂度是O(n),其中n是 haystack 列表的长度。对于大规模的数据集,这种算法的效率较低。

为了提高查找的效率,我们可以使用更高效的数据结构,比如集合(Set)。集合是一种无序且不重复的数据结构,查找操作的时间复杂度是O(1)。我们可以将 haystack 转换为集合,然后使用集合的 intersection() 方法来查找与 needles 的交集。

修改后的代码如下:
import random
import timeit

haystack = set(random.randint(1, 10000000) for i in range(10000000))
needles = set(random.randint(1, 1000) for i in range(1000))

def find():
    global haystack, needles
    found = len(haystack.intersection(needles))
    print(f"一共找到{found}个匹配。")

t = timeit.timeit("find()", setup="from __main__ import find", number=1)
print(f"查找过程一共消耗{t}秒。")

通过将 haystack 和 needles 转换为集合,并使用集合的 intersection() 方法,我们可以大大提高查找过程的执行效率。这样的优化可以使执行时间缩短10000倍以上。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-8-14 12:34:14 | 显示全部楼层
tommyyu 发表于 2023-8-14 12:31
运行不出来是因为他花了一分多钟来运行,你需要等待;

谢谢
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-8-14 12:40:03 | 显示全部楼层
isdkz 发表于 2023-8-14 12:31
这个问题涉及到如何优化查找过程的执行效率。首先,我们来解决源代码不能运行出结果的问题。

源代码中的 ...

需要那么麻烦吗?感觉只需要将其转化为集合就可以了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-8-14 13:28:15 | 显示全部楼层
他们是 ChatGPT 机器人
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-25 10:04

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表