检查值是否在列表中存在的最快方法

Question

在一个非常大的列表中（里面有几百万个值），检查一个值是否存在以及它的索引位置，最快的方法是什么？

Answer 1

你可以把你的项目放进一个 set 里。使用集合查找东西是非常高效的。

试试这个：

s = set(a)
if 7 in s:
  # do stuff

补充在评论里你提到你想要获取元素的索引。可惜的是，集合并没有元素位置的概念。一个替代的方法是先对你的列表进行排序，然后每次需要查找元素时使用二分查找。

Answer 2

正如其他人所说，使用 in 在处理大列表时可能会非常慢。这里有一些关于 in、set 和 bisect 性能的比较。请注意，时间（以秒为单位）是以对数尺度表示的。

测试用的代码：

import random
import bisect
import matplotlib.pyplot as plt
import math
import time


def method_in(a, b, c):
    start_time = time.time()
    for i, x in enumerate(a):
        if x in b:
            c[i] = 1
    return time.time() - start_time


def method_set_in(a, b, c):
    start_time = time.time()
    s = set(b)
    for i, x in enumerate(a):
        if x in s:
            c[i] = 1
    return time.time() - start_time


def method_bisect(a, b, c):
    start_time = time.time()
    b.sort()
    for i, x in enumerate(a):
        index = bisect.bisect_left(b, x)
        if index < len(a):
            if x == b[index]:
                c[i] = 1
    return time.time() - start_time


def profile():
    time_method_in = []
    time_method_set_in = []
    time_method_bisect = []

    # adjust range down if runtime is too long or up if there are too many zero entries in any of the time_method lists
    Nls = [x for x in range(10000, 30000, 1000)]
    for N in Nls:
        a = [x for x in range(0, N)]
        random.shuffle(a)
        b = [x for x in range(0, N)]
        random.shuffle(b)
        c = [0 for x in range(0, N)]

        time_method_in.append(method_in(a, b, c))
        time_method_set_in.append(method_set_in(a, b, c))
        time_method_bisect.append(method_bisect(a, b, c))

    plt.plot(Nls, time_method_in, marker='o', color='r', linestyle='-', label='in')
    plt.plot(Nls, time_method_set_in, marker='o', color='b', linestyle='-', label='set')
    plt.plot(Nls, time_method_bisect, marker='o', color='g', linestyle='-', label='bisect')
    plt.xlabel('list size', fontsize=18)
    plt.ylabel('log(time)', fontsize=18)
    plt.legend(loc='upper left')
    plt.yscale('log')
    plt.show()


profile()

Answer 3

7 in a

最简单和最快的方法。

你也可以考虑使用一个 set（集合），但是从你的列表中构建这个集合可能会花费比快速检查是否包含某个元素节省的时间还要多。唯一确定的方法是进行性能测试。（这也取决于你需要哪些操作）

检查值是否在列表中存在的最快方法

12 个回答

撰写回答