实践[前端] 基于Vue+Generator的排序异步可视化

站长

2024年04月07日 18:22 · 阅读数 7

众所周知JavaScript是单线程的，如果执行排序这种操作，则会造成页面渲染的阻塞，那么如何避免这种阻塞呢？我们可以使用异步渲染的方式将cpu密集的运算拆分为多个task,效果如下，我们在进行sort渲染的时候，按钮依然可以操作。红色为参加本次排序的数据项

在线体验地址：sort

仓库地址:sort

实践[前端] 基于Vue+Generator的排序异步可视化

新增效果，增加了开始和暂停

这也是实现异步的一个好处，可以随时暂停或开始渲染实践[前端] 基于Vue+Generator的排序异步可视化

从上面我们可以看到，每个渲染都分为多个task,而非一个task处理所有执行。

那么实现这种效果具体需要包括哪些点呢？

渲染canvas
排序程序
异步调度

首先我们定义排序使用的list，我们创建了一个数组，包含了180个数据项

const length = 180;
const randomList = Array.from({ length }).map(() => Math.random() * 250);

渲染canvas

下面代码的主要逻辑：

清除画布
开启绘制路径
循环列表，将极坐标转化为转化为笛卡尔坐标，并绘制出相应位置的点
返回一个promise,并延时一个定时器宏队列，保证每次渲染之间至少会被event_loop调度一次。
在promise中增加定时器，实现对flag状态位的监听，控制运行与暂停

const WIDTH = 1000;
const HEIGHT = 1000;
const flag = ref(true);
const WIDTHCENTER = WIDTH / 2;
const HEIGHTCENTER = HEIGHT / 2;
const canvas = ref<HTMLCanvasElement>();
const context = ref<CanvasRenderingContext2D | null>();
const draw = (changeList: number[]) => {
  const ctx = context.value;
  if (!ctx) return;
  ctx.clearRect(0, 0, WIDTH, HEIGHT);

  randomList.forEach((node, i) => {
    const x = node * Math.cos((Math.PI / (length / 2)) * i);
    const y = node * Math.sin((Math.PI / (length / 2)) * i);
    ctx.beginPath();
    ctx.moveTo(WIDTHCENTER + x, HEIGHTCENTER + y);
    if (changeList.includes(i)) {
      ctx.fillStyle = "#f00";
      ctx.strokeStyle = "#f00";
    } else {
      ctx.fillStyle = "#000";
      ctx.strokeStyle = "#000";
    }
    ctx.arc(WIDTHCENTER + x, HEIGHTCENTER + y, 4, 0, Math.PI * 2);
    ctx.fill();
    ctx.moveTo(WIDTHCENTER, HEIGHTCENTER);
    ctx.stroke();
  });

  return new Promise<void>((res) => {
    if (flag.value) {
      setTimeout(() => {
        res();
      }, 0);
    } else {
      setInterval(() => {
        if (flag.value) {
          res();
        }
      });
    }
  });
};

排序函数

排序函数使用generator将每次循环完毕的调度权交给调用者，让调用者决定是否开启下一次循环。下面包含了冒泡，插入，选择，希尔四种排序

// 冒泡排序
async function* sort() {
  for (let i = 0; i < randomList.length; i++) {
    let changeList = [];
    for (let j = 0; j < randomList.length; j++) {
      if (randomList[j] > randomList[j + 1]) {
        let temp = randomList[j];
        randomList[j] = randomList[j + 1];
        randomList[j + 1] = temp;
        changeList.push(j);
      }
    }
    await draw(changeList);
    yield true;
  }
  await draw([]);
  yield false;
}

