在元组数组中搜索值非常困难

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.

---

示例：排序前数组：

+-------+------------------------+
| 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

首先，作为一种更有效的方法，您可以在value_exists函数中使用生成器表达式，也不需要检查item[1] > needle：

def value_exists(needle, haystack):
    return next(item for item in haystack if item[1] == needle,None)

你可以用random.sample创建一个随机列表。例如：

>>> random.sample(range(100),10)
[87, 24, 71, 64, 86, 11, 59, 54, 20, 92]

同样，对于最后一部分，可以使用生成器表达式：

next(value_exists(randint(0, size), arrayA) for i in range(1, n),None)

关于数组的排序，如果有必要，您可以使用operator.itemgetter()作为key，这对于长列表更有效：

from operator import itemgetter
arrayA = sorted(arrayA, key=itemgetter(1))

Answer 2

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