2023年1月9日 17:03:44go评论81阅读模式

英文:

How can I imporve my code to get better perfomance when sorting the array

问题

以下是您要翻译的部分：

"Hey i want to create sorting alogrithms visualisation for user.I m using typescript to do it first algorithm i start implmenting is bubble sort it do well when the number amount is about 50 but is have a choose box and user can choose from 50,100,250,500.Every thing after 50 is lagging my browser.I m using d3.js to visualise the proccess. Oh and the data is generated using Fisher-Yates shuffle ( 0(n) complexity) .

That the code to add animations for bars to change places

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();
}

here is function i use to sort values i with setTimeout it menaged to work somehow with 50 numbers but further it doesnt work.Without set timeout it works even worse.

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();
};

I use the start the function when user clicks start button :

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

Edit : here is link to code that reproducts my issue : 链接"

英文:

Hey i want to create sorting alogrithms visualisation for user.I m using typescript to do it first algorithm i start implmenting is bubble sort it do well when the number amount is about 50 but is have a choose box and user can choose from 50,100,250,500.Every thing after 50 is lagging my browser.I m using d3.js to visualise the proccess. Oh and the data is generated using Fisher-Yates shuffle ( 0(n) complexity) .

That the code to add animations for bars to change places

  function updateBars(counter: number) {
    // Select all the bars and bind them to the data
    const bars = svg.selectAll&lt;SVGRectElement, number&gt;(&quot;rect&quot;).data(data);

    bars.style(&quot;fill&quot;, (_d, i) =&gt;
      i === counter || i === counter + 1 ? &quot;red&quot; : &quot;blue&quot;
    );

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

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

here is function i use to sort values i with setTimeout it menaged to work somehow with 50 numbers but further it doesnt work.Without set timeout it works even worse.

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

    const sort = () =&gt; {
      let swapsMade = false;
      for (let i = 0; i &lt; data.length - 1; i++) {
        if (data[i] &gt; 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&lt;SVGRectElement, number&gt;(&quot;rect&quot;).style(&quot;fill&quot;, &quot;black&quot;);
      }
    };

    sort();
  };

I use the start the function when user clicks start button :

 startButton.addEventListener(&quot;click&quot;, () =&gt; {
    bubbleSort(data, updateBars);
  });

Edit :
here is link to code that reproducts my issue : https://stackblitz.com/edit/vitejs-vite-v4oidb?file=src%2Fmain.ts

答案1

得分: 4

以下是您要翻译的代码部分：

  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); // <--- 调整需要的毫秒数
        }
      }
    }
    svg.selectAll('rect').style('fill', 'black');
  }

希望这对您有所帮助。如果您需要进一步的翻译或有其他问题，请随时提问。

英文:

The issue is that you will have multiple calls of updateBars before a next setTimeout is called, and this number of calls can represent too much work for one time slice created with the 50ms setTimeout.

This kind of animations is more easily managed with async functions.

All you need to do is define a delay function that promisifies setTimeout, and turn bubbleSort into an async function that awaits a delay after each call of updateBars:

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

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

Here is a snippet with your code, and where only the above code was inserted for your bubbleSort function:

const delay = ms =&gt; new Promise(resolve =&gt; setTimeout(resolve, ms)); // &lt;-- added

