使用NumPy数据类型的Python字典查找速度

Question

背景

我在NumPy数组中有很多数字消息代码,我需要快速将它们转换为字符串.我在性能方面遇到了一些问题,并希望了解为什么以及如何快速完成.

一些基准

我 - 琐碎的方法

import numpy as np

# dictionary to use as the lookup dictionary
lookupdict = {
     1: "val1",
     2: "val2",
    27: "val3",
    35: "val4",
    59: "val5" }

# some test data
arr = np.random.choice(lookupdict.keys(), 1000000)

# create a list of words looked up
res = [ lookupdict[k] for k in arr ]

字典查找占用了我咖啡休息时间的758毫秒.(我也试过,res = map(lookupdict.get, arr)但情况更糟.)

II - 没有NumPy

import random

# dictionary to use as the lookup dictionary
lookupdict = {
     1: "val1",
     2: "val2",
    27: "val3",
    35: "val4",
    59: "val5" }

# some test data
arr = [ random.choice(lookupdict.keys()) for _ in range(1000000) ]

# create a list of words looked up
res = [ lookupdict[k] for k in arr ]

时序结果相当大的变化到76毫秒!

应该注意的是,我对查找计时感兴趣.随机生成只是为了创建一些测试数据.是否需要花费很多时间并不感兴趣.此处给出的所有基准测试结果仅适用于一百万次查找.

III - 将NumPy数组转换为列表

我的第一个猜测是这与列表与数组问题有关.但是,通过修改NumPy版本来使用列表:

res = [ lookupdict[k] for k in list(arr) ]

给了我778毫秒,其中大约110毫秒用于转换列表和570毫秒进行查找.因此,查找速度要快一些,但总时间是相同的.

IV - 类型转换np.int32为int

由于唯一的其他差异似乎是数据类型(np.int32vs. int),我尝试在运行中转换类型.这有点愚蠢,因为dict可能会做同样的事情:

res = [ lookupdict[int(k)] for k in arr ]

然而,这似乎做了一些有趣的事情,因为时间下降到266毫秒.似乎几乎但不完全相同的数据类型在字典查找中发挥了令人讨厌的技巧,并且dict代码在转换时效率不高.

V - 字典键转换为 np.int32

为了测试这一点,我修改了NumPy版本,以便在dict键和查找中使用完全相同的数据类型:

import numpy as np

# dictionary to use as the lookup dictionary
lookupdict = {
     np.int32(1): "val1",
     np.int32(2): "val2",
    np.int32(27): "val3",
    np.int32(35): "val4",
    np.int32(59): "val5" }

# some test data
arr = np.random.choice(lookupdict.keys(), 1000000)

# create a list of words looked up
res = [ lookupdict[k] for k in arr ]

这提高到177毫秒.76毫秒不是一个微不足道的改进,但相差甚远.

VI - 使用int对象的数组转换

import numpy as np

# dictionary to use as the lookup dictionary
lookupdict = {
     1: "val1",
     2: "val2",
    27: "val3",
    35: "val4",
    59: "val5" }

# some test data
arr = np.array([ random.choice(lookupdict.keys()) for _ in range(1000000) ], 
               dtype='object')

# create a list of words looked up
res = [ lookupdict[k] for k in arr ]

这给出了86毫秒,这已经非常接近本机Python 76毫秒.

结果摘要

1. dict键int,使用int(native python)索引:76 ms
2. dict键int,用int对象索引(NumPy):86 ms
3. dict键np.int32,索引np.int32:177 ms
4. dict键int,索引np.int32:758 ms

问题(S)

为什么？我该怎么做才能尽快使字典查找？我的输入数据是NumPy数组,所以最好(最快但很难看)到目前为止将dict键转换为np.int32.(不幸的是,dict键可能分布在很多数字上,因此逐个数组索引不是一个可行的替代方案.但是快10分钟.)

Answer 1

正如你所怀疑的那样,它的int32.__hash__错误在于x11和以下一样慢int.__hash__:

%timeit hash(5)
10000000 loops, best of 3: 39.2 ns per loop
%timeit hash(np.int32(5))
1000000 loops, best of 3: 444 ns per loop

(该int32类型在C中实现.如果你真的很好玩,你可以挖掘源代码并找出它在那里做了多长时间).

编辑:

减慢事情的第二部分是==对dict查找的隐式比较:

a = np.int32(5)
b = np.int32(5)
%timeit a == b  # comparing two int32's
10000000 loops, best of 3: 61.9 ns per loop
%timeit a == 5  # comparing int32 against int -- much slower
100000 loops, best of 3: 2.62 us per loop

这就解释了为什么你的V比I和IV快得多.当然,坚持使用全int解决方案会更快.

所以我看到它,你有两个选择:

1. 坚持使用纯int类型,或者在dict-lookup之前转换为int
2. 如果最大的代码值不是太大,和/或内存不是问题,你可以交换dict-lookups进行列表索引,这不需要hash.

例如:

lookuplist = [None] * (max(lookupdict.keys()) + 1)
for k,v in lookupdict.items():
    lookuplist[k] = v

res = [ lookuplist[k] for k in arr ] # using list indexing

(编辑:你可能也想在np.choose这里试验)

Answer 2

这很有趣，我可能找到了我的问题的答案。

替代方案 III 是将数组转换为列表。如果方法正确，这似乎可以提供非常好的结果。这：

res = [ lookupdict[k] for k in list(arr) ]

时钟 778 毫秒。

但是这个：

res = [ lookupdict[k] for k in arr.tolist() ]

时钟 86 毫秒。

这背后的技术解释是arr.tolist将数组转换为int对象，而list(arr)创建对象列表np.int32。

Answer 3

在我的时间里，你的II - Without NumPy速度比I

In [11]: timeit [lookupdict[k] for k in np.random.choice(lookupdict.keys(),1000000)]
1 loops, best of 3: 658 ms per loop

In [12]: timeit [lookupdict[k] for k in [np.random.choice(lookupdict.keys()) for _ in range(1000000)]]
1 loops, best of 3: 8.04 s per loop

choice但是，如果通过对值进行查找来跳过查找，您将获得更多时间

In [34]: timeit np.random.choice(lookupdict.values(),1000000)
10 loops, best of 3: 85.3 ms per loop

好的，让我们重点关注查找：

In [26]: arr =np.random.choice(lookupdict.keys(),1000000)

In [27]: arrlist=arr.tolist()

In [28]: timeit res = [lookupdict[k] for k in arr]
1 loops, best of 3: 583 ms per loop

In [29]: timeit res = [lookupdict[k] for k in arrlist]
10 loops, best of 3: 120 ms per loop

In [30]: timeit res = [lookupdict[k] for k in list(arr)]
1 loops, best of 3: 675 ms per loop

In [31]: timeit res = [lookupdict[k] for k in arr.tolist()]
10 loops, best of 3: 156 ms per loop

In [32]: timeit res = [k for k in arr]
1 loops, best of 3: 215 ms per loop

In [33]: timeit res = [k for k in arrlist]
10 loops, best of 3: 51.4 ms per loop

In [42]: timeit arr.tolist()
10 loops, best of 3: 33.6 ms per loop

In [43]: timeit list(arr)
1 loops, best of 3: 264 ms per loop

第一个观察结果 - 对 an 的迭代np.array比对等效列表的迭代慢

其次 -list(arr)速度较慢arr.tolist()。 list()似乎有两个问题。其本身速度较慢，而且项目也较慢np.int32。