#javascript
#javascript
Вопрос:
Я пытаюсь добавить сортировку слиянием в свой проект визуализации алгоритма, и у меня возникла странная проблема… Когда я добавляю ожидание сна (любое число), столбцы на HTML-странице сортируются неправильно, но когда я комментирую только эту строку (ожидание сна (любое число)), сортировка проходит нормально! Есть идеи, почему это происходит. (проблема в закомментированных строках)
Ссылка Github на веб-сайт:https://github.com/Marwan-Ezzat-Mohamed/AlgorthimVisualization (без ошибки и без анимации)
Вы можете просто посмотреть, что происходит, когда я раскомментирую прокомментированный код в функции ниже здесь:https://marwan-ezzat-mohamed.github.io/algovis/index
async function merge(a, low, m, high) {
var i, j, k;
var temp = [];
var len = m - low;
console.log(len, 'arr: ', a);
let bars = Array.from(document.getElementById('addbarshere').children);
let animationspeed = Number(
document.getElementById('animation_speed').value
);
for (i = 0; i < len; i ) {
bars[i].style.backgroundColor=red;
temp[i] = a[low i];
}
i = 0;
j = m;
k = low;
while (i < len amp;amp; j < high) {
let animationspeed = Number(
document.getElementById('animation_speed').value
);
if (temp[i] <= a[j]) {
bars[k].style.height = temp[i] 'px';
bars[k].style.backgroundColor=yellow;
//await sleep(animationspeed);
bars[k].style.backgroundColor=blue;
a[k ] = temp[i ];
} else {
bars[k].style.height = bars[j].style.height;
bars[k].style.backgroundColor=yellow;
//await sleep(animationspeed);
bars[k].style.backgroundColor=blue;
a[k ] = a[j ];
}
}
while (i < len) {
let animationspeed = Number(
document.getElementById('animation_speed').value
);
bars[k].style.height = temp[i] 'px';
bars[k].style.backgroundColor=yellow;
//await sleep(100);
bars[k].style.backgroundColor=blue;
a[k ] = temp[i ];
}
}
function mergesort(a, low, high) {
if (high - low > 1) {
var m = low ((high - low) >> 1);
mergesort(a, low, m);
mergesort(a, m, high);
merge(a, low, m, high);
}
}
Комментарии:
1. Я только что запустил ваш код из Github локально, и кнопка «Сортировка слиянием» анимируется. Что именно происходит не так?
2. Цвета анимации не отображаются, потому что это происходит так быстро, что вы даже не можете видеть it…so чтобы добавить цвет для эффекта переключения, я должен использовать функцию сна, чтобы вы действительно могли видеть, что происходит. когда я использую функцию ожидания сна, сортировка по какой-то причине работает некорректно. вы можете понять, что я имею в виду, если раскомментируете прокомментированные строки в функции выше или посмотрите эту ссылку: marwan-ezzat-mohamed.github.io/algovis/index
Ответ №1:
Проблема в том, что в вашем коде есть условие гонки. Ваша функция слияния является асинхронной, и вы вызываете ее без ожидания в функции сортировки слиянием. Это означает, что при достижении спящих режимов выполнение не блокируется, оно просто продолжается за пределами этого вызова функции слияния. В конце концов, все вызовы функций слияния выполняются «одновременно», а не один за другим, и они создают тарабарщину при работе с одним и тем же списком.
Чтобы решить эту проблему, вы должны гарантировать, что слияния выполняются синхронно. Для этой цели вы также можете преобразовать свою функцию сортировки слиянием в асинхронную функцию и использовать await для вызовов merge и mergesort, чтобы заставить их выполняться синхронно. Это все, что вам нужно изменить (в дополнение к раскомментированию ваших спящих режимов).
async function mergesort(a, low, high) {
if (high - low > 1) {
var m = low ((high - low) >> 1);
await mergesort(a, low, m);
await mergesort(a, m, high);
await merge(a, low, m, high);
}
}
Примечание: На самом деле, они не все делают что-то одновременно. Один что-то делает, пока другие спят. Они просто запланированы несинхронным способом и приводят к выполнению вместо блокировки.