如何借用内存

主要观点:2014 年发现一种有超能力的新算法,能利用已被其他重要数据填满的内存,虽神奇但不实用。作者实现了该算法的版本,用于解决有向图可达性问题,仅用 O(log n)普通内存(实际为常量,限于少于 232 个节点的图),其余为输入和 O(n3 log n)位“借用”内存,运行时间约为 Θ(n8)。
关键信息

  • 算法描述:通过透明计算,添加结果到存储在内存中的值,可后期恢复,如 add_reachability 函数通过添加或减去计算结果到借用内存数组来表示可达性。
  • 三个技巧:将加法转换为旋转(rotate_array函数)、乘法运算(通过一系列复杂操作实现)、与零比较(利用旋转操作实现类似与零比较的效果)。
  • 代码实现:包含两个相互递归的子例程 add_reachabilityrotate_by_reachability,用多种技巧实现算法功能,还介绍了在 C 语言中对算法的重新实现以解决运行时栈问题,提供了下载的源代码及编译方法。
    重要细节
  • 原算法更通用,可用于解决其他问题如计算矩阵行列式等,仍仅用 O(log n)普通非借用内存。
  • 该算法虽有诸多限制(如运行慢、不能用于所有程序、不能同时使用借用内存的程序等),但能利用借用内存仍很有趣,作者实现它只是为了好玩。
  • 在 C 语言实现中,通过重新实现算法避免使用运行时栈,用两个 64 位整数代替,每个栈帧仅需 2 位,可管理 64 个帧,适用于小于 232 个节点的图,且运行似乎更快,但更难理解。
阅读 3
0 条评论