Какой самый эффективный способ проверить существование числа в наборе чисел в Python

Question

Итак, у меня есть список чисел в python в списке, подобном этому: [1,89,1221,1919,1920,10210,...] с несколькими тысячами чисел, и я хочу проверить, есть ли в нем переменная i.

Я делаю это так:

if i in mylist:

Но это самый быстрый способ?

Некоторые дополнительные характеристики:

• список не содержит дубликатов
• список содержит только целые числа
• список можно упорядочить, если это повышает производительность
• список на самом деле может быть набором (поэтому без дубликатов)
• список может быть любым видом коллекции

Answer 1

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

Однако преобразование в набор только для одного теста членства звучит неэффективно, хотя бы из-за накладных расходов по созданию новой структуры данных.

import random
import timeit

mylist = list(random.randint(1, 50000) for i in xrange(1000))
myset = set(mylist)

s = "1919 in mylist"
t = timeit.Timer(s, "from __main__ import mylist")
print s + ":%.2f usec/pass" % (1000000 * t.timeit(number = 100000)/100000)

s = "1919 in set(mylist)"
t = timeit.Timer(s, "from __main__ import mylist")
print s + ":%.2f usec/pass" % (1000000 * t.timeit(number = 100000)/100000)

Вот результаты:

1919 in mylist:22.81 usec/pass
1919 in set(mylist):65.42 usec/pass

Answer 2

Один из подходов заключается в использовании модуля timeit для проверки различных подходов.Например, я набрал следующий код:

import array
import bisect
import random
import timeit

mylist = list(random.randint(1, 50000) for i in xrange(1000))
myset = set(mylist)
myarray = array.array('l', mylist)

s = "1919 in mylist"
t = timeit.Timer(s, "from __main__ import mylist")
print s + ":%.2f usec/pass" % (1000000 * t.timeit(number = 100000)/100000)

s = "1919 in myset"
t = timeit.Timer(s, "from __main__ import myset")
print s + ":%.2f usec/pass" % (1000000 * t.timeit(number = 100000)/100000)

s = "1919 in myarray"
t = timeit.Timer(s, "from __main__ import myarray")
print s + ":%.2f usec/pass" % (1000000 * t.timeit(number = 100000)/100000)

mysortedlist = sorted(mylist)
mysortedarray = array.array('l', mysortedlist)

s = "1919 in mysortedlist"
t = timeit.Timer(s, "from __main__ import mysortedlist")
print s + ":%.2f usec/pass" % (1000000 * t.timeit(number = 100000)/100000)

s = "1919 in mysortedarray"
t = timeit.Timer(s, "from __main__ import mysortedarray")
print s + ":%.2f usec/pass" % (1000000 * t.timeit(number = 100000)/100000)

def bisect_in(a, x):
    i = bisect.bisect_left(a, x)
    return (i != len(a) and a[i] == x)

s = "bisect_in(mysortedlist, 1919)"
t = timeit.Timer(s, "from __main__ import bisect_in, mysortedlist")
print s + ":%.2f usec/pass" % (1000000 * t.timeit(number = 100000)/100000)

и получил следующие результаты:

1919 in mylist:73.89 usec/pass
1919 in myset:0.29 usec/pass
1919 in myarray:103.77 usec/pass
1919 in mysortedlist:75.12 usec/pass
1919 in mysortedarray:114.21 usec/pass
bisect_in(mysortedlist, 1919):4.17 usec/pass

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

Answer 3

Преобразование в набор и выполнение in - самый быстрый способ.

if i in set(mylist):

Набор - это, в основном, хеш-таблица, а поиск - O (1).

Answer 4

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

Исходный список:

   In [106]: %timeit i in myList
   10000 loops, best of 3: 21.3 us per loop

Создание таблицы поиска:

   In [90]: lookup = [False for i in range( max(myList)+1 )]

   In [91]: for i in myList:
                lookup[i] = True

   In [92]: %timeit lookup[i]
   10000000 loops, best of 3: 50.7 ns per loop  

Таблица поиска здесь в ~ 400 раз быстрее, чем несортированный список.

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

Интересно, что метод таблицы поиска медленнее на 25% при использовании массивов Numpy.(Однако создание таблицы поиска выполняется намного быстрее)

Редактировать: Этот метод также превосходит "i in set (myList)" в 2 раза по скорости.

Answer 5

Сделать набор из списка, пересечь множества и проверить размер пересечения?