From 7edf272e78b6a3cb2cc42a1bb9d64ccd980e21c3 Mon Sep 17 00:00:00 2001 From: Eltrac Date: Sat, 14 Jun 2025 00:35:28 +0800 Subject: docs: update draft Former-commit-id: 0581645e685bbc37bdd4885383a241e0f996f279 --- content/posts/weekly/33.md | 3 +- ...260\203\345\272\246\347\256\227\346\263\225.md" | 134 +++++++++++++++++++++ 2 files changed, 136 insertions(+), 1 deletion(-) create mode 100644 "content/\344\270\200\344\270\252\347\224\265\346\242\257\350\260\203\345\272\246\347\256\227\346\263\225.md" (limited to 'content') diff --git a/content/posts/weekly/33.md b/content/posts/weekly/33.md index f9ccb542..3a945576 100644 --- a/content/posts/weekly/33.md +++ b/content/posts/weekly/33.md @@ -56,12 +56,13 @@ PPS. 我喜欢 Apple Music 的无缝切换，效果真的很惊艳，虽然有 奇点（Singularity）是一个科幻小说家创造的概念，用来描述一个 AI 开始爆发式增长的时间节点。Sam Altman 在这篇文章中指出，奇点可能要比想象中更「缓和」和「平滑」——如果我们向 2020 年的人描述 2025 年的 AI 发展，那听起来可能不太现实，但实际上 AI 达到现在的程度确实只经过了五年。 -我很认可的一个观点是，Sam Altman 认为 AI 是一种**工具**，暗示人类依旧是主体。他指出，未来人人都能创造软件和艺术，但仍然会有专家和普通人的区分，只要专家也愿意接受这种新工具的话。在我看来，创造软件的能力与水平高低无关，创造艺术的能力与审美高低无关；不只是 AI，任何一种技术发展，在降低某一门槛的同时，也在提高上限和好的标准，提高平均水平的同时最高值也被提高了。很多人意识不到人是工具的使用者，自己想法的贫瘠和灵魂的无趣无法被技术发展解决——我仍然觉得 [AI 正在让人变得前所未有地自以为是](/posts/ai-正在让人变得前所未有地自以为是/)。 +我很认可的一个观点是，Sam Altman 认为 AI 是一种**工具**，暗示人类依旧是主体。他指出，未来人人都能创造软件和艺术，但仍然会有专家和普通人的区分，只要专家也愿意接受这种新工具的话。在我看来，创造软件的能力与水平高低无关，创造艺术的能力与审美高低无关；==不只是 AI，任何一种技术发展，在降低某一门槛的同时，也在提高上限和好的标准，提高平均水平的同时最高值也被提高了==。很多人意识不到人是工具的使用者，自己想法的贫瘠和灵魂的无趣无法被技术发展解决——我仍然认为 [AI 正在让人变得前所未有地自以为是](/posts/ai-正在让人变得前所未有地自以为是/)。 此外，Sam Altman 反复强调 AI 会提高整个社会的生产力，包括科研，人类社会的发展速度会越来越快，呈指数级增长。不过，我还不太能想明白的是：为什么要追求快？以及发展究竟有没有尽头？有没有最高值？ [#AI](/tags/ai/) [#技术](/tags/技术/) + ## 💡 新知复盘 diff --git "a/content/\344\270\200\344\270\252\347\224\265\346\242\257\350\260\203\345\272\246\347\256\227\346\263\225.md" "b/content/\344\270\200\344\270\252\347\224\265\346\242\257\350\260\203\345\272\246\347\256\227\346\263\225.md" new file mode 100644 index 00000000..41bd4190 --- /dev/null +++ "b/content/\344\270\200\344\270\252\347\224\265\346\242\257\350\260\203\345\272\246\347\256\227\346\263\225.md" @@ -0,0 +1,134 @@ +--- +title: 一个电梯调度算法 +subtitle: +tags: + - 计算机 + - 算法 +related_cards: +mentioned_books: +date: 2025-06-13T23:19:00 +categories: +banner: +draft: true +toc: true +--- + +作为一个程序员，我在博客上写的技术文章还是太少了，原因大概有两个：一是自己的技术水平还不足以产出太多原创内容；二是觉得计算机领域的知识很难写成所有人都能读懂的文章——总之就是，不想写枯燥的操作教程，也不想在博客上复制粘贴代码。不过最近倒是有了一些可以成文的想法。 + +[搬家](/posts/逃离群居生活/)之后，我每天都要乘电梯。尽管公寓楼的人流量比较小，基本不会出现与其他使用者争夺电梯资源的情况，但就算是这样，楼栋的电梯调度方式依然让我感到迷惑。这几天我一直尝试搞清楚电梯的运作模式，想着能不能用伪代码的方式表示出来，甚至做一些改进。好巧不巧，最近关注的一个博主就发了一篇有关电梯交互和调度算法的[文章](https://blog.codingnow.com/2025/06/elevator.html)，我了解到**几乎每一个需要乘电梯上班的程序员都思考过这个问题**，还挺奇妙的。 + +## 用户如何与电梯交互 + +回想一般坐电梯的过程：在某一层按下电梯按钮——电梯来到你所在的楼层——进入电梯后按下楼层按键——电梯带你前往你想要前往的楼层——你走出电梯，结束。 + +先把乘坐电梯的人都抽象为用户（`User`），电梯就表示为 `Elevator`，方便之后的描述。在上述交互过程中，用户会向系统输入两个指令： + +1. 在进入电梯前按下按钮，表示自己需要**向上**还是**向上** +2. 在进入电梯后按下按钮，表示自己需要去**哪一层** + +将第一个指令命名为 `Direction`，第二个指令命名为 `Destination` 或 `to`。除了这两个输入，影响电梯行为的其实还有用户所在的楼层，命名为 `Location` 或 `from`，也作为输入的一部分传给电梯的相关模块。 + +表示为伪代码： + +```javascript +user.getDirection() +user.getDestination() +user.getLocation() +``` + +电梯的交互逻辑就是这样。[云风](https://blog.codingnow.com/2025/06/elevator.html)在他的文章中提出可以用「召唤按钮」代替常见的上和下两个按键，这个可以先搁在一边，回头再看看。 + +电梯的调度算法就需要处理这三个输入，然后确定电梯的移动方式，即向上移动还是向下移动，途中在哪个楼层停下并开门。电梯本身的属性也要考虑到，包括电梯目前所在的楼层、是否可以移动（故障、超载或厢门未关闭时不能移动）。 + +```javascript +elevator.getCurrentFloor() +elevator.isMovable() +``` + +如果电梯正在响应一个用户的请求时收到了另一个用户的请求，应该先完成上一个用户的请求，还是想办法同时满足两个用户的请求，也是需要考虑的问题。同样地，这个问题先放一放，先实现基本的逻辑再说。 + +## 单用户单电梯的情况 + +调度电梯就是决定电梯如何移动，在何时调用哪一部电梯的过程。对于单部电梯来说，调度过程分为两步，也就是接和送。 + +### 接 + +假设电梯有一个 `move()` 方法，输入正数向上移动一定楼层，输入负数向下移动一定楼层。要移动到用户所在的楼层，就可以简单地表示为： + +```javascript +elevator.move(user.getLocation() - elevator.getCurrentFloor()) + +// 这显然可以封装为一个单独的函数 +elevator.moveTo = (location) => { + this.move(location - this.getCurrentFloor()) +} +``` + +使用 `moveTo()` 方法的时候就不需要再考虑电梯当前所在的位置了，因为已经被封装好了。这么看来，在单用户的情况下，单个「召唤按钮」的方案的确可以代替上和下两个按钮的方案，当用户按下按钮，只需要执行 `elevator.moveTo(user.getLocation())` 就可以了，在算法层面完全不需要考虑用户在一开始按的是向上还是向下。 + +### 送 + +送的步骤也很简单，用户进入电梯并输入目的地后，只需要执行： + +```javascript +elevator.moveTo(user.getDestination()) +``` + +似乎讲了一堆废话，单用户单电梯的情况就是很简单嘛！ + +## 单用户多电梯调度 + +这更贴近我的情况，我每天都在乘电梯的时候好奇：为什么我按下了左边的电梯，响应请求的却是另一部电梯？明明左边那部电梯离我更近。 + +虽然看起来每部电梯都有各自的物理按键，但两部电梯的控制是相通的。在算法层面，用户与两部电梯是同时交互的，而不是单独地给一部电梯下达了命令。我认为这是合理的，如果有一部电梯更近，而用户按了更远的那一部，或者如果用户按下的那一部电梯正在被使用，而另一部是空闲的，让用户独立操作某一部电梯就不是什么好事。 + +总而言之，在不止一部电梯的情况下，我们依然只需要考虑单一的输入。 + +### 接 + +在有多部电梯的情况下，只需要调度一部电梯接送用户。为了最小化用户的等待时间，提高效率，选择距离用户最近的电梯就是最佳方案。由于我们正在考虑单用户的情况，所以不存在电梯繁忙、正在运送其他用户的情况。 + +这时就不能直接让 `elevator` 对象响应请求了，可能需要一个额外的电梯调度器（`elevatorScheduler`）决定让那一部电梯前去接送用户。这个调度器应该能够访问系统中所有的电梯，对比他们与用户的距离，然后派遣最近的那部电梯。 + +```javascript +// in 'elevatorScheduler' +const elevators = this.getElevatorArray() +const userLocation = user.getLocation() + +let closestElevator = null + +for (let elevator of elevators) { + const thisDistance = userLocation - elevator.getCurrentFloor() + const closetDistance = userLocation - closestElevator.getCurrentFloor() + + if (!closestElevator || cloestDistance > thisDistance) { + closestElevator = elevator + } +} + +closestElevator.moveTo(userLocation) +``` + +### 送 + +由于接到用户之后，任务就完全交给其中一部电梯了，其他电梯则不需要考虑。所以送的步骤还是和「单用户单电梯的情况」相同，在此不赘述。 + +## 多用户单电梯调度 + +我记得有一次出门，我和家人忙忙慌慌地收拾东西，把电梯一直占着，过了好久我们才下楼，走出电梯门的时候发现楼下有两个人已经不耐烦到坐在地上刷手机了，愧疚感顿时涌上心头。用户不止一个，而资源访问是互斥的，就会出现这种情况（好在电梯应该不会有死锁问题）。 + +电梯显然不能及时响应每一个用户的请求，当一个用户正在占用资源时，就不得不等待另一个用户释放资源。不过，电梯如何才算被占用呢？事实上，只有电梯厢门打开或准备打开时才算被占用，因为电梯在接和送的过程其实都可以停靠。比如，有人从一楼前往五楼，而我打算从三楼前往四楼；当电梯正在从一楼向上移动时，我在三楼按下按钮，电梯理应响应我的请求，在三楼停下打开门；当我进入电梯按下四楼按钮，它也理应在四楼停下开门让我出去，然后再送另一个用户去五楼。 + +在多用户的情况下，单个「召唤按钮」的模式就不那么好用了。还是那个例子，当有人从一楼前往五楼，我依然在三楼，但我打算下行前往一楼。这个时候，电梯不应该给我开门，应该在送完去五楼的用户之后返回时再给我开门。如果没有上行和下行按钮的区分，电梯就无法在接送时确定要不要响应用户请求，以及何时响应用户请求。 + +### 接 + + + +### 送 + +## 多用户多电梯调度 + +### 接 + +### 送 -- cgit v1.2.3