Java Script 排序算法可视化工具 [英] Java Script Sorting algorithm visualizer

问题描述

k = []长度 = 100;时间 = 真cont = document.getElementsByClassName("cont")[0];cont.innerHTML = "";for (让 i = 0; i < len; i++) {t = Math.round(Math.random() * 800 ) + 5k.push(t);cont.innerHTML += "<div class='block' style = 'height:" + t + "px'></div>"}功能重置(){k = []cont.innerHTML = "";for (让 i = 0; i < len; i++) {t = Math.round(Math.random() * 800 ) + 5k.push(t);cont.innerHTML += "<div class='block' style = 'height:" + t + "px'> </div>"}}函数气泡(){函数 iloop(i){如果(我< len){设置超时(功能(){函数 jloop(j){如果(j  k[j + 1]) {让 tmp = k[j];k[j] = k[j + 1];k[j + 1] = tmp;}cont.innerHTML = "";for (让 p = 0; p 

.cont {宽度:100%；高度:900px；显示:块；背景颜色:粉红色；填充:0px；显示:-webkit-box；显示:-ms-flexbox;显示:弹性；-webkit-box-pack: 中心；-ms-flex-pack:居中；对齐内容:居中；-ms-flex-line-pack:居中；对齐内容:居中；}.cont .block {显示:内联块；宽度:10px；边距:自动 1px；背景颜色:红色；字体大小:5px；底部:0px；}

 重置数组<button class="bubble" onclick="bubble()">冒泡排序<div class="cont">

我正在使用这个简单的代码来制作一个用于排序算法的 javascript 可视化工具，但问题是它非常不稳定，即使在 100 毫秒的延迟下运行时也会跳过多个帧.我有一个 i7 7700hq 和 gtx 1060，所以我知道问题主要不是我的笔记本电脑，而是我的方法，所以我应该采取什么方法

如果您的代码段不起作用，这里有一个代码笔版本https://codepen.io/varunagarwal/pen/gOaQqbG

有人告诉我把它变成一个可运行的片段，这样你就可以了

解决方案

您有重叠的 setTimeout 计时器，并且其中有 很多 正在计划中.您只想在有更改显示时让步给浏览器，并且您只想显示给定的更改一次.

由于您使用的是 ES2015+，我可能会使用生成器函数进行排序，并在发生变化时产生:

function *sortGen() {for (let i = 0; i < len; ++i) {for (让 j = 0; j  k[j + 1]) {让 tmp = k[j];k[j] = k[j + 1];k[j + 1] = tmp;产量 j;//*** 屈服于调用者，说明发生了什么变化}}}}

然后调用它的代码会调用它的 next 方法，进行更新，然后通过 requestAnimationFrame 在下一个动画帧之前安排回调(除非你想人为地减慢它的速度，在这种情况下 setTimeout 很好).如果浏览器不忙于做其他事情，动画帧每秒发生 60 次(大约每 16.666667 毫秒).这是使用上述 sortGen 函数中的生成器的 bubble:

function bubble() {const gen = sortGen();打钩();功能滴答(){const 结果 = gen.next();如果(！结果.完成){//*** 无需重新创建所有元素，只需对交换的元素重新排序const el = cont.children[result.value];const next = el.nextElementSibling;el.parentElement.insertBefore(next, el);requestAnimationFrame(tick);}}}

(您可以将其设为异步生成器并使用 for-await-of 循环，但我认为它并没有真正让您受益.)

这是一个活生生的例子；我还在代码中包含了一些注释，提出了其他建议:

"use strict";//*** 使用严格模式//*** 声明你的变量(旧代码依赖于隐式全局变量的恐怖，它//严格模式修复)让 k = [];//*** 始终使用分号(或始终依赖 ASI)让 len = 100;让时间 = 真；const cont = document.getElementsByClassName("cont")[0];//*** 不要重复代码，只需使用`reset`重启();功能重置(){k = [];//*** 不要在 `innerHTML` 上使用 +=让 html = "";for (让 i = 0; i < len; i++) {//*** 声明你的变量const t = Math.round(Math.random() * 800 ) + 5;k.push(t);html += makeBlock(t);}cont.innerHTML = html;}函数makeBlock(值){return "<div class='block' style = 'height:" + value + "px'></div>";}函数 *sortGen() {for (let i = 0; i < len; ++i) {for (让 j = 0; j  k[j + 1]) {让 tmp = k[j];k[j] = k[j + 1];k[j + 1] = tmp;产量 j;//*** 屈服于调用者，说明发生了什么变化}}}}函数气泡(){const gen = sortGen();打钩();功能滴答(){const 结果 = gen.next();如果(！结果.完成){//*** 无需重新创建所有元素，只需对交换的元素重新排序const el = cont.children[result.value];const next = el.nextElementSibling;el.parentElement.insertBefore(next, el);requestAnimationFrame(tick);}}}

.cont {宽度:100%；高度:900px；显示:块；背景颜色:粉红色；填充:0px；显示:-webkit-box；显示:-ms-flexbox;显示:弹性；-webkit-box-pack: 中心；-ms-flex-pack:居中；对齐内容:居中；-ms-flex-line-pack:居中；对齐内容:居中；}/* *** 不要在行尾隐藏关闭 } */.cont .block {显示:内联块；宽度:10px；边距:自动 1px；背景颜色:红色；字体大小:5px；底部:0px；}/* *** 不要在行尾隐藏关闭 } */

 重置数组<button class="bubble" onclick="bubble()">冒泡排序<div class="cont">

也在 CodePen 上.

就其价值而言，异步生成器方法如下所示:

const nextFrame = cb =>新承诺(解决 => {requestAnimationFrame(() => {cb();解决();});});函数气泡(){(异步() => {for await (sortGen() 的常量值) {等待 nextFrame(() => {const el = cont.children[值];const next = el.nextElementSibling;el.parentElement.insertBefore(next, el);});}})().catch(错误=> {//在这里处理/报告错误...控制台错误(错误)；});}

"use strict";//*** 使用严格模式//*** 声明你的变量(旧代码依赖于隐式全局变量的恐怖，它//严格模式修复)让 k = [];//*** 始终使用分号(或始终依赖 ASI)让 len = 100;让时间 = 真；const cont = document.getElementsByClassName("cont")[0];//*** 不要重复代码，只需使用`reset`重启();功能重置(){k = [];//*** 不要在 `innerHTML` 上使用 +=让 html = "";for (让 i = 0; i < len; i++) {//*** 声明你的变量const t = Math.round(Math.random() * 800 ) + 5;k.push(t);html += makeBlock(t);}cont.innerHTML = html;}函数makeBlock(值){return "<div class='block' style = 'height:" + value + "px'></div>";}函数 *sortGen() {for (let i = 0; i < len; ++i) {for (让 j = 0; j  k[j + 1]) {让 tmp = k[j];k[j] = k[j + 1];k[j + 1] = tmp;产量 j;//*** 屈服于调用者，说明发生了什么变化}}}}const nextFrame = cb =>新承诺(解决 => {requestAnimationFrame(() => {cb();解决();});});函数气泡(){(异步() => {for await (sortGen() 的常量值) {等待 nextFrame(() => {const el = cont.children[值];const next = el.nextElementSibling;el.parentElement.insertBefore(next, el);});}})().catch(错误=> {//在这里处理/报告错误...控制台错误(错误)；});}

.cont {宽度:100%；高度:900px；显示:块；背景颜色:粉红色；填充:0px；显示:-webkit-box；显示:-ms-flexbox;显示:弹性；-webkit-box-pack: 中心；-ms-flex-pack:居中；对齐内容:居中；-ms-flex-line-pack:居中；对齐内容:居中；}/* *** 不要在行尾隐藏关闭 } */.cont .block {显示:内联块；宽度:10px；边距:自动 1px；背景颜色:红色；字体大小:5px；底部:0px；}/* *** 不要在行尾隐藏关闭 } */

 重置数组<button class="bubble" onclick="bubble()">冒泡排序<div class="cont">

也在 CodePen 上.

k = []
len = 100;
time = true

cont = document.getElementsByClassName("cont")[0];
cont.innerHTML = "";
for (let i = 0; i < len; i++) {
    t = Math.round(Math.random() * 800 ) + 5
    k.push(t);
    cont.innerHTML += "<div class='block' style = 'height:" + t + "px'></div>"
}


function reset(){
    k = []
    cont.innerHTML = "";
    for (let i = 0; i < len; i++) {
        t = Math.round(Math.random() * 800 ) + 5
        k.push(t);
        cont.innerHTML += "<div class='block' style = 'height:" + t + "px'> </div>"
    }

}

function bubble(){
    function iloop(i){
        if(i < len){
        setTimeout(function(){
            function jloop(j){
                if(j < len){
                setTimeout(function(){
                    if (k[j] > k[j + 1]) {
                        let tmp = k[j];
                        k[j] = k[j + 1];
                        k[j + 1] = tmp;
                    }
                    cont.innerHTML = "";
                    for (let p = 0; p < len; p++) {
                        cont.innerHTML += "<div class='block' style = 'height:" + k[p] + "px'></div>"
                    }
                    j++;
                    jloop(j);
                }, 100);
                }
            }
            jloop(0);



            i++;
            iloop(i);
        }, 100);
        }
    }
    iloop(0);
}

.cont {
  width: 100%;
  height: 900px;
  display: block;
  background-color: pink;
  padding: 0px;
  display: -webkit-box;
  display: -ms-flexbox;
  display: flex;
  -webkit-box-pack: center;
  -ms-flex-pack: center;
  justify-content: center;
  -ms-flex-line-pack: center;
  align-content: center; }
  .cont .block {
    display: inline-block;
    width: 10px;
    margin: auto 1px;
    background-color: red;
    font-size: 5px;
    bottom: 0px; }

<button class="reset" onclick="reset()">Reset Array
</button> 
<button class="bubble" onclick="bubble()">Bubble Sort
</button> 
<div class="cont"> 
 </div>

I am using this simple code to make a javascript visualizer for sorting algorithm but the problem is that it is very choppy and skips multiples frames while running even at a delay of 100ms. I have an i7 7700hq and gtx 1060 so I know that the problem is mostly not my laptop but my approach to it so what approach should I take

Here is a code pen version if your snippets are not working https://codepen.io/varunagarwal/pen/gOaQqbG

Edit: someone told me to make it a runnable snippet so there you go

解决方案

You have overlapping setTimeout timers, and a lot of them being scheduled. You only want to yield back to the browser when there's a change to show, and you only want to show a given change once.

Since you're using ES2015+, I'd probably use a generator function to do the sort, yielding when something changes:

function *sortGen() {
    for (let i = 0; i < len; ++i) {
        for (let j = 0; j < len; ++j) {
            if (k[j] > k[j + 1]) {
                let tmp = k[j];
                k[j] = k[j + 1];
                k[j + 1] = tmp;
                yield j; // *** Yield to caller, saying what changed
            }
        }
    }
}

Then the code calling it would call its next method, do the update, and then schedule callback for just before the next animation frame via requestAnimationFrame (unless you want to artificially slow it down, in which case setTimeout is fine). Animation frames happen 60 times/second (roughly every 16.666667ms) provided the browser isn't busy doing something else. Here's bubble using the generator from the sortGen function above:

function bubble() {
    const gen = sortGen();
    tick();

    function tick() {
        const result = gen.next();
        if (!result.done) {
            // *** No need to recreate all the elements, just reorder the ones that got swapped
            const el = cont.children[result.value];
            const next = el.nextElementSibling;
            el.parentElement.insertBefore(next, el);
            requestAnimationFrame(tick);
        }
    }
}

(You could make it an async generator and use a for-await-of loop, but I don't think it really buys you much.)

Here's a live example; I've also included some comments in the code making other suggestions:

"use strict"; // *** Use strict mode

// *** Declare your variables (the old code relied on The Horror of Implicit Globals, which
// strict mode fixes)
let k = []; // *** Consistently use semicolons (or consistently rely on ASI)
let len = 100;
let time = true;

const cont = document.getElementsByClassName("cont")[0];
// *** Don't duplicate code, just use `reset`
reset();

function reset(){
    k = [];
    // *** Never use += on `innerHTML`
    let html = "";
    for (let i = 0; i < len; i++) {
        // *** Declare your variables
        const t = Math.round(Math.random() * 800 ) + 5;
        k.push(t);
        html += makeBlock(t);
    }
    cont.innerHTML = html;
}

function makeBlock(value) {
    return "<div class='block' style = 'height:" + value + "px'></div>";
}

function *sortGen() {
    for (let i = 0; i < len; ++i) {
        for (let j = 0; j < len; ++j) {
            if (k[j] > k[j + 1]) {
                let tmp = k[j];
                k[j] = k[j + 1];
                k[j + 1] = tmp;
                yield j; // *** Yield to caller, saying what changed
            }
        }
    }
}

function bubble() {
    const gen = sortGen();
    tick();

    function tick() {
        const result = gen.next();
        if (!result.done) {
            // *** No need to recreate all the elements, just reorder the ones that got swapped
            const el = cont.children[result.value];
            const next = el.nextElementSibling;
            el.parentElement.insertBefore(next, el);
            requestAnimationFrame(tick);
        }
    }
}

.cont {
  width: 100%;
  height: 900px;
  display: block;
  background-color: pink;
  padding: 0px;
  display: -webkit-box;
  display: -ms-flexbox;
  display: flex;
  -webkit-box-pack: center;
  -ms-flex-pack: center;
  justify-content: center;
  -ms-flex-line-pack: center;
  align-content: center;
} /* *** Don't hide closing } at the end of a line */
.cont .block {
  display: inline-block;
  width: 10px;
  margin: auto 1px;
  background-color: red;
  font-size: 5px;
  bottom: 0px;
} /* *** Don't hide closing } at the end of a line */

<button class="reset" onclick="reset()">Reset Array
</button> 
<button class="bubble" onclick="bubble()">Bubble Sort
</button> 
<div class="cont"> 
</div>

Also on CodePen.

For what it's worth, the async generator approach looks something like this:

const nextFrame = cb => new Promise(resolve => {
    requestAnimationFrame(() => {
        cb();
        resolve();
    });
});

function bubble() {
    (async () => {
        for await (const value of sortGen()) {
            await nextFrame(() => {
                const el = cont.children[value];
                const next = el.nextElementSibling;
                el.parentElement.insertBefore(next, el);
            });
        }
    })()
    .catch(error => {
        // Handle/report error here...
        console.error(error);
    });
}

"use strict"; // *** Use strict mode

// *** Declare your variables (the old code relied on The Horror of Implicit Globals, which
// strict mode fixes)
let k = []; // *** Consistently use semicolons (or consistently rely on ASI)
let len = 100;
let time = true;

const cont = document.getElementsByClassName("cont")[0];
// *** Don't duplicate code, just use `reset`
reset();

function reset(){
    k = [];
    // *** Never use += on `innerHTML`
    let html = "";
    for (let i = 0; i < len; i++) {
        // *** Declare your variables
        const t = Math.round(Math.random() * 800 ) + 5;
        k.push(t);
        html += makeBlock(t);
    }
    cont.innerHTML = html;
}

function makeBlock(value) {
    return "<div class='block' style = 'height:" + value + "px'></div>";
}

function *sortGen() {
    for (let i = 0; i < len; ++i) {
        for (let j = 0; j < len; ++j) {
            if (k[j] > k[j + 1]) {
                let tmp = k[j];
                k[j] = k[j + 1];
                k[j + 1] = tmp;
                yield j; // *** Yield to caller, saying what changed
            }
        }
    }
}

const nextFrame = cb => new Promise(resolve => {
    requestAnimationFrame(() => {
        cb();
        resolve();
    });
});

function bubble() {
    (async () => {
        for await (const value of sortGen()) {
            await nextFrame(() => {
                const el = cont.children[value];
                const next = el.nextElementSibling;
                el.parentElement.insertBefore(next, el);
            });
        }
    })()
    .catch(error => {
        // Handle/report error here...
        console.error(error);
    });
}

.cont {
  width: 100%;
  height: 900px;
  display: block;
  background-color: pink;
  padding: 0px;
  display: -webkit-box;
  display: -ms-flexbox;
  display: flex;
  -webkit-box-pack: center;
  -ms-flex-pack: center;
  justify-content: center;
  -ms-flex-line-pack: center;
  align-content: center;
} /* *** Don't hide closing } at the end of a line */
.cont .block {
  display: inline-block;
  width: 10px;
  margin: auto 1px;
  background-color: red;
  font-size: 5px;
  bottom: 0px;
} /* *** Don't hide closing } at the end of a line */

<button class="reset" onclick="reset()">Reset Array
</button> 
<button class="bubble" onclick="bubble()">Bubble Sort
</button> 
<div class="cont"> 
</div>

Also on CodePen.

这篇关于Java Script 排序算法可视化工具的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！