应用分区方法进行动态规划

Question

我有一个小型的宠物项目。其中最大的挑战之一是为给定的游戏板生成随机船舶组合。事实证明，这不是一项简单的任务，我必须应用动态规划才能找到结果。这需要相当长的时间，尤其是在没有解决方案的情况下。

    static placeShips(col: number, row: number, placedShips: Ship[], shipsToPlace: ShipTypeAbstract[]): Ship[]|null {
        Grid.iter++
        if (shipsToPlace.length === 0) {
            return placedShips
        }
        const grid = Grid.initGrid(col, row)
        placedShips.forEach((ship: Ship) => {
            grid.placeShipWithSurrounding(ship)
        })

        const types = [...shipsToPlace]
        const shipType = types.pop()
        const orientations = Math.random() > 0.5 ? [true, false] : [false, true]
        for (const isHorizontal of orientations) {
            const maxCol = isHorizontal ? grid.cols - shipType.getSize() : grid.cols
            const maxRow = isHorizontal ? grid.rows : grid.rows - shipType.getSize()
            const randomRowOffset = Math.floor(Math.random() * maxRow)
            for (var r = 0; r < maxRow; r++) {
                var rr = r + randomRowOffset
                if (rr >= maxRow) {
                    rr -= maxRow
                }
                const randomColOffset = Math.floor(Math.random() * maxCol)
                for (var c = 0; c < maxCol; c++) {
                    if (Grid.iter > row * col * 50) {
                        throw new Error(`In ${Grid.iter} iteration we weren't able to fit all ships`)
                    }

                    var cc = c + randomColOffset
                    if (cc >= maxCol) {
                        cc -= maxCol
                    }
                    const ship = new Ship(new Position(cc, rr), isHorizontal, shipType)

                    if (grid.canPlace(ship) === true) {
                        const pl = [...placedShips]
                        pl.push(ship)
                        const res = Grid.placeShips(col, row, pl, [...types])
                        if (res !== null) {
                            return res
                        }
                    }
                }
            }
        }

        return null
    }

我将尽最大努力优化这段代码（将添加记忆、预排序输入船舶数组、优化循环等），但除非我找到完全不同的方法，否则它总是很耗时。

我运行了性能测试并得到了预期的结果：

$ wrk -t 10 -c50 -d10s --timeout 1m http://localhost:3000/shuffle/PdgFRR
Running 10s test @ http://localhost:3000/shuffle/PdgFRR
  10 threads and 50 connections
  Thread Stats   Avg      Stdev     Max   +/- Stdev
    Latency     3.65s     1.54s    5.74s    70.41%
    Req/Sec     2.06      2.18    10.00     92.63%
  98 requests in 10.09s, 51.22KB read
Requests/sec:      9.71
Transfer/sec:      5.08KB

对于或多或少棘手的船舶组合，它每秒只能处理 10 个请求。据我所知（我是一名PHP开发人员，宠物项目的目标是与nodejs相处）该方法阻塞了主线程。

为了解决这个问题，我想应用分区方法（将小块工作传递给 setTimeout 或 setImmediate 函数），但问题是我不知道如何将动态编程循环拆分为块。有什么线索可以实现这个目标吗？

附注我认为我做错了什么，因为这么简单的游戏需要大量的计算。还有很多更奇特的游戏可以动态生成整个游戏世界。例如，国际象棋每回合计算数千步。

Answer 1

您的解决方案是一种递归蛮力解决方案。在任何语言中它都会很慢。当然，如果您不经常分配动态内存或者使用 c/c++/rust 等快速语言重写它，它会更快。可以在 Nodejs 内部导入和使用本机模块功能。

---

将计算分块

如果您希望相对容易地将单个复杂任务分成多个部分，您可以执行以下操作：将所有类方法替换为

async

，例如

static async placeShips(

。在这种情况下，这些函数返回将被包装在

Promise

中，因为现在方法内部理论上可以是异步的并且不会阻塞主线程。在异步函数内部，可以使用

await

关键字从 Promise 中解开值。

const res = await Grid.placeShips(col, row, pl, [...types]);

这样，所有的实现部分都将通过 Promise 进行调度，这意味着微任务 = 比宏任务具有更大优先级的任务。

要插入一些优先级较低的调度机制，我们可以使用

setTimeout

并将其包装到 Promise api 中，以便在异步函数中轻松使用它

const waitNextEventLoopCycle = () => new Promise(resolve => setTimeout(resolve, 0));
// shorter but less explicit implementation
const waitLoop = () => new Promise(setTimeout);

以及每当您决定对当前进程进行小幅停止时的使用情况（最好不要太频繁，因为每次使用都会稍微减慢该作业的执行速度）

await waitLoop()

这种技术在现实世界中有一点用处，但如果你可以避免它 - 你最好避免它。它在递归解决方案中也并不完美，因为很难找到想要停止的点，而不需要执行太多次。例如，如果您有数十亿次迭代循环，那么您可以在每 1 亿次时停止，这将是非常明显和有效的。

---

值得尝试的是分配一个单独的线程或进程来处理特定查询的任务。模块

node:worker_threads

（线程）、

node:child_process

或

node:cluster

（进程）可以在这里提供帮助。

然而，在现实世界中，大多数项目（在某些情况下，因为很多开发人员不熟悉 js 或 Nodejs 平台）都会产生一堆类似的 NodeJS 服务器进程，并且使用其他一些软件来为这些进程分派工作.