Python:两个列表之间的快速映射和查找

Question

我目前正在开发一个高性能的 python 2.7 项目，该项目使用大小为一万个元素的列表。显然，每个操作都必须尽可能快地执行。

所以，我有两个列表:一个是 unique 任意数字的列表，我们称它为 A，另一个是从 1 开始的线性列表，长度与第一个列表，名为 B，表示 A 中的索引(从 1 开始)

类似于枚举，从 1 开始。

例如:

A = [500, 300, 400, 200, 100] # The order here is arbitrary, they can be any integers, but every integer can only exist once
B = [  1,   2,   3,   4,   5] # This is fixed, starting from 1, with exactly as many elements as A

如果我有 B 的一个元素(称为 e_B)并且想要 A 中的相应元素，我可以简单地执行 correspond_e_A = A[e_B - 1]。没问题。

但现在我有一个巨大的随机非唯一整数列表，我想知道 A 中整数的索引，以及 B 中的相应元素是什么。

第一个问题我觉得我有一个合理的解法:

indices_of_existing = numpy.nonzero(numpy.in1d(random_list, A))[0]

这种方法的优点在于不需要 map() 单个操作，numpy 的 in1d 只返回一个列表，如 [True, True, False, True, ...]。使用 nonzero() 我可以获得 A 中存在的 random_list 中元素的索引。完美，我认为。

但是对于第二个问题，我很困惑。 我试过类似的东西:

corresponding_e_B = map(lambda x: numpy.where(A==x)[0][0] + 1, random_list))

这正确地给了我索引，但它不是最优的，因为首先我需要一个 map()，其次我需要一个 lambda，最后 numpy.where() 在找到该项目后不会停止(记住，A只有独特的元素)，这意味着它无法扩展到像我这样的庞大数据集。

我查看了 bisect，但似乎 bisect 只适用于单个请求，不适用于列表，这意味着我仍然必须使用 map() 并按元素构建我的列表(这很慢，不是吗？ )

由于我是 Python 的新手，我希望这里的任何人都有想法？也许是我还不知道的图书馆？

Answer 1

我认为您最好使用哈希表来查找而不是 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 中 map 和 filter 返回类似生成器的对象，所以你需要一个 list 围绕过滤器如果你想获得列表形式的结果。

我尝试尽可能多地使用内置函数来将计算负担推到 C 端(假设您使用 CPython)。所有名称都是预先解析的，因此速度应该非常快。

一般来说，为了获得最佳性能，您可能需要考虑使用 PyPy ，一个很棒的替代 Python 实现，带有 JIT 编译。

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

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

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 快很多(只有 ~10%在 Python 2 中，在 Python 3 中大约慢 25%，但在 PyPy 中慢了近 75%)。这里有一个过早优化的例子。我想差异是由于 fun22 在 Python 2 中为每个查询构建了一个不必要的临时列表。我们还看到二进制搜索非常糟糕(查看 fun23 ).