python - bool 值的大大小小的列表和字节数组的相对性能

我在写一个简单的Sieve of Eratosthenes，其中不执行任何除法或模运算就产生一个最多为N的所有素数的列表。抽象地讲，我的实现使用N个布尔值组成的数组，这些值都以False开头，并在算法过程中最终翻转为True。我想知道如果将其实现为list和0的1，list和True的False或bytearray和0中的>。计时（python 2.7）使用python 2.7，我在使用N = 10k和N = 30M时发现以下内容：$ python -m timeit -s 'import sieve' -n 10 'sieve.soe_list(3000000)'10 loops, best of 3: 1.42 sec per loop$ python -m timeit -s 'import sieve' -n 10 'sieve.soe_byte(3000000)'10 loops, best of 3: 1.23 sec per loop$ python -m timeit -s 'import sieve' -n 10 'sieve.soe_list2(3000000)'10 loops, best of 3: 1.65 sec per loop$ python -m timeit -s 'import sieve' -n 500 'sieve.soe_list(10000)'500 loops, best of 3: 3.59 msec per loop$ python -m timeit -s 'import sieve' -n 500 'sieve.soe_byte(10000)'500 loops, best of 3: 4.12 msec per loop$ python -m timeit -s 'import sieve' -n 500 'sieve.soe_list2(10000)'500 loops, best of 3: 4.25 msec per loop 10k 3Mbyte (01) 4.12 ms 1.23 slist (01) 3.59 ms 1.42 slist (TF) 4.25 ms 1.65 s令我惊讶的是，对于较小的N，整数的1是最好的，对于较大的N，list是最好的。 True和False的bytearray总是较慢。计时（python 3.3）我还重复了python 3.3中的测试：$ python -m timeit -s 'import sieve' -n 10 'sieve.soe_list(3000000)'10 loops, best of 3: 2.05 sec per loop$ python -m timeit -s 'import sieve' -n 10 'sieve.soe_byte(3000000)'10 loops, best of 3: 1.76 sec per loop$ python -m timeit -s 'import sieve' -n 10 'sieve.soe_list2(3000000)'10 loops, best of 3: 2.02 sec per loop$ python -m timeit -s 'import sieve' -n 500 'sieve.soe_list(10000)'500 loops, best of 3: 5.19 msec per loop$ python -m timeit -s 'import sieve' -n 500 'sieve.soe_byte(10000)'500 loops, best of 3: 5.34 msec per loop$ python -m timeit -s 'import sieve' -n 500 'sieve.soe_list2(10000)'500 loops, best of 3: 5.16 msec per loop 10k 3Mbyte (01) 5.34 ms 1.76 slist (01) 5.19 ms 2.05 slist (TF) 5.16 ms 2.02 s这里有相同的顺序，对于较小的N，list更好，对于较大的N，list更好，但是bytearray和list的True与和False。记忆使用内存使用与python 2.7和3.3完全相同。我在list或1上使用了0，在算法的开头和结尾处的大小相同。>>> import sieve>>> sieve.verbose = True>>> x = sieve.soe_list(10000)soe_list, 10000 numbers, size = 83120>>> x = sieve.soe_byte(10000)soe_byte, 10000 numbers, size = 10993>>> x = sieve.soe_list2(10000)soe_list2, 10000 numbers, size = 83120>>> x = sieve.soe_list(3000000)soe_list, 3000000 numbers, size = 26791776>>> x = sieve.soe_byte(3000000)soe_byte, 3000000 numbers, size = 3138289>>> x = sieve.soe_list2(3000000)soe_list2, 3000000 numbers, size = 26791776 10k 3Mbyte (01) ~11k ~3.1Mlist (01) ~83k ~27Mlist (TF) ~83k ~27M我有点惊讶〜大的sys.getsizeof比大的list使用更多的内存，因为大的bytearray更快。编辑：糟糕，如评论中所指出，我读错了我自己的值并将27M解释为2.7M。列表确实更大。问题谁能解释为什么为什么对于小N使用bytearray时该算法运行更快，对于大N使用list时该算法运行得更快？测试代码供参考sieve.py：import sysif sys.version_info.major == 3: xrange = rangeverbose = Falsedef soe_byte(upper): numbers = bytearray(0 for _ in xrange(0,upper+1)) if verbose: print("soe_byte, {} numbers, size = {}".format(upper, sys.getsizeof(numbers))) primes = [] cur = 2 while cur <= upper: if numbers[cur] == 1: cur += 1 continue primes.append(cur) for i in xrange(cur,upper+1,cur): numbers[i] = 1 return primesdef soe_list(upper): numbers = list(0 for _ in xrange(0,upper+1)) if verbose: print("soe_list, {} numbers, size = {}".format(upper, sys.getsizeof(numbers))) primes = [] cur = 2 while cur <= upper: if numbers[cur] == 1: cur += 1 continue primes.append(cur) for i in xrange(cur,upper+1,cur): numbers[i] = 1 return primesdef soe_list2(upper): numbers = list(False for _ in xrange(0,upper+1)) if verbose: print("soe_list2, {} numbers, size = {}".format(upper, sys.getsizeof(numbers))) primes = [] cur = 2 while cur <= upper: if numbers[cur] == True: cur += 1 continue primes.append(cur) for i in xrange(cur,upper+1,cur): numbers[i] = True return primes (adsbygoogle = window.adsbygoogle || []).push({}); 最佳答案 谁能用一个列表解释为什么该算法运行得更快  小N，对大N使用字节数组更快？这都是非常特定于实现的，但是您会看到这种现象在实践中经常发生，在这种情况下，使用较小的数据类型将在较小的输入上表现更差，而在较大的输入上表现更好。例如，如果您使用按位逻辑来提取第n位（其中n是变量），而不是仅使用布尔数组，通常会看到这种情况。当n是运行时变量时，从字节中提取第n位需要更多的指令，而不仅仅是设置整个字节，但是位集使用的空间更少。广义上讲，这通常是因为用于访问这些较小类型的指令更昂贵，但是硬件缓存比DRAM访问快得多，并且使用较小类型所获得的空间局部性得到改善，而不能弥补输入大小的不足。变得越来越大。换句话说，当您点击较大的输入时，空间局部性将发挥越来越重要的作用，而较小的数据类型将为您提供更多的输入（允许您将更多相邻的元素放入高速缓存行中）。您可能还会获得改进的时间局部性（更频繁地访问高速缓存行中的相同相邻元素）。因此，即使将元素加载到寄存器中时，它们需要更多指令或更昂贵的指令，也可以通过现在从缓存访问更多内存这一事实来弥补上述开销。现在，为什么bytearrays可能需要比整数列表更多的指令或更昂贵的指令，我不确定。这是非常个别的情况，特定于实现的细节。但也许在您的情况下，它试图将字节数组的第n个元素加载到dword对齐的边界和dword大小的寄存器中，并且必须提取特定的字节以使用其他指令和操作数在寄存器中进行修改。除非我们知道您的Python编译器/解释器为您的特定机器发出的确切机器指令，否则所有这些都是推测。但是无论哪种情况，您的测试都表明bytearrays需要更昂贵的指令来访问，但是对缓存的友好性更高（这对您输入较大的输入会有所补偿）。无论哪种情况，对于较小的数据类型还是较大的数据类型，您都会看到很多事情在发生。这包括压缩，其中在处理压缩数据时要特别注意对齐等硬件细节，这些压缩数据有时可能会胜过未压缩数据，因为解压缩数据所需的额外处理将通过压缩数据的改进的空间局部性来补偿，但仅限于足够大的输入内存访问在其中起着更加关键的作用。 (adsbygoogle = window.adsbygoogle || []).push({});