算法演绎 | 巧妙的 Completer 完成器

0. 缘起

最近几个月接触了些算法题，然后想个有趣的点子:

是否可以用 Flutter 做一个交互应用，可视化 地展示算法执行过程中的变量的信息。

比如拿一个最简单的累加算法来说，启动算法之后，每次点击下一步，界面上会展示出该步对应的变量信息。就可以可视化地呈现出一个算法运算过程中变量的变化情况。

int sum(int count) {
  int sum = 0;
  for (int i = 0; i < count; i++) {
    sum = sum + i;
  }
  return sum;
}

当算法执行完毕后，每一步都会被记录，可以左右切换，查看对应步数的变量情况(如下右图)：

算法演绎过程	演绎结束后切换查看帧

---

1. 对数据的定义

帧 Frame ： 记录算法执行一步中的所有数据 节点 Node : 一帧中的变量信息单体数据

目前的节点 Node 只是展示变量名和对应的值，未来可以拓展其他类型的节点，自己绘制需要展示的内容。一帧 Frame 由若干个 Node 构成：

class Frame{
  final List<Node> nodes;

  Frame(this.nodes);
}

class Node {
  final String name;
  final String value;

  Node({
    required this.name,
    required this.value,
  });
}

数据定义完了，接下来重点就是如何在一个方法运行期间，收集每一帧的数据。

---

2. 对数据的收集

拿 sum 算法来说，每一步执行时机我们是知道的。如下所示，我们可以在第四行下方得到每帧的数据：

这样很自然地可以想到：可以执行一下 sum 方法，然后用的列表收集所有的 Frame 数据。但这样有一些缺陷，一方面：我们无法控制算法执行的过程，无法中断算法；另一方面, 这样会一次性把所有的 Frame 收集起来，如果是上百亿的数据，内存会吃不消。

int sum(int count) {
  int sum = 0;
  for (int i = 0; i < count; i++) {
    sum = sum + i;
    /// 收集当前帧信息
    List<Node> nodes = [
      Node(name: 'i', value: i.toString()),
      Node(name: 'sum', value: sum.toString()),
      if (i == count - 1) Node(name: 'return', value: sum.toString()),
    ];
    Frame frame = Frame(nodes);
  }
  return sum;
}

---

有什么方式，可以暂停代码的执行，并且可以在之后的交互中恢复执行呢？答案是 Completer，它可以让代码进行异步地等待，直到 Completer 对象的完成。这里将充分发挥 Completer 的价值，让你对它有深刻地认知。

代码处理如下所示，定义一个 AlgoFrameCallback 的异步回调函数，向外界暴露算法执行过程中的 Frame 数据。回调返回 bool 值，返回 true 时表示希望停止算法，直接返回。由于这里通过 await 等待异步回调执行完毕，所以每一帧都会异步阻塞而暂停，等待下一步的时异步任务完成的时机。

typedef AlgoFrameCallback = Future<bool> Function(Frame frame);

Future<int?> sum(int count, AlgoFrameCallback callBack) async {
  int sum = 0;
  for (int i = 0; i < count; i++) {
    sum = sum + i;
    // 回调本次循环的变量信息
    /// 收集当前帧信息
    List<Node> nodes = [
      Node(name: 'i', value: i.toString()),
      Node(name: 'sum', value: sum.toString()),
      if (i == count - 1)Node(name: 'return', value: sum.toString()),
    ];
    Frame frame = Frame(nodes);
    bool end = await callBack(frame);
    if(end) return null;
  }

  return sum;
}

---

3. Completer 的使用

下面代码中 startSumProgram 方法会启动 sum 算法触发的 Frame 回调，通过 _onFrameTick 异步方法进行监听。每次接收到 Frame 时，将其加入到 _frames 列表中，并更新界面；然后返回 _completer.future，就可以让 sum 中的回调逻辑异步阻塞，来等待 _completer 的完成。

final List<Frame> _frames = [];
final int _counter = 10;
Completer<bool>? _completer;

void startSumProgram() {
  _completer?.complete(true);
  _completer = Completer();
  _frames.clear();
  sum(_counter, _onFrameTick);
}

Future<bool> _onFrameTick(Frame frame) {
  _frames.add(frame);
  setState(() {});
  return _completer!.future;
}

---

想要执行到下一帧，需要让 _completer 完成，也就是下一步时需要做的工作。点击时触发 _next 方法，使用 _completer#complete 方法完成，然后重新创建下一帧的完成器，继续阻塞下一帧的前进，从而完成需求。

void _next() {
   _completer?.complete(false);
   _completer = Completer();
}

---

4. 算法运行状态

ProgramStatus 是用于记录算法运行状态的枚举，用于确定运行按钮的激活状态，以及交互过程中的流程控制。比如在算法运行(running)的过程中，无法后退；算法演绎结束，可以根据记录的帧来前进和后退。

演绎中	演绎结束

enum ProgramStatus {
  none,
  running,
  success,
}

---

我们需要在不同的时机维护 ProgramStatus状态的正确性，比如开启算法是置为 running 状态:

当算法运行完毕，置为 success 状态。这样就可以根据算法的运行状态，维护界面构建的逻辑。

---

根据算法运行的状态，也可以控制业务逻辑的代码；比如下一帧方法在算法完成后，需要通过 _frames 列表根据激活索引来更新当前帧。因为算法运行完毕，_completer 的完成就无法驱动下一帧了。

void _next() {
  if(programStatus==ProgramStatus.success){
    activeFrameIndex++;
    setState(() {});
  }else{
    _completer?.complete(false);
    _completer = Completer();
  }
}

late int activeFrameIndex = _counter-1;

Frame get activeFrame{
  if(programStatus==ProgramStatus.success){
    /// 结束演绎，通过索引查询帧记录
   return _frames[activeFrameIndex];
  }
  return _frames.last;
}

到这里 ，一个最简单的算法演绎就完成了。可以在界面上展示算法执行过程中的变量变化细节。这样对算法的理解非常有帮助，当然这只是一个开始，验证了算法演绎的可行性。后续还会构思一下根据 Frame 来自己绘制信息，这样数组、队列、栈、链表、二叉树等相关算法就可以可视化展示。那到这里本文就结束啦，谢谢观看~