rad*_*o23 5 python performance numpy
import numpy as np\nimport itertools\n\na = np.array([ 1, 6, 7, 8, 10, 11, 13, 14, 15, 19, 20, 23, 24, 26, 28, 29, 33,\n 34, 41, 42, 43, 44, 45, 46, 47, 52, 54, 58, 60, 61, 65, 70, 75]).astype(np.uint8)\nb = np.array([ 2, 3, 4, 10, 12, 14, 16, 20, 22, 26, 28, 29, 30, 31, 34, 36, 37,\n 38, 39, 40, 41, 46, 48, 49, 50, 52, 53, 55, 56, 57, 59, 60, 63, 66,\n 67, 68, 69, 70, 71, 74]).astype(np.uint8)\nc = np.array([ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,\n 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33,\n 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50,\n 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67,\n 68, 69, 70, 71, 72, 73, 74, 75]).astype(np.uint8)\n我想获得 3 个数组的笛卡尔积，但我不希望一行中的任何重复元素[1, 2, 1]无效，并且只有这两个元素之一有效[10, 14, 0]，或者[14, 10, 0]因为 10 和 14 都在a和中b。
def no_numpy():\n combos = {tuple(set(i)): i for i in itertools.product(a, b, c)}\n combos = [val for key, val in combos.items() if len(key) == 3]\n%timeit no_numpy() # 32.5 ms \xc2\xb1 508 \xc2\xb5s per loop\n# Solution from (/sf/answers/780265181/)\ndef cartesian_product(*arrays):\n broadcastable = np.ix_(*arrays)\n broadcasted = np.broadcast_arrays(*broadcastable)\n rows, cols = np.prod(broadcasted[0].shape), len(broadcasted)\n dtype = np.result_type(*arrays)\n\n out = np.empty(rows * cols, dtype=dtype)\n start, end = 0, rows\n for a in broadcasted:\n out[start:end] = a.reshape(-1)\n start, end = end, end + rows\n return out.reshape(cols, rows).T\n\ndef numpy():\n combos = {tuple(set(i)): i for i in cartesian_product(*[a, b, c])}\n combos = [val for key, val in combos.items() if len(key) == 3]\n%timeit numpy() # 96.2 ms \xc2\xb1 136 \xc2\xb5s per loop\n我的猜测是在 numpy 版本中将 转换np.array为集合是它慢得多的原因，但严格比较时获得初始产品cartesian_product比 快得多itertools.product。
是否可以以任何方式修改 numpy 版本以超越纯 python 解决方案，或者是否有另一种解决方案优于两者？
\n虽然第一个解决方案比第二个解决方案更快，但效率相当低，因为它创建了大量临时 CPython 对象（每项至少 6 个itertools.product）。创建大量对象的成本很高，因为它们是由 CPython 动态分配和引用计数的。Numpy 函数cartesian_product非常快，但对结果数组的迭代非常慢，因为它创建了大量 Numpy 视图并在numpy.uint8而不是 CPython上进行操作int。Numpy 类型和函数为非常小的数组带来了巨大的开销。
Numpy 可以用来加速这个操作，如 @AlainT 所示，但这并不是一件容易的事，Numpy 并不能解决此类问题。
一种解决方案是使用Numba更有效地自行完成工作，并让 Numba 的JIT 编译器优化循环。您可以使用 3 个嵌套循环来高效生成笛卡尔积的值并筛选项目。字典可用于跟踪已经看到的值。3 项的元组可以打包为一个整数，以减少内存占用并提高性能（因此字典可以更好地适应 CPU 缓存并避免创建缓慢的元组对象）。
这是生成的代码：
import numba as nb
# Signature of the function (parameter types)
# Note: `::1` means the array is contiguous
@nb.njit('(uint8[::1], uint8[::1], uint8[::1])')
def with_numba(a, b, c):
seen = dict()
for va in a:
for vb in b:
for vc in c:
# If the 3 values are different
if va != vb and vc != vb and vc != va:
# Sort the 3 values using a fast sorting network
v1, v2, v3 = va, vb, vc
if v1 > v2: v1, v2 = v2, v1
if v2 > v3: v2, v3 = v3, v2
if v1 > v2: v1, v2 = v2, v1
# Compact the 3 values into one 32-bit integer
packedKey = (np.uint32(v1) << 16) | (np.uint32(v2) << 8) | np.uint32(v3)
# Is the sorted tuple (v1,v2,v3) already seen?
if packedKey not in seen:
# Add the value and remember the ordered tuple (va,vb,vc)
packedValue = (np.uint32(va) << 16) | (np.uint32(vb) << 8) | np.uint32(vc)
seen[packedKey] = packedValue
res = np.empty((len(seen), 3), dtype=np.uint8)
for i, packed in enumerate(seen.values()):
res[i, 0] = np.uint8(packed >> 16)
res[i, 1] = np.uint8(packed >> 8)
res[i, 2] = np.uint8(packed)
return res
with_numba(a, b, c)
以下是我的 i5-9600KF 处理器上的结果：
numpy: 122.1 ms (x 1.0)
no_numpy: 49.6 ms (x 2.5)
AlainT's solution: 49.0 ms (x 2.5)
mathfux's solution 34.2 ms (x 3.5)
mathfux's optimized solution 7.5 ms (x16.2)
with_numba: 4.9 ms (x24.9)
所提供的解决方案比迄今为止最慢的实现快约 25 倍，比迄今为止提供的最快实现快约 1.5 倍。
当前的 Numba 代码受到 Numba 字典操作速度的限制。可以使用更多低级技巧来优化代码。解决方案是用大小为压缩的布尔数组（1 项 = 1 位）替换字典256**3/8，以跟踪已经看到的值（通过检查第packedKeyth 位）。res如果未设置提取位，则可以直接添加打包值。这需要res预先分配到最大大小或实现指数增长的数组（如list在 Python 或std::vectorC++ 中）。另一种优化是对列表进行排序并使用平铺策略来提高缓存局部性。这种优化远不容易实现，但我希望它们能够大大加快执行速度。
如果您计划使用更多数组，那么哈希映射可能会成为瓶颈，并且位数组可能会很大。虽然使用平铺确实有助于减少内存占用，但您可以使用布隆过滤器大幅加快实现速度。这种概率数据结构可以通过跳过许多重复项来加快执行速度，而不会导致任何缓存未命中，并且内存占用较低。您可以删除大部分重复项，然后对数组进行排序，然后删除重复项。关于您的问题，基数排序可能比通常的排序算法更快。