本文探讨了如何使用位图法对非负整数进行线性时间排序去重，并分析了在Numba加速过程中遇到的问题。我们详细解释了Python任意精度整数与Numba固定宽度有符号整数之间的差异，特别是位移操作1
位图法：一种高效的排序去重策略
在处理非负整数的排序与去重问题时，如果整数的范围不是特别大，位图（bitmask）法是一种理论上可以达到线性时间复杂度的有效策略。其核心思想是利用一个大的整数（或位数组）的每一位来表示一个数字是否存在。
基本原理：
构建位图： 遍历输入数组中的每个数字 x。通过位或操作 m = m | (1 提取排序后的唯一元素： 从最低位（第0位）开始，逐位检查 m。如果第 i 位为1，则数字 i 是一个唯一的元素。将 m 右移一位 (m = m >> 1) 并递增 i，直到 m 为0。
以下是这种策略的Python实现示例：
import numpy as npfrom time import perf_counterfrom numba import njitdef count_unique_bitmask(ls): """ 使用位图法对非负整数进行排序并去重。 该方法假设输入整数非负且在位图m所能表示的范围内。 """ ret = [] m = 0 # 初始化位图，用于标记数字的存在 # 阶段1: 构建位图 for x in ls: # 将数字x对应的位设置为1 # 例如，如果x=3，则m的第3位变为1 m = m | (1 < 0: # 只要位图m中还有位是1，就继续 if (m & 1): # 检查当前最低位（第i位）是否为1 ret.append(i) m = m >> 1 # 位图右移一位，准备检查下一位 i += 1 # 对应数字递增 return ret# 示例测试RNG = np.random.default_rng(0)# 生成一个包含大量随机非负整数的数组，最大值2^16-1，数量2^17x = RNG.integers(2**16, size=2**17) print(f"输入数组大小: {len(x)}")# 使用Numpy的np.unique进行基准测试start = perf_counter()y1 = np.unique(x)print(f"np.unique 耗时: {perf_counter() - start:.6f} 秒")# 使用纯Python实现的位图法进行测试start = perf_counter()y2 = count_unique_bitmask(x)print(f"位图法 (Python) 耗时: {perf_counter() - start:.6f} 秒")print(f"结果一致性检查: {np.array_equal(y1, y2)}")
在上述测试中，纯Python实现的位图法通常会比高度优化的 np.unique 函数慢，因为Python解释器的开销较大。为了弥补这一性能差距，开发者常会考虑使用Numba这样的JIT（Just-In-Time）编译器来加速Python代码。
Numba加速尝试与意外行为
Numba通过即时编译Python函数为机器码，可以显著提升数值计算的性能。当尝试将上述 count_unique_bitmask 函数用 @njit 装饰器进行加速时，却出现了意料之外的结果——函数返回了一个空列表。
# ... (省略导入和RNG初始化)@njit # 添加Numba JIT装饰器def count_unique_bitmask_numba(ls): """ 使用Numba加速的位图法，对非负整数进行排序并去重。 注意：此函数在特定条件下会遇到问题。 """ ret = [] m = 0 for x in ls: m = m | (1 < 0: if (m & 1): ret.append(i) m = m >> 1 i += 1 return ret# 再次测试Numba版本start = perf_counter()y3 = count_unique_bitmask_numba(x)print(f"位图法 (Numba) 耗时: {perf_counter() - start:.6f} 秒")# 此时np.array_equal(y1, y3) 将返回 False，因为y3是空列表print(f"结果一致性检查 (Numba): {np.array_equal(y1, y3)}")
为什么Numba版本会失败并返回一个空列表？这涉及到Python和Numba在整数类型处理上的根本差异。
Numba中整数表示的陷阱：有符号64位整数
Python的整数是任意精度的，这意味着它们可以表示任意大小的整数，只要内存允许。这种灵活性是以性能为代价的。为了实现高性能，Numba通常会将Python整数编译为固定宽度的机器整数类型，默认为64位有符号整数（int64）。
问题就出在这个“有符号”特性上。在64位有符号整数表示中，最高位（第63位）被用作符号位。当这个位为1时，表示一个负数。
考虑位移操作 1
当 amount 小于 63 时，1 当 amount 等于 63 时，1 当 amount 大于 63 时，结果会因为溢出而截断或行为未定义，但通常也会导致负数或0。
为了验证这一点，我们可以运行一个简单的Numba测试程序：
from numba import njit@njitdef shift_test(amount): """ 演示在Numba中1左移操作对不同位数的行为， 特别是在64位有符号整数中的符号位影响。 """ return 1 << amountprint("Numba中位移操作的行为:")for i in range(66): result = shift_test(i) print(f"{i:2d}: {hex(result)} (十进制: {result})") if i == 63: print(" --- 注意: 1 << 63 在Numba int64中变为负数 ---")
运行上述代码，你会观察到当 i 达到 63 时，shift_test(63) 返回的值是一个负数。
回到 count_unique_bitmask_numba 函数：当输入数组 ls 中包含大于等于63的数字时，例如 x = 63，执行 m = m | (1 0: 这个循环条件将立即变为 False，导致循环提前终止。由于 ret 列表在循环开始前是空的，所以最终函数返回一个空列表。
结论与注意事项
位图法限制： 这种基于单个整数位图的排序去重方法，其能处理的最大数字受限于所用整数类型的位数。在Numba默认的 int64 环境下，它只能正确处理小于 63 的非负整数。对于大于等于63的数字，位移操作会导致位图 m 变为负数，从而破坏算法逻辑。Numba整数类型： Numba为了性能优化，默认使用固定宽度的有符号整数。进行位操作时，必须充分了解其底层数据类型的限制，尤其是涉及最高位的操作。替代方案：对于小范围整数（ 如果你确定所有数字都小于63，那么位图法在Numba中可以高效工作。对于大范围整数： 如果数字范围超过63，位图法不再适用。你需要考虑其他更通用的方法：使用 np.unique： Numpy的 unique 函数底层由高度优化的C代码实现，对于大多数情况，其性能表现都非常出色且稳定。使用 set： Python的 set 数据结构天然支持去重。你可以先将列表转换为 set 进行去重，然后转换为列表并排序。Numba可以很好地处理Python的 set。使用布尔数组： 创建一个足够大的布尔数组（例如 `seen = np.zeros(
以上就是使用Numba优化位图排序去重：深入理解整数表示与潜在陷阱的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1371078.html
微信扫一扫 
支付宝扫一扫 
