Python中是否有非O(n²)的快速方法从整数矩阵生成布尔矩阵？

时间复杂度下界说明 #

不存在时间复杂度低于O(n²)的可行方案：n×n矩阵包含n²个独立元素，每个元素的正负判断没有前置依赖关系，必须完成所有元素的遍历和判断才能得到完整的布尔矩阵，因此该问题的理论时间复杂度下界就是O(n²)。你觉得现有方案慢，本质是实现的常数项过高，而非时间复杂度量级的问题。

实际运行速度优化思路（均为降低常数项，提升效果明显） #

• 向量化运算优化
  优先使用成熟科学计算库的向量化操作，底层为编译型语言实现，比手写解释型语言的嵌套循环常数项低几个数量级。以Python为例，使用numpy实现的代码如下：

  import numpy as np
  # 输入整数矩阵
  matrix_int = np.array([[-5,-8,6],[4,6,-9],[7,8,9]])
  # 一行完成转换，得到布尔矩阵
  matrix_bool = matrix_int > 0
  # 如需转换为Python原生嵌套列表，补充.tolist()即可
  # matrix_bool = matrix_bool.tolist()
  

• 内存访问优化
  如果你用C/C++/Rust等编译型语言手动实现，注意匹配矩阵的内存存储顺序遍历：行优先存储的矩阵就按行逐元素遍历，列优先的就按列遍历，尽可能减少缓存失效，通常能带来30%~100%的速度提升。
• 位压缩存储优化
  如果你的使用场景允许批量访问布尔结果，可以把输出的布尔值按bit压缩存储，比如每8个布尔值存入1个uint8类型变量，最终内存占用仅为常规布尔数组的1/8，缓存命中率更高，适合超大规模矩阵的转换场景。
• 并行计算优化
  面对10^4 × 10^4以上规模的超大矩阵时，可以将矩阵拆分为多个子块，用多线程分别处理不同子块的转换逻辑，多核CPU下能得到接近核心数倍数的速度提升。

内容的提问来源于stack exchange，提问作者JohnPers