Как я могу улучшить свой код, чтобы повысить производительность при сортировке массива

Эй, я хочу создать визуализацию алгоритмов сортировки для пользователя. Я использую машинописный текст, чтобы сделать это. Первый алгоритм, который я начинаю внедрять, - это пузырьковая сортировка, она хорошо работает, когда число составляет около 50, но у него есть поле выбора, и пользователь может выбирать из 50 100 250 500. Каждый вещь после 50 отстает от моего браузера. Я использую d3.js для визуализации процесса. Да, и данные генерируются с использованием перетасовки Фишера-Йейтса (сложность 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, она как-то работала с 50 числами, но дальше она не работает. Без установленного таймаута она работает еще хуже.

  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

Знаете ли вы, что сортировка пузырьком 500 элементов требует в 100 раз больше перестановок, чем сортировка 50?

Yves Daoust 09.01.2023 11:05

@YvesDaoust в порядке, но лагает даже на 100 элементах

IvonaK 09.01.2023 11:21
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Улучшение производительности загрузки с помощью Google Tag Manager и атрибута Defer
Улучшение производительности загрузки с помощью Google Tag Manager и атрибута Defer
В настоящее время производительность загрузки веб-сайта имеет решающее значение не только для удобства пользователей, но и для ранжирования в...
Безумие обратных вызовов в javascript [JS]
Безумие обратных вызовов в javascript [JS]
Здравствуйте! Юный падаван 🚀. Присоединяйся ко мне, чтобы разобраться в одной из самых запутанных концепций, когда вы начинаете изучать мир...
Система управления парковками с использованием HTML, CSS и JavaScript
Система управления парковками с использованием HTML, CSS и JavaScript
Веб-сайт по управлению парковками был создан с использованием HTML, CSS и JavaScript. Это простой сайт, ничего вычурного. Основная цель -...
JavaScript Вопросы с множественным выбором и ответы
JavaScript Вопросы с множественным выбором и ответы
Если вы ищете платформу, которая предоставляет вам бесплатный тест JavaScript MCQ (Multiple Choice Questions With Answers) для оценки ваших знаний,...
0
2
78
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Проблема в том, что у вас будет несколько вызовов updateBars до того, как будет вызван следующий setTimeout, и это количество вызовов может представлять собой слишком много работы для одного временного интервала, созданного с помощью 50 мс setTimeout.

Такими анимациями легче управлять с помощью функций async.

Все, что вам нужно сделать, это определить delay функцию, которая обещает setTimeout, и превратить bubbleSort в async функцию, которая await вызывает задержку после каждого вызова updateBars:

  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 был вставлен только приведенный выше код:

const delay = ms => new Promise(resolve => setTimeout(resolve, ms)); // <-- added

const drawVisualization = (data) => {
  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('.visualization').selectAll('rect').remove();
  d3.select('.visualization').select('svg').remove();

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

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

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

      d3.select(this).style('opacity', 1);
    });

  const startButton = document.querySelector(
    '.run-sorting-btn'
  );

  function updateBars(counter) {
    // Select all the bars and bind them to the data
    const bars = svg.selectAll('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();
  }

  // Replaced this function with async version that calls delay(10);
  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');
  }

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

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

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

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

const drawVisualizationOnLoad = () => {
  const dataSize = +dataSizeSelect.property('value');
  const data = generateData(dataSize);
  drawVisualization(data);
};

// draw on first load

drawVisualizationOnLoad();

// change if values are changed

dataSizeSelect.on('change', drawVisualizationOnLoad);
body {
  font-family: 'Lato', 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: '<>';
  font: 17px 'Consolas', 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;
  }
}
<script src = "https://cdnjs.cloudflare.com/ajax/libs/d3/7.8.0/d3.min.js"></script>

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

  <div class = "visualization"></div>
</main>

Другие вопросы по теме

Как правильно обернуть компонент React, чтобы фиксировать события DOM, такие как щелчок, отправка и т. д., При пересылке дочерних элементов и ссылок в Typescript?
Как я могу использовать файл svg в файле scss?
Как преобразовать объект значений любого типа в объект строковых значений (Typescript)?
Как правильно ввести ошибку в ответном запросе?
Ошибка подписи индекса машинописного текста: ошибка типа: аргумент типа не может быть назначен параметру типа «SetStateAction <никогда []>»
Как показать номер строки вывода файла TypeScript в консоли Chrome DevTools с помощью WebStorm?
Почему этот код не компилируется, начиная с TypeScript 4.7?
Ошибка типа реквизита Vue + TypeScript: «Foo» относится только к типу, но здесь используется как значение»
Ошибка машинописного текста: элемент неявно имеет тип «любой», поскольку выражение типа «строка» не может использоваться для индексации
Свойство Preact router «путь» не существует для типа «IntrinsicAttributes»