Поиск всех ключей в словаре из данного списка БЫСТРО

Ответ 1

Из нескольких дополнительных методов, которые я пробовал, самым быстрым было простое понимание списка:

def way6(theList, theDict):
    return [item for item in theList if item in theDict]

Выполняется тот же самый процесс, что и ваш самый быстрый подход, way1, но быстрее. Для сравнения, самый быстрый способ set был

def way5(theList, theDict):
    return list(set(theList).intersection(theDict))

timeit результаты:

>>> import timeit
>>> setup = """from __main__ import way1, way5, way6
from random import randint
length = 100000
listOfRandomInts = [randint(0,length*length/10-1) for x in range(length)]
dictionaryOfRandomInts = {randint(0,length*length/10-1): "It here" for x in range(length)}
"""
>>> timeit.timeit('way1(listOfRandomInts,dictionaryOfRandomInts)', setup=setup, number=1000)
14.550477756582723
>>> timeit.timeit('way5(listOfRandomInts,dictionaryOfRandomInts)', setup=setup, number=1000)
19.597916393388232
>>> timeit.timeit('way6(listOfRandomInts,dictionaryOfRandomInts)', setup=setup, number=1000)
13.652289059326904

Добавив предложение @abarnert:

def way7(theList, theDict):
    return list(theDict.viewkeys() & theList)

и снова запустите время, которое я сейчас получаю:

>>> timeit.timeit('way1(listOfRandomInts,dictionaryOfRandomInts)', setup=setup, number=1000)
13.110055883138497
>>> timeit.timeit('way5(listOfRandomInts,dictionaryOfRandomInts)', setup=setup, number=1000)
17.292466681101036
>>> timeit.timeit('way6(listOfRandomInts,dictionaryOfRandomInts)', setup=setup, number=1000)
14.351759544463917
>>> timeit.timeit('way7(listOfRandomInts,dictionaryOfRandomInts)', setup=setup, number=1000)
17.206370930653392

way1 и way6 имеют переключаемые места, поэтому я снова перезапустил:

>>> timeit.timeit('way1(listOfRandomInts,dictionaryOfRandomInts)', setup=setup, number=1000)
13.648176054011941
>>> timeit.timeit('way6(listOfRandomInts,dictionaryOfRandomInts)', setup=setup, number=1000)
13.847062579316628

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

Ответ 2

Во-первых, я думаю, что вы на 2.7, поэтому я сделаю большую часть этого с помощью 2.7. Но стоит отметить, что если вы действительно заинтересованы в оптимизации кода, ветка 3.x продолжает получать улучшения производительности, а ветка 2.x никогда не будет. И почему вы используете CPython вместо PyPy?

