教你使用 G2 上手算法可视化

学习算法是每个程序员的必经之路，但如何快速、高效的理解并掌握算法却不是一件容易的事情。算法可视化能更直观了解算法背后的思想和逻辑，这里教大家使用 G2 可视化语法库进行算法可视化。

算法实现

下面是冒泡排序的 JavaScript 实现，但有所区别的是，我们稍微进行了改造，使其成为一个生成器函数，并在每次进行元素交换操作后生成数据快照，同时使用 swap字段来标识当前参与交换的元素。

// >>> 改造前
function bubbleSort(arr) {
  let n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    for (let j = 0; j <= n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

// >>> 改造后
function* bubbleSort(arr) {
  let n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    for (let j = 0; j <= n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
// >>> 注意这行代码
      yield arr.map((a, i) => ({
        value: a,
        // 标识交换的元素
        swap: i === j || i === j + 1,
      }));
    }
  }
  return arr;
}

算法可视化

本文使用了 @antv/G2 来进行绘制，G2 是一套简洁的渐进式可视化语法，主要用于制作基于网页的可视化。它提供了一套函数风格式、声明形式的 API 和组件化的编程范式，希望能帮助用户能快速完成报表搭建、数据探索、可视化叙事等多样化的需求。

要实现算法可视化的动画效果，我们需要用到 G2 5.0 的新特性：timingKeyframe，可以将其类比理解为CSS的 Keyframe。

整体实现思路如下：

定义 G2 的视图关键帧
对生成器进行迭代，取出每一帧的数据
基于帧数据绘制每一帧的视图

import { Chart } from '@antv/g2';

const chart = new Chart({
  container: 'container',
  autoFit: true
});

// 需要进行排序的数组
const data = [43, 2, 5, 24, 53, 78, 82, 63, 49, 6];

// 定义视图的关键帧
const keyframe = chart.timingKeyframe()

for (const frame of bubbleSort(data)) {
  keyframe
    // 绘制一个条形图
    .interval()
    // 对数据稍作加工，为其添加上索引(index)字段，其中'...' 是一种解构语法
    .data(frame.map((datum, index) => ({ index, ...datum })))
    // 将索引字段编码到 x 轴的维度
    .encode('x', 'index')
    // 将表示值的字段编码到 y 轴的维度
    .encode('y', 'value')
    // 为了实现每次排序过程中的交换效果
    .encode('key', 'value')
    // 将表示当前正在交换元素的 swap 标记字段编码到条形图的颜色上
    .encode('color', 'swap');
}

chart.render();

封装

为了使上述代码适应更多的排序算法，我们对其进行简单的封装。

function sortAlgorithmKeyframe(container, sortFn, data){
  const chart = new Chart({
    container,
    autoFit: true
  });
  
  const keyframe = chart.timingKeyframe();

	const addFrame = (d) => {
  	keyframe
      .interval()
      .data(d.map(({ value, swap }, i) => ({ x: i, y: value, swap })))
      .encode("x", "x")
      .encode("y", "y")
      .encode("key", "y")
      .encode("color", "swap")
      .legend(false)
      .axis("x", false)
      .axis("y", false);
  };

  // 绘制首帧
  addFrame(data.map((d, i) => ({ value: d, swap: false })));

  for (const frame of sortFn(data)) {
    // 添加排序帧
    addFrame(frame);
  }

  chart.render();
  
  return chart;
}

// 调用示例
sortAlgorithmKeyframe('container', bubbleSort, [43, 2, 5, 24, 53, 78, 82, 63, 49, 6])

更多算法

基于 sortAlgorithmKeyframe，我们还可以实现更多的算法可视化案例。

选择排序

function* selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let lowest = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[lowest]) lowest = j;
    }
    if (lowest !== i) {
      [arr[i], arr[lowest]] = [arr[lowest], arr[i]];
    }
    yield arr.map((a, index) => ({
      value: a,
      swap: index === lowest || index === i ? true : false
    }));
  }
  return arr;
}

插入排序

function* insertionSort(arr) {
  var len = arr.length;
  var preIndex, current;
  for (var i = 1; i < len; i++) {
    preIndex = i - 1;
    current = arr[i];
    while (preIndex >= 0 && arr[preIndex] > current) {
      arr[preIndex + 1] = arr[preIndex];
      preIndex--;
    }
    arr[preIndex + 1] = current;
    yield arr.map((a, index) => ({
      value: a,
      swap: index === preIndex + 1 || index === i
    }));
  }
  return arr;
}

该案例已沉淀到 G2 官网，大家可以访问进行调试。G2 5.0 于 2023.03.21 正式发布，更多新版本特性大家可以访问G2 官网和G2 5.0 发布文章进行了解。