// 插入排序
async function* sort2() {
  for (let i = 1; i < randomList.length; i++) {
    let changeList = [];
    let perIndex = i;
    let count = randomList[i];
    while (perIndex >= 1 && randomList[perIndex - 1] > count) {
      randomList[perIndex] = randomList[perIndex - 1];
      perIndex -= 1;
      changeList.push(perIndex);
    }
    randomList[perIndex] = count;
    await draw(changeList);
    yield true;
  }
  await draw([]);
  yield false;
}
// 插入排序
async function* sort3() {
  for (let i = 0; i < randomList.length; i++) {
    let changeList = [];
    let perIndex = i;
    for (let j = i; j < randomList.length; j++) {
      if (randomList[perIndex] >= randomList[j]) {
        perIndex = j;
        changeList.push(perIndex);
      }
    }
    let temp = randomList[i];
    randomList[i] = randomList[perIndex];
    randomList[perIndex] = temp;
    await draw(changeList);
    yield true;
  }
  await draw([]);
  yield false;
}
// 希尔排序
async function* sort4() {
  let temp = undefined,
    gap = 1;
  // 动态定义间隔序列
  while (gap < randomList.length / 3) {
    gap = gap * 3 + 1;
  }
  for (gap; gap > 0; gap = Math.floor(gap / 3)) {
    let changeList = [];
    for (var i = gap; i < randomList.length; i++) {
      let j = -1;
      temp = randomList[i];
      for (j = i - gap; j >= 0 && randomList[j] > temp; j -= gap) {
        randomList[j + gap] = randomList[j];
        changeList.push(j + gap);
      }
      randomList[j + gap] = temp;
      await draw(changeList);
      yield true;
    }
    yield false;
  }

  for (let i = 0; i < randomList.length; i++) {
    let changeList = [];
    let perIndex = i;
    for (let j = i; j < randomList.length; j++) {
      if (randomList[perIndex] >= randomList[j]) {
        perIndex = j;
        changeList.push(perIndex);
      }
    }

    let temp = randomList[i];
    randomList[i] = randomList[perIndex];
    randomList[perIndex] = temp;
    await draw(changeList);
    yield true;
  }
  await draw([]);
  yield false;
}

调度函数

调度时我们使用while循环处理每个排序返回的next,并进行循环渲染，保证动画的连续性

const start = async () => {
  let next = sort();
  while (!(await next.next()).done);
};

完整代码

这个代码还有很大的优化空间，比如几种排序算法是完全可以独立封装的，同时保证draw这种绘制方法不应直接编入排序算法中，应当保持职责分离，等近期事情结束了再进行职责分离，方式就使用 useFunc的方式就可以了

<template>
  <div class="home">
    <canvas id="canvas" ref="canvas"></canvas>
    <div>
      <div class="button" @click="bubStart">冒泡排序</div>
      <div class="button" @click="insertStart">插入排序</div>
      <div class="button" @click="selectStart">选择排序</div>
      <div class="button" @click="shellStart">希尔排序</div>
      <div class="button" @click="() => (flag = !flag)">
        {{ flag ? "暂停" : "开始" }}
      </div>
    </div>
    <div style="padding: 15px">{{ time }}</div>
  </div>
</template>

<script lang="ts" setup>
import { onMounted, ref } from "vue";
const length = 300;
const WIDTH = 1000;
const HEIGHT = 1000;
const WIDTHCENTER = WIDTH / 2;
const HEIGHTCENTER = HEIGHT / 2;
let randomList = Array.from({ length }).map(() => Math.random() * 500);

const time = ref(0);
const flag = ref(true);
const canvas = ref<HTMLCanvasElement>();
const context = ref<CanvasRenderingContext2D | null>();

const draw = (changeList: number[]) => {
  const ctx = context.value;
  if (!ctx) return;
  ctx.clearRect(0, 0, WIDTH, HEIGHT);

  randomList.forEach((node, i) => {
    const x = node * Math.cos((Math.PI / (length / 2)) * i);
    const y = node * Math.sin((Math.PI / (length / 2)) * i);
    ctx.beginPath();
    ctx.moveTo(WIDTHCENTER + x, HEIGHTCENTER + y);
    if (changeList.includes(i)) {
      ctx.fillStyle = "#f00";
      ctx.strokeStyle = "#f00";
    } else {
      ctx.fillStyle = "#000";
      ctx.strokeStyle = "#000";
    }
    ctx.arc(WIDTHCENTER + x, HEIGHTCENTER + y, 4, 0, Math.PI * 2);
    ctx.fill();
    ctx.moveTo(WIDTHCENTER, HEIGHTCENTER);
    ctx.stroke();
  });

  return new Promise<void>((res) => {
    if (flag.value) {
      setTimeout(() => {
        res();
      }, 0);
    } else {
      setInterval(() => {
        if (flag.value) {
          res();
        }
      });
    }
  });
};

