Fastest way to check if a value exists in a list

Какой самый быстрый способ проверить, существует ли значение в очень большом списке (с миллионами значений) и каков его индекс?

7 in a

Самый простой и быстрый способ сделать это.

Вы также можете рассмотреть возможность использования set, но создание этого набора из вашего списка может занять больше времени, чем сэкономит более быстрое тестирование членства. Единственный способ убедиться в этом - хорошо протестировать. (это также зависит от того, какие операции вам требуются)

Как указывали другие, 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()

Вы могли бы поместить свои элементы в set. Поиск по настройкам очень эффективен.

Попробуйте:

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

редактировать В комментарии вы говорите, что хотели бы получить индекс элемента. К сожалению, наборы не имеют представления о позиции элемента. Альтернативой является предварительная сортировка вашего списка, а затем использование бинарного поиска каждый раз, когда вам нужно найти элемент.

Первоначальный вопрос был:

Какой самый быстрый способ узнать, существует ли значение в списке (списке с миллионами значений в нем) и каков его индекс?

Таким образом, нужно найти две вещи:

1. это элемент в списке, и


2. что такое индекс (если в списке).

Для этого я модифицировал код @xslittlegrass для вычисления индексов во всех случаях и добавил дополнительный метод.

Результаты

Методы:

1. в--в основном, если x в b: возвращает b.index(x)


2. попробуйте--try / catch для b.index(x) (не нужно проверять, есть ли x в b)


3. set - в основном, если x в set(b): возвращает b.index(x)


4. разделить пополам - отсортировать b по его индексу, двоичный поиск x в sorted(b). Обратите внимание на мод от @xslittlegrass, который возвращает индекс в отсортированном b, а не исходном b)


5. reverse- сформировать словарь обратного поиска d для b; затем d [x] предоставляет индекс x.

Результаты показывают, что метод 5 является самым быстрым.

Интересно, что методы try и set эквивалентны по времени.

Тестовый код

import random
import bisect
import matplotlib.pyplot as plt
import math
import timeit
import itertools

def wrapper(func, *args, **kwargs):
    " Use to produced 0 argument function for call it"
    # Reference https://www.pythoncentral.io/time-a-python-function/
    def wrapped():
        return func(*args, **kwargs)
    return wrapped

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

def method_try(a,b,c):
    for i, x in enumerate(a):
        try:
            c[i] = b.index(x)
        except ValueError:
            c[i] = -1

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

def method_bisect(a,b,c):
    " Finds indexes using bisection "

    # Create a sorted b with its index
    bsorted = sorted([(x, i) for i, x in enumerate(b)], key = lambda t: t[0])

    for i,x in enumerate(a):
        index = bisect.bisect_left(bsorted,(x, ))
        c[i] = -1
        if index < len(a):
            if x == bsorted[index][0]:
                c[i] = bsorted[index][1]  # index in the b array

    return c

def method_reverse_lookup(a, b, c):
    reverse_lookup = {x:i for i, x in enumerate(b)}
    for i, x in enumerate(a):
        c[i] = reverse_lookup.get(x, -1)
    return c

def profile():
    Nls = [x for x in range(1000,20000,1000)]
    number_iterations = 10
    methods = [method_in, method_try, method_set_in, method_bisect, method_reverse_lookup]
    time_methods = [[] for _ in range(len(methods))]

    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)]

        for i, func in enumerate(methods):
            wrapped = wrapper(func, a, b, c)
            time_methods[i].append(math.log(timeit.timeit(wrapped, number=number_iterations)))

    markers = itertools.cycle(('o', '+', '.', '>', '2'))
    colors = itertools.cycle(('r', 'b', 'g', 'y', 'c'))
    labels = itertools.cycle(('in', 'try', 'set', 'bisect', 'reverse'))

    for i in range(len(time_methods)):
        plt.plot(Nls,time_methods[i],marker = next(markers),color=next(colors),linestyle='-',label=next(labels))

    plt.xlabel('list size', fontsize=18)
    plt.ylabel('log(time)', fontsize=18)
    plt.legend(loc = 'upper left')
    plt.show()

profile()