字典的方法"/>
用来处理python字典的方法
正如我做的一点测试,int => int(不同值)的3,000万个项目的python字典可以很容易地在我的Mac上吃掉2G以上的内存。 由于我只使用int到int dict,所以有比使用python dict更好的解决方案吗?
我需要的一些要求是
内存效率更高,可保存数以千万计的int到int项
基本的dict方法,例如通过键获取值并迭代所有项目
易于序列化为字符串/二进制将是一个加号
更新,
4.通过给定的键容易获得子集,例如d.fromkeys([...])
谢谢。
您可以做出任何假设吗?按键?例如。它们是连续的吗?是否按顺序输入? O(lg n)查找性能是否可以接受?
Python对象相当大,但我认为它们不足够大,无法炸毁高达2 GB的3000万个整数对。我希望有更多的数百兆字节。您如何确定这些数字?并且您正在使用64位Python,还是您的整数特别大(>数十亿)?
我不知道这是否是有效的建议,但请考虑使用其他语言。 Python速度慢且非常消耗内存。考虑C ++
@JasonHsu您可以张贴一些要插入字典的数据条目吗?这将有助于我们了解键->值的大小。
@ delnan,@ Srika Appal,其简单用法如{1:30000001,2:30000002,...,30000000:60000000}。不太现实,但我只是出于测试目的而创建了它。我在Macbook 64位,Python 2.7.5上简单地使用了" for i in range(30000000):d [i] = i + 30000000",而未明确调用任何GC。经过两次测试,它使用了3.06G :)
@ The-IT,拥有一些具有python接口并且可以很容易地与我现有的python逻辑粘合的基于C的库,将非常好。 :)
@larsmans,实际上键是userid或字符串型用户ID的哈希,值将是某个计数器或字符串值的哈希。一些繁琐的过程类似于d.fromkeys([u1,u2,...]),其中d是百万级的大字典,用于获取用户群组的子集。
不确定是否可以使用Numpy。有人可以建议吗?谢谢。
如果键是连续的(如您的示例中所示),则使用numpy数组将很容易。让键成为索引!您的示例将变为numpy.arange(30000000, 60000001, dtype=numpy.int32)或类似的内容。如果需要检测不存在的键,则可以使用NaN或某种不太可能出现在实际数据中的哨兵值(也许-1)。
@Blckknght,基于B树的索引在速度上仍然给我带来Log(n)的复杂性,但是,如果找不到更好的基于哈希表的解决方案,我将绝对考虑。感谢你的信息。
@delnan:经过测试,这里肯定是3.05GB。在64位Python上,这并非不合理:指针为8个字节; dict每个条目包含2个指针,单个int可能为24个字节(8字节refcnt,8字节类型的指针,8字节long的值)。所以多数民众赞成在每个条目64个字节。剩余的空间使用量可以归因于字典的过度分配。
@nneonneo 64位Python是我考虑但不想承担的事情之一。是的,现在加起来。
刚刚在32位Python上进行了测试;其1.46GB。显然,大量的int是64位Python严重失败的地方。
@nneonneo,请在底部检查我有关Judy数组的最新测试。我无法在2天内将其设置为答案。 :)
@JasonHsu:后面的计算表明,使用32位int哈希表的"自己动手"实现将只有300MB(在[int,int]对的简单数组上实现,并带有负载因子0.8)。您可以轻松地在array之上实现该功能,也可以在C中实现其原始性能。如果正确实现,专门针对您的应用程序进行调整的数据结构肯定会胜过任何通用容器。
@ nneonneo,Python认为自己是一种"胶水语言",因此,这种"高密度"数据处理工作将留给较低级的C / C ++库,并使用诸如Cython之类的东西"胶合" :)到64位,因为这是一个折衷方案,以允许更大的内存空间(如果我理解正确的话)
至少有两种可能性:
数组
您可以尝试使用两个数组。一个用于键,另一个用于值,以便index(key)== index(value)
2017年1月5日更新:在数组中使用4字节整数。
阵列将使用较少的内存。在使用python用clang编译的64位FreeBSD机器上,一个3000万个整数的数组使用大约117 MiB。
这些是我使用的python命令:
Python 2.7.13 (default, Dec 28 2016, 20:51:25)
[GCC 4.2.1 Compatible FreeBSD Clang 3.8.0 (tags/RELEASE_380/final 262564)] on freebsd11
Type"help","copyright","credits" or"license" for more information.
>>> from array import array
>>> a = array('i', xrange(30000000))
>>> a.itemsize
4
导入数组后,ps报告:
USER PID %CPU %MEM VSZ RSS TT STAT STARTED TIME COMMAND
rsmith 81023 0.0 0.2 35480 8100 0 I+ 20:35 0:00.03 python (python2.7)
制作数组后:
USER PID %CPU %MEM VSZ RSS TT STAT STARTED TIME COMMAND
rsmith 81023 29.0 3.1 168600 128776 0 S+ 20:35 0:04.52 python (python2.7)
驻留集大小以1 KiB为单位报告,因此(128776-8100)/ 1024 = 117 MiB
使用列表推导,您可以轻松获得键满足特定条件的索引列表。然后,您可以使用该列表中的索引来访问相应的值...
麻木
如果您有可用的numpy,则使用它的速度更快,功能更多并且使用的RAM稍微少一些:
Python 2.7.5 (default, Jun 10 2013, 19:54:11)
[GCC 4.2.1 Compatible FreeBSD Clang 3.1 ((branches/release_31 156863))] on freebsd9
Type"help","copyright","credits" or"license" for more information.
>>> import numpy as np
>>> a = np.arange(0, 30000000, dtype=np.int32)
从ps:启动Python后为6700 KiB,在导入numpy之后为17400 KiB,在创建数组后为134824 KiB。大约是114 MiB。
此外,numpy支持记录数组。
Python 2.7.5 (default, Jun 10 2013, 19:54:11)
[GCC 4.2.1 Compatible FreeBSD Clang 3.1 ((branches/release_31 156863))] on freebsd9
Type"help","copyright","credits" or"license" for more information.
>>> import numpy as np
>>> a = np.zeros((10,), dtype=('i4,i4'))
>>> a
array([(0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0),
(0, 0), (0, 0)],
dtype=[('f0', '
>>> a.dtype.names
('f0', 'f1')
>>> a.dtype.names = ('key', 'value')
>>> a
array([(0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0),
(0, 0), (0, 0)],
dtype=[('key', '
>>> a[3] = (12, 5429)
>>> a
array([(0, 0), (0, 0), (0, 0), (12, 5429), (0, 0), (0, 0), (0, 0), (0, 0),
(0, 0), (0, 0)],
dtype=[('key', '
>>> a[3]['key']
12
在这里,您可以分别访问键和值。
>>> a['key']
array([ 0, 0, 0, 12, 0, 0, 0, 0, 0, 0], dtype=int32)
感谢您的建议,我错失了一些关键要求,即k-v搜索,通过给定键获取子集仍然很重要。所以我不能简单地将它们存储到2个数组中。
@JasonHsu:那么numpy记录数组呢?
如下所述,我将首先尝试一些基于Judy数组的解决方案,如果不起作用,则请尝试Numpy,因为?O(1)查找时间对我而言仍然很重要。感谢您的信息。 :)
O(1)在很大程度上限制了您的选择。哈希映射,不需要搜索的数组(如果键在给定范围内,则可以将其用作索引)是显而易见的选择。
这是一个令人难以置信的答案,应该得到比以往更多的赞誉。
您对array.array不公平,因为您将64位整数数组与32位整数np.array进行了比较。对于大多数64位系统,l表示64位有符号整数。您可以先使用a=array.array(l),然后使用a.itemsize来检查项目的大小(最有可能是8)。np.array仍然是一个更好的选择,因为还有更多功能可以使用。
@ead好点!香港专业教育学院更新了我的答案,以array使用4字节整数。
基于Judy-array的解决方案似乎是我应该考虑的选择。我仍在寻找Python可以使用的良好实现。稍后将更新。
更新,
最后,我在。
那里似乎没有任何文档,但是我试图仅通过dir(...)其包和对象来找到其方法,但是它可以工作。
同样的实验,使用judy.JudyIntObjectMap,它以标准dict的1/3占用了?986MB的内存。它还提供JudyIntSet,在某些特殊情况下,与JudyIntObjectMap相比,它不需要引用任何实际的Python对象作为值,因此可以节省更多内存。
(如以下进一步测试所示,JudyArray仅使用几MB到几十MB,约986MB的大部分实际上是由Python内存空间中的值对象使用的。)
这是一些对您有帮助的代码,
>>> import judy
>>> dir(judy)
['JudyIntObjectMap', 'JudyIntSet', '__doc__', '__file__', '__name__', '__package__']
>>> a=judy.JudyIntObjectMap()
>>> dir(a)
['__class__', '__contains__', '__delattr__', '__delitem__', '__doc__', '__format__', '__getattribute__', '__getitem__', '__hash__', '__init__', '__iter__', '__len__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__setattr__', '__setitem__', '__sizeof__', '__str__', '__subclasshook__', '__value_sizeof__', 'by_index', 'clear', 'get', 'iteritems', 'iterkeys', 'itervalues', 'pop']
>>> a[100]=1
>>> a[100]="str"
>>> a["str"]="str"
Traceback (most recent call last):
File"", line 1, in
KeyError: 'non-integer keys not supported'
>>> for i in xrange(30000000):
... a[i]=i+30000000 #finally eats ~986MB memory
...
更新,
好的,我们测试了一个30M int的JudyIntSet。
>>> a=judy.JudyIntSet()
>>> a.add(1111111111111111111111111)
Traceback (most recent call last):
File"", line 1, in
ValueError: we only support integers in the range [0, 2**64-1]
它仅占用5.7MB的空间来存储30M的顺序int数组[0,30000000),这可能是由于JudyArray的自动压缩所致。 709MB以上是bcz,我使用range(...)而不是更合适的xrange(...)来生成数据。
因此,具有30M int的JudyArray核心的大小完全可以忽略。
如果有人知道更完整的Judy Array包装器实现,请告诉我,因为该包装器仅包装JudyIntObjectMap和JudyIntSet。对于int-int dict,JudyIntObjectMap仍然需要真正的python对象。如果我们只进行counter_add并设置值,则最好将int值存储在C空间中,而不要使用python对象。希望有人有兴趣创建或介绍一个:)
如果您想要的只是一个易于使用的类似字典的计数器,则添加了另一个答案。
Python标准库中的高性能Counter对象
如果我们对使用方法有更多了解,可能会更容易提出好的解决方案。
您说您想通过键来获取值并遍历所有值,但是与是否需要插入/删除数据无关。
一种非常有效的数据存储方式是使用数组模块。如果不需要插入/删除数据,则只需两个数组即可。" key"数组将被排序,您可以对右键进行二进制搜索。然后,您只需从另一个数组中相同的位置选择值即可。
您可以轻松地将其封装在行为类似于dict的类中。我不知道在某个地方是否有现成的解决方案,但是实现起来应该并不困难。这应该可以帮助您避免拥有大量消耗内存的python对象。
但是您可能还有其他要求,使得这种解决方案不切实际/不可能。
谢谢你的建议。病态仍然需要通过给定的键集来获取大字典的子集,例如d.fromkeys([...])。可以对键数组进行扫描和过滤,并插入防止重复操作,因此...对我来说,数组不是一个选择。
更多推荐
用来处理python字典的方法
发布评论