В любом случае, некоторые дополнительные микро-оптимизации, чтобы попробовать (в дополнение к тем, что в jonrsharpe answer:

Кэширующий атрибут и/или глобальный поиск в локальных переменных (он называется LOAD_FAST по какой-либо причине). Например:

def way1a(theList, theDict):
    resultsList = []
    rlappend = resultsList.append
    for listItem in theList:
        if listItem in theDict:
            rlappend(theDict[listItem])
    return resultsList

In [10]: %timeit way1(listOfRandomInts, dictionaryOfRandomInts)
100 loops, best of 3: 13.2 ms per loop
In [11]: %timeit way1a(listOfRandomInts, dictionaryOfRandomInts)
100 loops, best of 3: 12.4 ms per loop

Но для некоторых операторов специальные методы, такие как __contains__ и __getitem__, могут не стоить. Конечно, вы не узнаете, пока не попытаетесь:

def way1b(theList, theDict):
    resultsList = []
    rlappend = resultsList.append
    tdin = theDict.__contains__
    tdgi = theDict.__getitem__
    for listItem in theList:
        if tdin(listItem):
            rlappend(tdgi(listItem))
    return resultsList

In [14]: %timeit way1b(listOfRandomInts, dictionaryOfRandomInts)
100 loops, best of 3: 12.8 ms per loop

Между тем, ответ Jon way6 уже полностью оптимизирует resultList.append, используя listcomp, и мы просто увидели, что оптимизация поисковых запросов, которые он, вероятно, не поможет. Особенно в 3.x, где понимание собирается скомпилировать в собственную функцию, но даже в 2.7 я бы не ожидал никакой выгоды по тем же причинам, что и в явном цикле. Но попробуйте просто убедиться:

def way6(theList, theDict):
    return [theDict[item] for item in theList if item in theDict]
def way6a(theList, theDict):
    tdin = theDict.__contains__
    tdgi = theDict.__getitem__
    return [tdgi(item) for item in theList if tdin(item)]

In [31]: %timeit way6(listOfRandomInts, dictionaryOfRandomInts)
100 loops, best of 3: 14.7 ms per loop
In [32]: %timeit way6a(listOfRandomInts, dictionaryOfRandomInts)
100 loops, best of 3: 13.9 ms per loop

Удивительно (по крайней мере для меня), на этот раз это действительно помогло. Не знаю, почему.

Но я действительно настраивал это: еще одно преимущество превращения выражения фильтра и выражения значения в вызовы функций состоит в том, что мы можем использовать filter и map:

def way6b(theList, theDict):
    tdin = theDict.__contains__
    tdgi = theDict.__getitem__
    return map(tdgi, filter(tdin, theList))
def way6c(theList, theDict):
    tdin = theDict.__contains__
    tdgi = theDict.__getitem__
    return map(tdgi, ifilter(tdin, theList))

In [34]: %timeit way6b(listOfRandomInts, dictionaryOfRandomInts)
100 loops, best of 3: 10.7 ms per loop
In [35]: %timeit way6c(listOfRandomInts, dictionaryOfRandomInts)
100 loops, best of 3: 13 ms per loop

Но этот выигрыш во многом зависит от 2.x; 3.x имеет более быстрое понимание, а его list(map(filter(…))) медленнее 2.x map(filter(…)) или map(ifilter(…)).

Вам не нужно преобразовывать обе стороны набора пересечений в набор, только с левой стороны; правая сторона может быть любым итерабельным, а dict уже является итерируемым из его ключей.

Но, что еще лучше, представление ключа ключа (dict.keys в 3.x, dict.keyview в 2.7) уже является подобным множеству объекту, а один поддерживается хэш-таблицей dict, поэтому вам не нужно преобразовать что угодно. (Он не имеет такого же интерфейса - он не имеет метода intersection, но его оператор & принимает итерации, в отличие от set, который имеет метод intersection, который принимает итерации, но его & принимает только множества Это раздражает, но мы только заботимся о производительности здесь, верно?)

def way3(theList,theDict):
    return list(set(theList).intersection(set(theDict.keys())))
def way3a(theList,theDict):
    return list(set(theList).intersection(theDict))
def way3b(theList,theDict):
    return list(theDict.viewkeys() & theList)

In [20]: %timeit way3(listOfRandomInts, dictionaryOfRandomInts)
100 loops, best of 3: 23.7 ms per loop
In [20]: %timeit way3a(listOfRandomInts, dictionaryOfRandomInts)
100 loops, best of 3: 15.5 ms per loop
In [20]: %timeit way3b(listOfRandomInts, dictionaryOfRandomInts)
100 loops, best of 3: 15.7 ms per loop

Это последнее не помогло (хотя использование Python 3.4 вместо 2.7, это было на 10% быстрее...), но первая определенно сделала.

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

Во всяком случае, самым быстрым результатом стал map(filter(…)) на 2,7, довольно неплохой запас. В 3,4 (что я здесь не показывал), Jon listcomp был самым быстрым (даже фиксированным, чтобы возвращать значения, а не ключи), и быстрее, чем любой из 2.7 методов. Кроме того, 3.4 самая быстрая операция установки (с использованием представления ключа в виде набора и списка как итерабельного) была намного ближе к итерационным методам, чем к 2.7.

Ответ 3

$ ipython2 # Apple CPython 2.7.6
[snip]
In [3]: %timeit way1(listOfRandomInts, dictionaryOfRandomInts)
100 loops, best of 3: 13.8 ms per loop

$ python27x -m ipython # custom-built 2.7.9
[snip]
In [3]: %timeit way1(listOfRandomInts, dictionaryOfRandomInts)
100 loops, best of 3: 13.7 ms per loop

$ ipython3 # python.org CPython 3.4.1
[snip]
In [3]: %timeit way1(listOfRandomInts, dictionaryOfRandomInts)
100 loops, best of 3: 12.8 ms per loop    

Итак, это 8% ускорение, просто используя более поздний Python. (И ускорение было ближе к 20% в версиях listcomp и dict-key-view.) И это не потому, что Apple 2.7 плохо или что-то в этом роде, просто 3.x продолжает получать оптимизацию за последние 5+ лет, в то время как 2.7 не имеет (и никогда больше не будет).

А между тем:

$ ipython_pypy # PyPy 2.5.0 Python 2.7.8
[snip]
In [3]: %timeit way1(listOfRandomInts, dictionaryOfRandomInts)
1000000000 loops, best of 3: 1.97 ns per loop

Это 7000000x ускорение, просто набрав 5 дополнительных символов.:)

Я уверен, что он обманывает здесь. Либо JIT неявно запомнил результат, либо заметил, что я даже не смотрел на результат и не подтолкнул его к цепочке, и понял, что ему не нужно делать какие-либо шаги или что-то в этом роде. Но иногда это происходит в реальной жизни; У меня был огромный беспорядок кода, который провел 3 дня отладки и пытался оптимизировать, прежде чем осознать, что все, что он сделал, не нужно...

Во всяком случае, ускорения порядка 10x довольно типичны для PyPy, даже если он не может обмануть. И это намного проще, чем настраивать поиск атрибутов или отменять порядок, который превращается в набор на 5%.

Jython более непредсказуем - иногда почти так же быстро, как PyPy, иногда намного медленнее, чем CPython. К сожалению, timeit разбит на Jython 2.5.3, и я просто полностью сломал Jython 2.7, обновив с rc2 на rc3, поэтому... нет тестов сегодня. Аналогично, IronPython в основном Jython переделан на другой виртуальной машине; он обычно быстрее, но снова непредсказуем. Но моя текущая версия Mono и моя текущая версия IronPython не сочетаются друг с другом, поэтому тестов нет.