// 冒泡排序
async function* sort() {
  for (let i = 0; i < randomList.length; i++) {
    let changeList = [];
    for (let j = 0; j < randomList.length; j++) {
      if (randomList[j] > randomList[j + 1]) {
        let temp = randomList[j];
        randomList[j] = randomList[j + 1];
        randomList[j + 1] = temp;
        changeList.push(j);
      }
    }
    await draw(changeList);
    yield true;
  }
  await draw([]);
  yield false;
}

// 插入排序
async function* sort2() {
  for (let i = 1; i < randomList.length; i++) {
    let changeList = [];
    let perIndex = i;
    let count = randomList[i];
    while (perIndex >= 1 && randomList[perIndex - 1] > count) {
      randomList[perIndex] = randomList[perIndex - 1];
      perIndex -= 1;
      changeList.push(perIndex);
    }
    randomList[perIndex] = count;
    await draw(changeList);
    yield true;
  }
  await draw([]);
  yield false;
}
// 插入排序
async function* sort3() {
  for (let i = 0; i < randomList.length; i++) {
    let changeList = [];
    let perIndex = i;
    for (let j = i; j < randomList.length; j++) {
      if (randomList[perIndex] >= randomList[j]) {
        perIndex = j;
        changeList.push(perIndex);
      }
    }
    let temp = randomList[i];
    randomList[i] = randomList[perIndex];
    randomList[perIndex] = temp;
    await draw(changeList);
    yield true;
  }
  await draw([]);
  yield false;
}
// 希尔排序
async function* sort4() {
  let temp = undefined,
    gap = 1;
  // 动态定义间隔序列
  while (gap < randomList.length / 3) {
    gap = gap * 3 + 1;
  }
  for (gap; gap > 0; gap = Math.floor(gap / 3)) {
    let changeList = [];
    for (var i = gap; i < randomList.length; i++) {
      let j = -1;
      temp = randomList[i];
      for (j = i - gap; j >= 0 && randomList[j] > temp; j -= gap) {
        randomList[j + gap] = randomList[j];
        changeList.push(j + gap);
      }
      randomList[j + gap] = temp;
      await draw(changeList);
      yield true;
    }
    yield false;
  }

  for (let i = 0; i < randomList.length; i++) {
    let changeList = [];
    let perIndex = i;
    for (let j = i; j < randomList.length; j++) {
      if (randomList[perIndex] >= randomList[j]) {
        perIndex = j;
        changeList.push(perIndex);
      }
    }

    let temp = randomList[i];
    randomList[i] = randomList[perIndex];
    randomList[perIndex] = temp;
    await draw(changeList);
    yield true;
  }
  await draw([]);
  yield false;
}

const bubStart = async () => {
  randomList = Array.from({ length }).map(() => Math.random() * 500);
  let next = sort();
  let start = Date.now();
  while (!(await next.next()).done);
  time.value = Date.now() - start;
};

const insertStart = async () => {
  randomList = Array.from({ length }).map(() => Math.random() * 500);
  let next = sort2();
  let start = Date.now();
  while (!(await next.next()).done);
  time.value = Date.now() - start;
};

const selectStart = async () => {
  randomList = Array.from({ length }).map(() => Math.random() * 500);
  let next = sort3();
  let start = Date.now();
  while (!(await next.next()).done);
  time.value = Date.now() - start;
};

const shellStart = async () => {
  randomList = Array.from({ length }).map(() => Math.random() * 500);
  let next = sort4();
  let start = Date.now();
  while (!(await next.next()).done);
  time.value = Date.now() - start;
};

onMounted(async () => {
  console.log(canvas.value);
  context.value = canvas.value?.getContext("2d");
  if (!canvas.value) return;
  canvas.value.width = WIDTH;
  canvas.value.height = HEIGHT;
});
</script>
<style lang="scss" scoped>
#canvas {
  width: 500px;
  height: 500px;
  // background-color: black;
}
.button {
  padding: 15px;
  display: inline-block;
  border-radius: 5px;
  user-select: none;
  cursor: pointer;
  border: 1px solid #cecece;
}
</style>

总结

上述代码实现了一个比较精简的异步拆分渲染拆分逻辑，如果以后遇到此类问题都可以利用这种方式将阻塞任务拆分，提高用户的体验感和互动性。

但是这种方式存在的问题是因为每次调度会间隔15-20ms,会导致运算性能极其低下，慎用！！！

仓库地址:sort