让我们假设这个任务:
Generate array A of big random numbers. Sort them. Then generate random number and check if such number exists in array A. Repeat. If found, return its original position (before sort) in the array A and the number's value.
示例:排序前的数组 A:
+-------+------------------------+
| index | 0 1 2 3 4 5 6 7 8 |
| value | 1 3 9 27 81 17 51 40 7 |
+-------+------------------------+
排序后:
+-------+------------------------+
| index | 0 1 8 2 5 9 3 7 6 |
| value | 1 3 7 9 17 21 27 40 51 |
+-------+------------------------+
数组中是否存在数字 21？是的，在索引 9 上!
我想出了以下解决方案:
def value_exists(needle, haystack):
# finds if needle exists in haystack of tuples and returns it if so
for item in haystack:
if item[1] > needle:
return None
if item[1] == needle:
return item
n = 200000
size = 100000000
# fill array A with random numbers
arrayA = [1]
for i in range(1, n):
arrayA.append(randint(0, size))
arrayA = enumerate(arrayA)
# sort them by values keeping its indexes
arrayA = sorted(arrayA, key=lambda x: x[1])
# search
for i in range(1, n):
value = randint(0, size)
check = value_exists(value, arrayA)
if check:
break
if check:
print(check)
此解决方案有效，但速度极慢。将大小设置为 100,000,000 大约需要 30 秒。对于 10,000,000,000，我什至无法得到结果(>5 分钟)。
我无法意识到这项任务有什么耗时。我知道数字很大，但它们适合 64 位整数。我发现 value_exists 函数是问题的核心，是否可以改进？
请您参考如下方法:
为什么不用数组，为什么不用字典呢？您可以将随机数存储在 key 中，并将索引存储在 value 中。
然后，要检查随机数是否在集合中，只需使用in。
例子:
import random
# Create a large list of random numbers
A_list = random.sample(xrange(100000, 999999), 10000)
# EDIT: Forgot to sort the array!
A_list = sorted(A_list)
# Load the numbers in a dictionary
A_dict = {}
for idx, num in enumerate(A_list):
A_dict[num] = idx
# Now, check if a number exists
if 101337 in A_dict:
# it exists!
# Get its index
return A_dict[101337]
