python 两个列表相互映射_Python：两个列表之间的快速映射和查找

我认为建议您使用哈希表来代替

numpy.in1d,它使用O(n log n)合并排序作为预处理步骤.

>>> A = [500, 300, 400, 200, 100]

>>> index = { k:i for i,k in enumerate(A, 1) }

>>> random_list = [200, 100, 50]

>>> [i for i,x in enumerate(random_list) if x in index]

[0, 1]

>>> map(index.get, random_list)

[4, 5, None]

>>> filter(None, map(index.get, random_list))

[4, 5]

这是Python 2,在Python 3中映射并过滤返回类似于生成器的对象,因此如果要将结果作为列表获取,则需要围绕过滤器的列表.

我试图尽可能地使用内置函数来将计算负担推到C端(假设你使用CPython).所有的名字都是预先解决的,所以它应该非常快.

通常,为了获得最佳性能,您可能需要考虑使用PyPy,这是一个使用JIT编译的很好的替代Python实现.

比较多种方法的基准从来都不是一个坏主意：

import sys

is_pypy = '__pypy__' in sys.builtin_module_names

import timeit

import random

if not is_pypy:

import numpy

import bisect

n = 10000

m = 10000

q = 100

A = set()

while len(A) < n: A.add(random.randint(0,2*n))

A = list(A)

queries = set()

while len(queries) < m: queries.add(random.randint(0,2*n))

queries = list(queries)

# these two solve question one (find indices of queries that exist in A)

if not is_pypy:

def fun11():

for _ in range(q):

numpy.nonzero(numpy.in1d(queries, A))[0]

def fun12():

index = set(A)

for _ in range(q):

[i for i,x in enumerate(queries) if x in index]

# these three solve question two (find according entries of B)

def fun21():

index = { k:i for i,k in enumerate(A, 1) }

for _ in range(q):

[index[i] for i in queries if i in index]

def fun22():

index = { k:i for i,k in enumerate(A, 1) }

for _ in range(q):

list(filter(None, map(index.get, queries)))

def findit(keys, values, key):

i = bisect.bisect(keys, key)

if i == len(keys) or keys[i] != key:

return None

return values[i]

def fun23():

keys, values = zip(*sorted((k,i) for i,k in enumerate(A,1)))

for _ in range(q):

list(filter(None, [findit(keys, values, x) for x in queries]))

if not is_pypy:

# note this does not filter out nonexisting elements

def fun24():

I = numpy.argsort(A)

ss = numpy.searchsorted

maxi = len(I)

for _ in range(q):

a = ss(A, queries, sorter=I)

I[a[a

tests = ("fun12", "fun21", "fun22", "fun23")

if not is_pypy: tests = ("fun11",) + tests + ("fun24",)

if is_pypy:

# warmup

for f in tests:

timeit.timeit("%s()" % f, setup = "from __main__ import %s" % f, number=20)

# actual timing

for f in tests:

print("%s: %.3f" % (f, timeit.timeit("%s()" % f, setup = "from __main__ import %s" % f, number=3)))

结果：

$python2 -V

Python 2.7.6

$python3 -V

Python 3.3.3

$pypy -V

Python 2.7.3 (87aa9de10f9ca71da9ab4a3d53e0ba176b67d086, Dec 04 2013, 12:50:47)

[PyPy 2.2.1 with GCC 4.8.2]

$python2 test.py

fun11: 1.016

fun12: 0.349

fun21: 0.302

fun22: 0.276

fun23: 2.432

fun24: 0.897

$python3 test.py

fun11: 0.973

fun12: 0.382

fun21: 0.423

fun22: 0.341

fun23: 3.650

fun24: 0.894

$pypy ~/tmp/test.py

fun12: 0.087

fun21: 0.073

fun22: 0.128

fun23: 1.131

您可以调整场景的n(大小A),m(random_list的大小)和q(查询的数量).令我惊讶的是,我尝试聪明并使用内置函数而不是list comps并没有得到回报,因为fun22并不比fun21快很多(Python 2只有10％左右,Python 3只有~25％,但差不多75在PyPy中慢了％).这里是一个过早优化的案例.我想差异是因为fun22在Python 2中为每个查询构建了一个不必要的临时列表.我们也看到二进制搜索非常糟糕(看看fun23).