Libra - 送给天秤座的你

时间:2023-06-26 来源:m.86027.cn

Libra - 送给天秤座的你

省流：一个找次品数学问题的纯前端算法 demo,TypeScript 实现算法，界面React，用到了一些现代浏览器支持的ES Module相关 feature。

传送门：源码地址 | 在线示例

因为只是一个实现算法的 Demo，并未对数据进行限制，推荐不要用太大的数据（产品数*轻重的可能数不要超过 81），否则容易卡爆。

咋回事嘞

你呀，总是能给我出点新花样

做这个东西完全是因为逛贴吧的时候被这个从知乎转来的问题难住了，一时半会儿还真想不出答案。

问题：

12 个乒乓球，有一个次品，不知轻重，用一台无砝码天平称三次，找出次品，告知轻重？

虽然是个老问题，但不妨碍我出点新花样。取名 Libra（天秤座）纯粹是因为这个想法诞生于天秤座出生日期间，又刚好是个“天平”相关的问题。

考虑到引用的出处带有一些引战成分，我先在此声明：

我不是清北的学生，未来也大概率不会去考清北的研究生
做这个 demo 是出于对数学/前端的兴趣，加上最近确实有点闲了
想出的这个求解方案建立在和我一位室友通宵讨论的基础上，并非全靠我一人所想

正文

数学/算法问题

算法的原理在源代码的readme里有更详细的介绍。

readme

核心思路是将产品编号，将完整的称取的策略抽象成一颗字典树，每个叶节点都是结论，每个非叶节点都是一个当前情况下的后续称取策略，key 为可能的称量结果，value 为该称量结果的后续处理节点，是继续称量（非叶节点）还是得出结论（叶节点）。然后，用穷举法生成树，并在穷举的基础上利用一些贪心策略对不可能/重复的情况进行剪枝，将当前称量结果下的所有产品分为可能偏重、可能偏轻、合格品、未测量四种，通过枚举从各组选取上秤的数量来剪掉等价的称取策略。只要树能在所有可能次品编号以及次品轻重情况下走到正确的结论节点，那么这棵树就是一种可行的称取方案。

显然，根据初始状态所有产品编号都对等的性质，除了无解或者只有一个产品的特殊情况，可能的字典树一定是复数个。加上树的问题又基本上避免不了递归处理，如何实现？答案是用生成器进行迭代/递归，迭代出第一个树的根节点就停止寻找。

// 部分代码nexport function* findSolution(n: number, k: number, diffectiveDifferences: DefectiveDifference[]): Generator<TreeNode> {n const allProducts = products(n);n // 核心的递归方法n function* generateFor(restCases: Case[], restK: number): Generator<TreeNode> {n //...n }n const allCases = cases(allProducts, diffectiveDifferences);n const greedyLeastK = Math.ceil(Math.log(allCases.length) / Math.log(3));n yield* generateFor(allCases, Math.min(k, greedyLeastK));n}nn// 组件内调用算法时nfor (const solution of findSolution(count, times, kinds)) {n const foundNode = connectParent(solution);n setState((s) => ({ ...s, node: foundNode, root: foundNode, message: "" }));n // 找到第一个节点，即可停止搜索n return;n}n// 在迭代结束后执行的是没找到任何节点的情况nsetState((s) => ({n ...s,n node: false,n root: false,n message: i18n["info.no.solution"],n}));n

前端问题

框架选择

知乎的前端圈天天都能看到React和Vue的党争，那我还是提一下这个问题。

是的，我选择了 React，理由是对于我这样的TypeScript用户而言出 demo 开发很快。

由于算法本身是暴力的穷举，时间复杂度高达O(n^7)（目测的循环嵌套数），对于稍大的数据会存在地狱级的性能问题（卡个半分钟不讲道理）。这种场景，框架那点DOM操作的性能优化都是杯水车薪，数据对象的计算才是性能瓶颈。一旦不小心让Vue的reactivity代理了算法里用到的数据对象，性能只会更差，反过来会成为心智负担。所以我没有选择Vue，对这类问题也不倾向于选择Vue。

