python - 集合运算的奇怪表现

Question

所有这些结果都是使用 CPython 3.5.2 获得的。

我注意到 set 类的某些操作有奇怪的表现。

我测量了执行仅包含整数的两个集合的并集所需的时间。当然，这个时间取决于集合的大小。令人惊讶的是，它还取决于整数的“密度”。这是一个情节:

x 轴是两组大小的总和(对于每次体验，两组都是随机且彼此独立选择的)。y 轴是时间，以秒为单位(对数刻度)。

密度d表示集合是通过从总共N/d个整数中采样N个整数来实例化的。换句话说，对于密度 0.5，我们取某个区间的整数的二分之一，而对于密度 0.1，我们取某个(更大)区间的整数的十分之一。

这是获得一些结果的最小代码(如果需要，我可以发布用于绘图的完整代码，但它更长)。

import time
import random
import numpy

def get_values(size, density):
    return set(random.sample(range(int(size/density)), size))

def perform_op(size, density):
    values1 = get_values(size, density)
    values2 = get_values(size, density)
    t = time.time()
    result = values1 | values2
    return time.time()-t

size = 10000000
for density in [0.05, 0.1, 0.5, 0.99]:
    times = [perform_op(size, density) for _ in range(10)]
    print('density: %.2f, mean time: %.4f, standard deviation: %.4f' % (density, numpy.mean(times), numpy.std(times)))

联盟:

density: 0.05, time: 0.9846, standard deviation: 0.0440
density: 0.10, time: 1.0141, standard deviation: 0.0204
density: 0.50, time: 0.5477, standard deviation: 0.0059
density: 0.99, time: 0.3440, standard deviation: 0.0020

在集合具有相同大小的情况下，最快和最慢之间的计算时间大约相差 3 倍。此外，低密度的变化性更大。

有趣的是，对于交集(在perform_op函数中将values1 |values2替换为values1＆values2)，我们还有非恒定性能，但模式不同:

density: 0.05, time: 0.3928, standard deviation: 0.0046
density: 0.10, time: 0.4876, standard deviation: 0.0041
density: 0.50, time: 0.5975, standard deviation: 0.0127
density: 0.99, time: 0.3806, standard deviation: 0.0015

我没有测试其他集合操作。

我不明白为什么会有这样的差异。据我所知，Python 集合是通过哈希表实现的，因此只要哈希值分布良好，整数的密度就不重要。

这些不同表现的起源是什么？

Answer 1

这里有两个主要影响因素:

1. 您正在生成不同尺寸的输出；对于密集的输入，绝大多数值都会重叠，因此最终会产生更小的输出。
2. int 有一个非常简单的哈希码；它只是 int 的值。所以hash(1234) == 1234。对于密集输入，这意味着您拥有大部分连续的哈希码，没有重叠，因为这些值始终小于 set 存储桶的数量(例如，对于 100,000 个值，您有 262,144 个存储桶；当值很密集，您的哈希代码范围从 0 到 101,010，因此不会发生实际的环绕模 262,144)。更重要的是，散列码很大程度上是连续的，这意味着内存是以很大程度上连续的模式访问的(有助于 CPU 缓存获取启发)。对于稀疏输入，这不适用；您将有许多不相等的值散列到同一个存储桶(因为 0.05 情况下的 2,000,000 个值中的每一个都有 7-8 个不同的值，当有 262,144 个存储桶时，这些值将散列到同一个存储桶)。由于 Python 使用封闭散列(又名开放寻址)，因此与不相等值的存储桶冲突最终会跳过整个内存(防止 CPU 缓存提供尽可能多的帮助)来查找新值的存储桶。

演示桶碰撞问题:

>>> import random
>>> vals = random.sample(xrange(int(100000/0.99)), 100000)
>>> vals_sparse = random.sample(xrange(int(100000/0.05)), 100000)

# Check the number of unique buckets hashed to for dense and sparse values
>>> len({hash(v) % 262144 for v in vals})
100000  # No bucket overlap at all
>>> len({hash(v) % 262144 for v in vals_sparse})
85002   # ~15% of all values generated produced a bucket collision

每个发生冲突的值都必须在集合中跳跃，寻找未占用的存储桶，密集的值根本不会发生冲突，因此它们完全避免了这种成本。

如果您想要一个解决这两个问题的测试(同时仍然使用密集和稀疏输入)，请尝试使用 float (不等于 int 值) ，因为 float 哈希尝试将 int 等效的 float 哈希为与 int 相同的值)。为了避免实际相等值的不同级别，请从不重叠的值中选择输入，因此稀疏与密集不会改变生成的并集的大小。这是我使用的代码，无论密度如何，最终都会得到相当均匀的时间:

import time
import random
import numpy

def get_values(size, density, evens=True):
    if evens:
        # Divide by 100. to get floats with much more varied hashes
        vals = random.sample([x / 100. for x in xrange(0, int(size/density * 2), 2)], size)
    else:
        vals = random.sample([x / 100. for x in xrange(1, int(size/density * 2), 2)], size)
    return set(vals)

def perform_op(size, density):
    values1 = get_values(size, density)
    values2 = get_values(size, density, False)  # Select from non-overlapping values
    t = time.time()
    result = values1 | values2
    return time.time()-t, len(result)

size = 100000
for density in [0.05, 0.1, 0.5, 0.99]:
    times = [perform_op(size, density) for _ in range(10)]
    resultlens = [r for _, r in times]
    times = [t for t, _ in times]
    print('density: %.2f, mean time: %.4f, standard deviation: %.4f' % (density, numpy.mean(times), numpy.std(times)))
    print(numpy.mean(resultlens))