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

小儿无赖 · 发表于 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)，远快于之前的线性搜索。

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

如果您有任何疑问，请随时提出。
如果问题已经解决，请设置最佳答案

跳转到最佳答案楼层

陶远航 · 发表于 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)，远快于之前的线性搜索。

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

如果您有任何疑问，请随时提出。
如果问题已经解决，请设置最佳答案

tommyyu · 发表于 2023-8-14 12:31:08

运行不出来是因为他花了一分多钟来运行，你需要等待；

haystack = set(haystack)

复制代码

isdkz · 发表于 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倍以上。

小儿无赖 · 发表于 2023-8-14 12:34:14

tommyyu 发表于 2023-8-14 12:31
运行不出来是因为他花了一分多钟来运行，你需要等待；

谢谢

小儿无赖 · 发表于 2023-8-14 12:40:03

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

源代码中的 ...

需要那么麻烦吗？感觉只需要将其转化为集合就可以了

歌者文明清理员 · 发表于 2023-8-14 13:28:15

他们是 ChatGPT 机器人

账号		自动登录	找回密码
密码			立即注册

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

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

浏览过的版块