python - 在元组数组中搜索值非常慢

Question

让我们假设这个任务:

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 函数是问题的核心，是否可以改进？

Answer 1

为什么不用数组，为什么不用字典呢？您可以将随机数存储在 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]