最终，前端的核心代码只有一个文件，也符合我的预期，足够simple。

另一方面，我正在尝试把React移除，手操 DOM，但是不用jQuery这样的老一辈，而是直接用现代的浏览器 API，VanillaJS。有兴趣的朋友可以关注一下后续 demo 的更新。

呈现方案

关于这颗字典树的呈现方案，我想了很久。最终选择了这种选择称量结果的交互，而非整棵树的绘制或不同情况下执行逻辑的文字罗列。或许可以做得更加酷炫一点，比如选择后放大看到子节点，像俄罗斯套娃一样，但无奈赶不上天秤座最后一天的工期了。

开发/打包

没有前端开发工具链。

没有create-react-app，没有webpack，没有vite，没有parcel，没有snowpack。只有一个静态资源服务器serve，以及编译TypeScript非常快的esbuild。够用了，真的够用了，毕竟没有HMR和react-fast-refresh插件一样能写React。

没有依赖打包器。

没有rollup，没有gulp，更没有前面的工具链内部集成的打包。

国内 GitHub 访问慢，既要白嫖GitHub Pages的静态服务器资源，又要让流量尽可能走国内 CDN 提升体验，怎么办呢？

为了解决这个问题，我写了一个借助<script type="importmap">实现浏览器内直接引入npm包的工具库es-modularize，目前也还在探索更多的优化。有了他，依赖打包都可以免了，更甚者，等proposal-type-annotations过了，esbuild/tsc等TypeScript编译器都能免了，整个项目只需要装一个serve就能跑，上GitHub Pages都不用走Actions的构建。当然，为了浏览器兼容性，也有捆绑react代码的 fallback 版本，打包用的是esbuild。

状态管理

没有状态管理。

是的，没有redux，没有mobx，没有rxjs，没有zustand，没有jotai。没有状态管理，一样可以写有状态的非内容型网站。

在这里我发表一下我对前端圈天天讨论的状态管理问题的统一回复：状态管理是一个伪需求，需要 share 的 state 不是组件状态，而是属于你解决问题的 domain。你需要的是像remesh这样的规范业务代码与帮助划分问题域的工具库，而非 general purpose 的 state management for JavaScript application。

remesh

整个 App 只有一个useState作为全部的状态——仅仅是当前的生成树和当前所在的节点信息需要存一个状态。

Libra 的表单不需要状态。他们是纯粹的内容填写，只需要在提交表单时读取他们——通过submit事件+FormData一键读取整个表单是再合适不过了。demo 的代码里加了一些类型校验，但他们也不是必要的——下个轮子，可能就是做这个。

此外，遵循严格的immutable，本身就是一种『自动』的管理。怕性能问题，那就加memo，不加白不加。demo 中也有没加memo的组件，是因为当 React 需要重渲染那些组件时必然是props变了，memo反过来是负优化。

样式表

没有 CSS 预处理器，样式都是纯粹的 CSS。

引入 UI 库的方式不一定是装一个依赖包或者 CDN，也可以直接去 UI 库网站的控件实例上复制元素样式来用——当然别忘了加 License 注释以保护开源方的版权。

国际化

国际化靠的是直接根据页面参数动态import文案json文件。JSON 文件的编写，通过JSON schema进行约束，提示字段。之所以没有按照习惯从pathname里获取国际化参数，而是从search里获取，是因为对 GitHub Pages 的多路由导航到同一个文件的方案还不太熟，外加要赶上天秤座最后一天的工期就鸽了。

人的算力不及计算机。哪怕是清北学生智商在线，也不如计算机的求解来得简单粗暴。但是如何让计算机帮助求解问题，是一个需要智商的方法论。

很喜欢《理科生坠入情网，故尝试证明》第二季里的一句话：