typescript 如何改进代码以在对数组排序时获得更好的性能

7lrncoxx  于 2023-01-10  发布在  TypeScript
关注(0)|答案(1)|浏览(110)

嘿,我想为用户创建排序算法可视化。我用 typescript 做的第一个算法,我开始实现是气泡排序它做得很好,当数量约为50,但有一个选择框,用户可以选择50,100,250,500. 50岁以后的每件事都落后于我的浏览器。我用d3.js来可视化这个过程。哦,数据是用费舍尔-耶茨 Shuffle (0(n)复杂度)生成的。
为条形图添加动画以改变位置的代码

function updateBars(counter: number) {
    // Select all the bars and bind them to the data
    const bars = svg.selectAll<SVGRectElement, number>("rect").data(data);

    bars.style("fill", (_d, i) =>
      i === counter || i === counter + 1 ? "red" : "blue"
    );

    // Handle any new data elements by appending new bars
    bars
      .enter()
      .append("rect")
      .attr("x", (_d, i) => (i + counter) * (barWidth + barPadding))
      .attr("y", height)
      .attr("width", barWidth)
      .attr("height", 0)
      .merge(bars) // Merge the new bars with the existing ones
      .transition() // Animate the transition of the bars
      .duration(50)
      .attr("y", (d) => height - d)
      .attr("x", (_d, i) => i * (barWidth + barPadding))
      .attr("height", (d) => d);

    // Handle any removed data elements by removing the corresponding bars
    bars.exit().remove();
  }

这是我用setTimeout对值i进行排序函数,它似乎可以处理50个数字,但是它不起作用。没有设置Timeout,它的效果更差。

const bubbleSort = (data: number[], updateBars: Function) => {
    let sorted = false;

    const sort = () => {
      let swapsMade = false;
      for (let i = 0; i < data.length - 1; i++) {
        if (data[i] > data[i + 1]) {
          const temp = data[i];
          data[i] = data[i + 1];
          data[i + 1] = temp;
          swapsMade = true;
          updateBars(i);
        }
      }

      if (!swapsMade) {
        sorted = true;
      }

      // Call with delay to avoid performance issues
      if (!sorted) {
        setTimeout(sort, 50);
      }
      if (sorted) {
        svg.selectAll<SVGRectElement, number>("rect").style("fill", "black");
      }
    };

    sort();
  };

当用户点击启动按钮时,我使用启动功能:

startButton.addEventListener("click", () => {
    bubbleSort(data, updateBars);
  });

编辑:这里是链接到代码,再现我的问题:https://stackblitz.com/edit/vitejs-vite-v4oidb?file=src%2Fmain.ts

ozxc1zmp

ozxc1zmp1#

问题在于,在调用下一个setTimeout之前,您将多次调用updateBars,而对于使用50ms setTimeout创建的一个时间片来说,这个调用次数可能意味着太多的工作。
使用async函数更容易管理此类动画。
您所需要做的就是定义一个delay函数来承诺setTimeout,并将bubbleSort转换为async函数,awaitupdateBars的 * 每次 * 调用之后都会有一个延迟:

const delay = ms => new Promise(resolve => setTimeout(resolve, ms));

  const bubbleSort = async (data, updateBars) => {
    let swapsMade = true;
    while (swapsMade) {
      swapsMade = false;
      for (let i = 0; i < data.length - 1; i++) {
        if (data[i] > data[i + 1]) {
          const temp = data[i];
          data[i] = data[i + 1];
          data[i + 1] = temp;
          swapsMade = true;
          updateBars(i);
          await delay(10); // <--- adjust number of milliseconds as needed
        }
      }
    }
    svg.selectAll('rect').style('fill', 'black');
  }

下面是您的代码片段,其中只为bubbleSort函数插入了上述代码:
x一个一个一个一个x一个一个二个一个x一个一个三个一个

相关问题