const drawVisualization = (data) =&gt; {
  const margin = { top: 10, right: 10, bottom: 30, left: 10 };
  const width = 1200 - margin.left - margin.right;
  const height = 400 - margin.top - margin.bottom;

  // If it is .visualization del it first
  d3.select(&#39;.visualization&#39;).selectAll(&#39;rect&#39;).remove();
  d3.select(&#39;.visualization&#39;).select(&#39;svg&#39;).remove();

  const svg = d3
    .select(&#39;.visualization&#39;)
    .append(&#39;svg&#39;)
    .attr(&#39;width&#39;, width)
    .attr(&#39;height&#39;, height)
    .attr(&#39;transform&#39;, &#39;translate(&#39; + margin.left + &#39;,&#39; + margin.top + &#39;)&#39;);

  // Create a bar chart using the data
  const barPadding = 1;
  const barWidth = width / data.length - 1;
  svg
    .selectAll(&#39;rect&#39;)
    .data(data)
    .enter()
    .append(&#39;rect&#39;)
    .attr(&#39;x&#39;, (_d, i) =&gt; i * (barWidth + barPadding))
    .attr(&#39;y&#39;, (d) =&gt; height - d)
    .attr(&#39;width&#39;, barWidth)
    .attr(&#39;height&#39;, (d) =&gt; d)
    .on(&#39;mouseover&#39;, function (_d, i) {
      d3.select(this.parentElement)
        .append(&#39;text&#39;)
        .text(i)
        .attr(
          &#39;x&#39;,
          () =&gt; data.indexOf(i) * (barWidth + barPadding) + barWidth / 2
        )
        .attr(&#39;y&#39;, height - i - 20)
        .attr(&#39;font-size&#39;, &#39;14px&#39;)
        .attr(&#39;fill&#39;, &#39;blue&#39;)
        .attr(&#39;text-anchor&#39;, &#39;middle&#39;);

      d3.select(this).style(&#39;opacity&#39;, 0.85);
    })
    .on(&#39;mouseleave&#39;, function () {
      d3.select(this.parentElement).select(&#39;text&#39;).remove();

      d3.select(this).style(&#39;opacity&#39;, 1);
    });

  const startButton = document.querySelector(
    &#39;.run-sorting-btn&#39;
  );

  function updateBars(counter) {
    // Select all the bars and bind them to the data
    const bars = svg.selectAll(&#39;rect&#39;).data(data);

    bars.style(&#39;fill&#39;, (_d, i) =&gt;
      i === counter || i === counter + 1 ? &#39;red&#39; : &#39;blue&#39;
    );

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

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

  // Replaced this function with async version that calls delay(10);
  const bubbleSort = async (data, updateBars) =&gt; {
    let swapsMade = true;
    while (swapsMade) {
      swapsMade = false;
      for (let i = 0; i &lt; data.length - 1; i++) {
        if (data[i] &gt; data[i + 1]) {
          const temp = data[i];
          data[i] = data[i + 1];
          data[i + 1] = temp;
          swapsMade = true;
          updateBars(i);
          await delay(10); //&lt;---
        }
      }
    }
    svg.selectAll(&#39;rect&#39;).style(&#39;fill&#39;, &#39;black&#39;);
  }

  startButton.addEventListener(&#39;click&#39;, () =&gt; {
    bubbleSort(data, updateBars);
  });
};

const generateData = (numPoints) =&gt; {
  const data = [...Array(numPoints).keys()];
  for (let i = data.length - 1; i &gt; 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [data[i], data[j]] = [data[j], data[i]];
  }
  return data;
};

const dataSizeSelect = d3.select(&#39;#data-size&#39;);

// let isRunning = false;
// const startButton = document.querySelector(
//   &quot;.run-sorting-btn&quot;
// ) as HTMLButtonElement;

const drawVisualizationOnLoad = () =&gt; {
  const dataSize = +dataSizeSelect.property(&#39;value&#39;);
  const data = generateData(dataSize);
  drawVisualization(data);
};

// draw on first load

drawVisualizationOnLoad();

// change if values are changed

dataSizeSelect.on(&#39;change&#39;, drawVisualizationOnLoad);

body {
  font-family: &#39;Lato&#39;, sans-serif;
  overflow-x: hidden;
  height: 100vh;
}

main {
  margin-top: 50px;
  display: flex;
  justify-content: flex-start;
  align-items: center;
  flex-direction: column;
  height: 100%;
}

.header {
  margin-top: 20px;
  font-size: 32px;
  font-weight: bold;
}

.visualization {
  margin-top: 15px;
  width: 100%;
  display: flex;
  justify-content: center;
  align-items: center;
}

/* Sorting wrapper */

.selects-wrapper {
  display: flex;
  margin-top: 50px;
}

/* Select styles */
.select-outer-container {
  display: flex;
  flex-direction: column;
  justify-content: center;
  align-items: center;
}

.select-outer-container p {
  font-size: 18px;
}

.select-inner-container {
  position: relative;
  min-width: 200px;
}

select {
  cursor: pointer;
}
select::-ms-expand {
  display: none;
}

.select-inner-container:after {
  content: &#39;&lt;&gt;&#39;;
  font: 17px &#39;Consolas&#39;, monospace;
  color: #333;
  -webkit-transform: rotate(90deg);
  -moz-transform: rotate(90deg);
  -ms-transform: rotate(90deg);
  transform: rotate(90deg);
  right: 11px;
  /*Adjust for position however you want*/

  top: 18px;
  padding: 0 0 2px;
  border-bottom: 1px solid #999;
  /*left line */

  position: absolute;
  pointer-events: none;
}

.select-inner-container select {
  -webkit-appearance: none;
  -moz-appearance: none;
  appearance: none;
  /* Add some styling */

  display: block;
  width: 100%;
  max-width: 320px;
  height: 50px;
  margin: 5px 0px;
  padding: 0px 24px;
  font-size: 16px;
  line-height: 1.75;
  color: #333;
  background-color: #ffffff;
  background-image: none;
  border: 1px solid #cccccc;
  -ms-word-break: normal;
  word-break: normal;
}

/* Button */

.run-sorting-btn {
  margin-top: 10px;
  border: none;
  border-radius: 5px;
  font-size: 22px;
  font-weight: bold;
  width: 400px;
  padding: 10px 15px;
  background-color: green;
  color: white;
  cursor: pointer;
  transition: transform 0.3s ease-in;
}

.run-sorting-btn:hover {
  transform: translateY(-2px);
}

.run-sorting-btn:active {
  transform: translateY(3px);
  transition:  0.1s;
}

:root {
  font-family: Inter, Avenir, Helvetica, Arial, sans-serif;
  font-size: 16px;
  line-height: 24px;
  font-weight: 400;

  color-scheme: light dark;
  color: rgba(255, 255, 255, 0.87);
  background-color: #242424;

  font-synthesis: none;
  text-rendering: optimizeLegibility;
  -webkit-font-smoothing: antialiased;
  -moz-osx-font-smoothing: grayscale;
  -webkit-text-size-adjust: 100%;
}

a {
  font-weight: 500;
  color: #646cff;
  text-decoration: inherit;
}
a:hover {
  color: #535bf2;
}

body {
  margin: 0;
  display: flex;
  place-items: center;
  min-width: 320px;
  min-height: 100vh;
}

h1 {
  font-size: 3.2em;
  line-height: 1.1;
}

#app {
  max-width: 1280px;
  margin: 0 auto;
  padding: 2rem;
  text-align: center;
}

.logo {
  height: 6em;
  padding: 1.5em;
  will-change: filter;
  transition: filter 300ms;
}
.logo:hover {
  filter: drop-shadow(0 0 2em #646cffaa);
}
.logo.vanilla:hover {
  filter: drop-shadow(0 0 2em #3178c6aa);
}

.card {
  padding: 2em;
}

.read-the-docs {
  color: #888;
}

button {
  border-radius: 8px;
  border: 1px solid transparent;
  padding: 0.6em 1.2em;
  font-size: 1em;
  font-weight: 500;
  font-family: inherit;
  background-color: #1a1a1a;
  cursor: pointer;
  transition: border-color 0.25s;
}
button:hover {
  border-color: #646cff;
}
button:focus,
button:focus-visible {
  outline: 4px auto -webkit-focus-ring-color;
}

@media (prefers-color-scheme: light) {
  :root {
    color: #213547;
    background-color: #ffffff;
  }
  a:hover {
    color: #747bff;
  }
  button {
    background-color: #f9f9f9;
  }
}

&lt;script src=&quot;https://cdnjs.cloudflare.com/ajax/libs/d3/7.8.0/d3.min.js&quot;&gt;&lt;/script&gt;

&lt;main&gt;
  &lt;h1 class=&quot;header&quot;&gt;Sorting algorithms visualisation&lt;/h1&gt;
  &lt;div class=&quot;selects-wrapper&quot;&gt;
    &lt;div class=&quot;select-outer-container&quot;&gt;
      &lt;p&gt;Choose the data size:&lt;/p&gt;
      &lt;div class=&quot;select-inner-container&quot;&gt;
        &lt;select id=&quot;data-size&quot;&gt;
          &lt;option value=&quot;50&quot; selected&gt;50&lt;/option&gt;
          &lt;option value=&quot;100&quot;&gt;100&lt;/option&gt;
          &lt;option value=&quot;250&quot;&gt;250&lt;/option&gt;
          &lt;option value=&quot;500&quot;&gt;500&lt;/option&gt;
        &lt;/select&gt;
      &lt;/div&gt;
    &lt;/div&gt;
    &lt;div class=&quot;select-outer-container&quot;&gt;
      &lt;p&gt;Choose sorting alogorithm:&lt;/p&gt;
      &lt;div class=&quot;select-inner-container&quot;&gt;
        &lt;select id=&quot;sort-algorithm&quot;&gt;
          &lt;option value=&quot;bubble-sort&quot; selected&gt;Bubble Sort&lt;/option&gt;
          &lt;option value=&quot;selection-sort&quot;&gt;Selection Sort&lt;/option&gt;
          &lt;option value=&quot;insertion-sort&quot;&gt;Insertion Sort&lt;/option&gt;
          &lt;option value=&quot;merge-sort&quot;&gt;Merge Sort&lt;/option&gt;
          &lt;option value=&quot;quick-sort&quot;&gt;Quick Sort&lt;/option&gt;
        &lt;/select&gt;
      &lt;/div&gt;
    &lt;/div&gt;
  &lt;/div&gt;
  &lt;button class=&quot;run-sorting-btn&quot;&gt;Start&lt;/button&gt;

  &lt;div class=&quot;visualization&quot;&gt;&lt;/div&gt;
&lt;/main&gt;

通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。

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

问题

答案1

从导航到另一个屏幕后将屏幕从堆栈中移除

React Native地图在重新启动应用程序时渲染当前位置时出现问题。

问题：在Node.js中将变量值发送到显示控制器时出现问题。

mongoose代码在特定区域不起作用。

What's the correct way to type hint an empty list as a literal in python?

如何在Highcharts Gantt中更改本地化的星期名称

如何在同一个流中使用多个过滤器和映射函数？

如何使用Map/Set来将代码优化到O(n)？

.NET MAUI Android在GitHub Actions上构建失败，错误代码为1。

如何在Playwright视觉比较中屏蔽多个定位器？

在C++中，可以使用可变模板参数来检索类型的内部类型。

selenium.common.exceptions.StaleElementReferenceException: Message: stale element reference: stale element not found

Creating and opening a URL to log in to Website via Basic Auth with Robot Framework/Selenium (Python)

AG Grid 在上下文菜单中以大文本形式打开

发表评论