Python集合与数组的区别

Question

Python集合与数组的区别

9

我需要在内存中存储一个大型数字列表，然后需要进行成员检查。数组比列表更具有内存效率，而Set比列表更适合用于成员检查。我都需要！所以我的问题是：

1）数组比Set更节省多少内存？（相反的情况，请查看下面的结果）。 2）是否有一种数据结构可以在Set和数组之间取得更好的平衡？类似于带有带符号整数类型的Set？或者一些Numpy构造？

我使用以下脚本检查了成员资格时间差异。（我知道timeit更好，但方差足够低，时间就可以了）：

import array
import time 

class TimerContext:
    def __enter__(self):
        self.t0 = time.time()
    def __exit__(self, *args, **kwargs):
        print(time.time()-self.t0)

SIZE = 1000000

l = list([i for i in range(SIZE)])
a = array.array('I', l)
s = set(l)

print(type(l))
print(type(a))
print(type(s))

with TimerContext():
    x = 99999 in l
with TimerContext():
    x = 99999 in a
with TimerContext():
    x = 99999 in s

结果：

<class 'list'>
<class 'array.array'>
<class 'set'>
0.0012176036834716797
0.0024595260620117188
1.430511474609375e-06

因为集合在成员检查方面速度非常快（请注意科学计数法）。所以如果它们的内存占用与数组相差不大，我会更喜欢使用集合。但我不知道如何检查内存占用。

另外，有很多关于比较集合和列表的问题。但我没有看到任何关于比较数组和集合的好答案。

- Neil

1

如果了解您的真正问题，可能会有许多其他更好的解决方案。 - Daniel

3

sys.getsizeof 显示，对于你的示例而言，集合比数组大约多 8 倍。https://docs.python.org/3/library/sys.html#sys.getsizeof. - CristiFati

3

列表和数组成员测试的时间复杂度都为O(n)，集合的时间复杂度为O(1)。此外，还有一些近似算法可以帮助解决这个问题（例如布隆过滤器）。如果您对该问题有其他限制，则可能会有更多选项。 - Sam Mason

1

谷歌建议使用 https://pypi.org/project/intset/ 可能会有所帮助... - Sam Mason

@CristiFati 感谢您提供getsizeof。比我想象的要简单得多。 - Neil

显示剩余6条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Dušan Maďar · Accepted Answer

如果可能的话，在您的情况下，bisect 的性能接近于使用列表和数组的set进行成员检查。请参见下面的结果。

import array
from bisect import bisect
import sys
import time


class TimerContext:
    def __enter__(self):
        self.t0 = time.time()

    def __exit__(self, *args, **kwargs):
        print(time.time() - self.t0)


def get_size_in_megabytes(iterable):
    return round(sys.getsizeof(iterable) / (1024 ** 2), 2)


SIZE = 1000000

l = list([i for i in range(SIZE)])
a = array.array("I", l)
s = set(l)

print(type(l), get_size_in_megabytes(l))
print(type(a), get_size_in_megabytes(a))
print(type(s), get_size_in_megabytes(s))

with TimerContext():
    x = 99999 in l
with TimerContext():
    x = 99999 in a
with TimerContext():
    x = 99999 in s

print("list bisect")
with TimerContext():
    bisect(l, 99999)

print("array bisect")
with TimerContext():
    bisect(a, 99999)

结果：

<class 'list'> 8.58
<class 'array.array'> 3.81
<class 'set'> 32.0
0.0024390220642089844
0.0053005218505859375
3.814697265625e-06
list bisect
9.298324584960938e-06
array bisect
6.198883056640625e-06

感谢 @CristiFati 提供的 sys.getsizeof 使用方法。