主要观点:
- 开始玩 1975 年的《221B 贝克街 - 大侦探游戏》,包含 75 个独特谜题和线索书,目标是收集线索解谜。
- 实际讨论旅行商问题(TSP),如从贝克街出发访问 15 个地点并返回的最优路径,存在多种复杂情况,如不同入口出口、快速旅行等,设置正确初始距离困难,后用 Held–Karp 算法求解,初始实现约 6.5 秒得出 16 个城市的最优路径。
- 对该问题的兴趣分为对游戏和代码两部分,实际玩游戏时不常使用最优路径,因为太可预测且可能忽略谜题信息,有时甚至忽略骰子直接跳转。
- 因想改进代码将其转为有用模块,选择 WebAssembly 学习,过程艰难,调试困难,通过将一些学习成果回传至 JavaScript 提升性能,当前 WebAssembly 实现 16 个城市的问题约 32.5 毫秒,比最初快约 200 倍,但 WebAssembly 比 JavaScript 慢约百分之几,可能是优化不佳、WebAssembly 本身效率不如预期或 Node.js/V8/TurboFan 效率高。
关键信息:
- 游戏相关:有 75 个谜题,15 个地点,骰子移动,存在快速旅行等规则。
- 代码相关:最初用 JavaScript 实现 Held–Karp 算法,后改用 WebAssembly 提升性能,遇到诸多困难,如调试、内存处理等。
重要细节:
- 不同地点的入口出口情况,如 docks 有两个入口,park 有三个入口。
- WebAssembly 无 2D 数组概念,需用连续内存块和计算偏移量。
- 关于 JavaScript 性能的讨论,如对简单表达式的处理、数组实际是字典导致的性能问题等,以及 V8 编译器的优化机制。
**粗体** _斜体_ [链接](http://example.com) `代码` - 列表 > 引用。你还可以使用@来通知其他用户。