Hello World
Spiga

使用Jscex实现排序算法动画

2011-03-10 23:35 by 老赵, 3255 visits

用动画来观察排序算法是一件很酷的事情,例如有人便为各种排序算法提供了动画效果。只可惜这些效果都是实现准备好的gif图片,并非由代码写成。在大部分平台上编写这样的程序并没有太大困难,只要在绘制出图形之后短暂地阻塞线程就行了。可惜,在JavaScript中我们只能“一蹴而就”,要暂停的话,只能使用setTimeout进行回调了。不过,这也正是Jscex的用武之地,用Jscex编写的代码需要“暂停”,只需要简单地调用sleep异步方法,一切都很直接。

例如,传统的冒泡排序算法,使用JavaScript实现可能是这样的:

var bubbleSort = function (array) {
    for (var x = 0; x < array.length; x++) {
        for (var y = 0; y < array.length - x; y++) {
            if (array[y] > array[y + 1]) {
                swap(array, y, y + 1);
            }
        }
    }
}

如果使用Jscex,则变成了:

var bubbleSortAsync = eval(Jscex.compile("$async", function (array) {
    for (var x = 0; x < array.length; x++) {
        for (var y = 0; y < array.length - x; y++) {
            var r = $await(compareAsync(array[y], array[y + 1]));
            if (r > 0) {
                $await(swapAsync(array, y, y + 1));
            }
        }
    }
}));

算法实现上唯一的变化可能就是“比较”方法被独立成单独的compareAsync方法了。它和swapAsync方法的代码如下:

var compareAsync = eval(Jscex.compile("$async", function (x, y) {
    $await(Jscex.Async.sleep(10));
    return x - y;
}));

var swapAsync = eval(Jscex.compile("$async", function (array, x, y) {
    var t = array[x];
    array[x] = array[y];
    array[y] = t;

    repaint(array);

    $await(Jscex.Async.sleep(20));
}));

简单地说,一个排序算法的性能如何,关键看它的比较和元素交换的次数。因此,我在compareAsync和swapAsync方法中都使用sleep进行了一定时间的停顿(其中后者更长一些)。由于改变了元素位置,因此在swapAsync方法中我还重新绘制了图案。有了这两个方法,我们只要将其简单地组合进bubbleSortAsync方法中即可。

我们轻松实现的冒泡排序算法,Jscex编译器则会将其转化为复杂的Monadic代码,我本想贴在这里,但发现过于复杂凌乱,也太占地方。如果您感兴趣可以打开浏览器的console窗口,查看其输出结果。基于Jscex实现的选择排序和快速排序也和传统实现可谓毫无二致:

var selectionSortAsync = eval(Jscex.compile("$async", function (array) {
    for (var j = 0; j < array.length - 1; j++) {
        var mi = j;
        for (var i = j + 1; i < array.length; i++) {
            var r = $await(compareAsync(array[i], array[mi]));
            if (r < 0) { mi = i; }
        }
        $await(swapAsync(array, mi, j));
    }
}));

var quickSortAsync = eval(Jscex.compile("$async", function (array) {
    $await(_quickSortAsync(array, 0, array.length - 1));
}));

var _quickSortAsync = eval(Jscex.compile("$async", function (array, begin, end) {
    var index = $await(_partitionAsync(array, begin, end));

    if (begin < index - 1) {
        $await(_quickSortAsync(array, begin, index - 1));
    }

    if (index < end) {
        $await(_quickSortAsync(array, index, end));
    }
}));

var _partitionAsync = eval(Jscex.compile("$async", function (array, begin, end) {
    var i = begin;
    var j = end;
    var pivot = array[Math.floor((begin + end) / 2)];

    while (i <= j) {
        while (true) {
            var r = $await(compareAsync(array[i], pivot));
            if (r < 0) { i++; } else { break; }
        }

        while (true) {
            var r = $await(compareAsync(array[j], pivot));
            if (r > 0) { j--; } else { break; }
        }

        if (i <= j) {
            $await(swapAsync(array, i, j));
            i++;
            j--;
        }
    }

    return i;
}));

言止于此,我们现在就来看一下(冒泡选择快速)三种排序方式的动画吧(请使用支持canvas的浏览器,例如IE 9、FireFox、Chrome、Safari)。我很难想象,使用传统方式实现一个快速排序的动画会是什么情况。

我最近愈发懒惰,愈发不愿意去想这些事情了。如今Jscex已经支持JavaSript语言中绝大部分语言特性,包括条件判断,各种循环(以及循环中的break和continue),还有异常处理等等。对于Jscex带来的编程体验我有十足的信心,但现在的最大问题却是不知道该如何推广。我也希望可以有更多人可以参与并接受这个项目。之前想过用它来实现一个小游戏等等,但素材方面却总是难以落实。我十分希望能从您那里得到各方面的意见和建议。

最后还是一则招聘广告:盛大创新院某英语学习方向的项目招聘1至2名ASP.NET程序员:

  • 岗位职责:负责服务器及数据库的搭建、维护工作,并配合前端工程师完成网站架构。
  • 岗位要求:熟悉.NET 3.5开发,有关系型数据库(MySQL优先)开发管理经验。有MongoDB等NoSQL开发经验者优先。有网站数据负载均衡经验者优先。
  • 办事认真踏实,对行业充满热情,了解行业最新动态。

很显然,这不是我的招聘需求,不过我也帮忙筛选面试。欢迎大家自荐或推荐,邮件请至:

Creative Commons License

本文基于署名 2.5 中国大陆许可协议发布,欢迎转载,演绎或用于商业目的,但是必须保留本文的署名赵劼(包含链接),具体操作方式可参考此处。如您有任何疑问或者授权方面的协商,请给我留言

Add your comment

20 条回复

  1. 化石
    61.170.133.*
    链接

    化石 2011-03-11 00:26:14

    有工具可以将compile放在js发布之前,而不是运行时。友好的调试支持。文档。

  2. Tianyi Cui
    207.46.92.*
    链接

    Tianyi Cui 2011-03-11 00:30:25

    关于推广,建议精心写一篇英文文章投到thechangelog.com,看上去jscex目前的成熟度应该达到了这个级别。这个用来排序算法动画的例子不错。

  3. 海水一滴
    58.246.103.*
    链接

    海水一滴 2011-03-11 07:46:20

    老赵老师,我想用asp.net C# ajax实现:鼠标移动到一个标签上就触发一个事件,并从数据库提取数据,将结果更新一个div。不知如何实现,请赐教。谢谢咯

  4. 徐凡
    210.22.155.*
    链接

    徐凡 2011-03-11 09:38:37

    感觉用gwt(http://code.google.com/webtoolkit/)的方式做预编译更好点。

  5. 老赵
    admin
    链接

    老赵 2011-03-11 09:39:13

    @海水一滴

    爱怎么做怎么做,学点AJAX和JavaScript、DOM之类的,应该很容易吧。

  6. bl_song
    117.22.187.*
    链接

    bl_song 2011-03-11 11:10:40

    很酷啊,要学习javascripts

  7. winter
    114.80.133.*
    链接

    winter 2011-03-12 16:57:40

    超赞啊赵老 这个用来演示状态机也很不错 我之前用回调写了一个累死了

  8. 老赵
    admin
    链接

    老赵 2011-03-12 21:39:04

    @徐凡

    预编译要做自然也是可以的,但我就想用最单纯的方式去做,不依赖其他任何虚拟机啊,程序啊等等。说到GWT,话说Google很喜欢把JavaScript当Java用,Closure Compiler也是这种概念。

  9. 老赵
    admin
    链接

    老赵 2011-03-12 21:44:27

    @winter

    他爹最厉害了,回调这东西既难写又难懂……

  10. blankyao
    219.133.62.*
    链接

    blankyao 2011-03-14 16:02:48

    这个写的很帅气!

  11. ShaneYao
    58.62.196.*
    链接

    ShaneYao 2011-03-24 12:27:31

    那快速排序可真够快,哈哈

  12. Errant
    203.166.221.*
    链接

    Errant 2011-03-25 14:52:58

    你好,最近在关注你的博客,也刚开始试着用jscex,边学边用。

    请教下。假如我想在一个jscex定义的函数里头在嵌套一个jscex定义的函数要怎么做呢?大概这个样子的代码:

    var lastFrame = 0;
    var container = eval(Jscex.compile("$async", function () {
        while(true){
            $await(Jscex.Async.sleep(1000));
            Jscex.Async.start(action());
        }
    }));
    
    var action = eval(Jscex.compile("$async", function() {
        $await(Jscex.Async.sleep(3000));
        var thisFrame = new Date().getTime();
        var dt = thisFrame - lastFrame;
        console.log(dt);
        lastFrame = thisFrame;
    }));
    

    我想他1000+3000=4000毫秒执行一次。但事实上都是1000秒输出一次。。想达到我期望的效果该怎么办呢?或者说,jscex本来就是这么设计的,是我使用理解上有问题?

  13. 老赵
    admin
    链接

    老赵 2011-03-25 15:20:34

    @Errant

    需要compile的函数定义就暂时不要嵌套了。

    你的代码写错了,下面这行代码:

    Jscex.Async.start(action());
    

    其实是用来“启动一个异步操作”的,不是“等待异步操作返回”。Jscex后的函数是可以组合的,其实就是用$await:

    $await(action());
    

    像Jscex.Async.sleep这种也只是内置的异步操作,action是你自定义的异步操作,两者的性质其实完全一样。

  14. Errant
    114.249.137.*
    链接

    Errant 2011-03-26 09:11:54

    其实我起初的想法是这样的。比方说有个包容处理碰撞,更新坐标,绘制画布,的循环需要1000毫秒执行一次。 但接受用户操作并响应的操作不需要那么频繁。3000毫秒执行一次就好了。我想把响应用户操作的函数嵌套在大循环里头。 所以才这么做的。。。不嵌套。是不是需要把判断用户操作的函数独立出来。然后同时一起启动两个循环?

  15. 老赵
    admin
    链接

    老赵 2011-03-26 22:40:13

    @Errant

    对的,按照你的意思应该是两个独立的异步操作,分别做循环。

  16. Code之行人
    221.172.59.*
    链接

    Code之行人 2011-03-26 23:23:02

    呵呵,动画把版本的,这是强大啊

  17. Z
    124.74.47.*
    链接

    Z 2011-06-28 15:16:48

    既然能用setTimeout/setInterval实现为什么还要用异步呢? 不是很鸡肋么? 如果说是因为不能随时暂停/继续, 写一个管理不就可以了么? 总体来说用武之地是什么地方呢?

  18. 老赵
    admin
    链接

    老赵 2011-06-28 16:05:27

    @Z

    本来提供的就是一种更好用的编程方式,你的意思其实就相当于“为什么C能做XXX还要有Java来做呢?如果说是因为不能YYY,写一个管理不就可以了么?”。

  19. Z
    124.74.47.*
    链接

    Z 2011-06-28 18:36:41

    好吧, 我确实白痴了... 贴一段我的异步实现 内附测试和一个冒泡排序

    ( function( window, undefined ) {
    
    var
    slice = Array.prototype.slice,
    guid = parseInt( Math.random() * 10000 );
    
    Function.prototype.async = function( thisp ) {
        var breakpoint = 0,
            varList = [ "temp" + guid ],
            async = "(" + this.toString().replace( /(\W)sleep[\ ]*\(([^\)]*)\)/g, function( all, separator, millisec ) {
                millisec = ~~millisec;
                breakpoint += millisec;
                return separator + "window.setTimeout(function(){ms" + guid + "(" + breakpoint + ");}," + millisec + ");break;case " + breakpoint + ":";
            } ).replace( /(\W)var(\W)([^;]*)/g, function( all, separator0, separator1, list ) {
                list = list.split( "," );
                var index = list.length;
                while ( index-- ) {
                    varList[ varList.length ] = list[ index ].split( "=" )[ 0 ].trim();
                }
                return list;
            } ).replace( "{", "{var " + varList.join( "," ) +
            ";return function(bp" + guid + ") {var ms" + guid + "=arguments.callee;switch(bp" + guid + "){case 0:" ) + "}})";
        async = eval( async );
        this.async = function( thisp ) {
            var callback = async.apply( thisp, slice.call( arguments, 1 ) );
            window.setTimeout( function() {
                callback( 0 );
            }, 0 );
        };
        this.async.apply( null, arguments );
    };
    
    Function.prototype.sync = function( thisp ) {
        this.sync = eval( "(" + this.toString().replace( /(\W)sleep[\ ]*\(([^\)]*)\)/g, function( all, separator, millisec ) {
            millisec = ~~millisec;
                return separator + "(function(){var et=+new Date+" + millisec + ";while(+new Date<et);})();";
            } ) + ")" );
        this.sync();
    };
    
    window.sleep = function() {};
    
    } )( window );
    
    
    /* Test */
    var timepoint = ~~( +new Date / 1000 );
    var log = function( a, b ) {
        console.log( ~~( +new Date / 1000 ) - timepoint, a, b );
    };
    
    var N = function() {
        console.log( "Hi~" );
        sleep( 5000 );
        console.log( "Oops!" );
    };
    
    var F = function( times ) {
        var n = 10;
        log( "F" + times, n++ );
        sleep( 1000 );
        log( "F" + times, n++ );
        N.async();
        sleep( 2000 );
        log( "F" + times, n++ );
    };
    
    var times = 0;
    
    var Y = function() {
        log( "Y" );
        F.async( null, times++ );
        log( "Y" );
    };
    
    Y();
    window.setTimeout( function() {
        Y();
    }, 1000 );
    
    
    /* principle
    var tF = ( function( times ) {
        var n = 10;
        return function( level ) {
            switch ( level ) {
            case 0:
                console.log( "F", getTime(), times, n++ );
                break;
            case 10:
                console.log( "F", getTime(), times, n );
                break;
            }
        };
    } )();
    
    tF( 0 );
    tF( 10 );
    */
    
    
    
    
    
    
    /* Bubble Sort */
    var
    list = [],
    index = 50;
    while ( index-- ) {
        list[ index ] = index * 4 + 4;
    }
    
    var ctx = document.getElementsByTagName( "Canvas" )[ 0 ].getContext( "2d" );
    
    var
    drawList = function() {
        var index = list.length;
        ctx.beginPath();
        while ( index-- ) {
            ctx.moveTo( index * 3 + 1.5, ctx.canvas.height );
            ctx.lineTo( index * 3 + 1.5, ctx.canvas.height - list[ index ] );
        }
        ctx.stroke();
        ctx.closePath();
    };
    
    var
    countTimes = 0,
    swapItem = function( a, b ) {
        var temp = list[ a ];
        list[ a ] = list[ b ];
        list[ b ] = temp;
    },
    bubbleStep = function() {
        var index = list.length;
        while ( index-- ) {
            if ( list[ index ] > list[ index + 1 ] ) {
                swapItem( index, index + 1 );
                return false;
            }
        }
        return true;
    },
    startSort = function( sortStep ) {
        ctx.clearRect( 0, 0, ctx.canvas.width, ctx.canvas.height );
        if ( sortStep() === true ) {
            drawList();
            console.log( "Count Times: " + countTimes );
            return;
        }
        drawList();
        countTimes += 1;
        sleep( 20 );
        startSort.async( null, bubbleStep );
    };
    
    list.sort( function() { return Math.random() > 0.5 ? 1 : 0; } );
    startSort.async( null, bubbleStep );
    
    
    
    /*
    var lastFrame = 0;
    var container = function () {
        while( true ){
            sleep( 1000 );
            action.sync();
        }
    };
    
    var action = function() {
        sleep( 3000 );
        var thisFrame = new Date().getTime();
        var dt = thisFrame - lastFrame;
        console.log(dt);
        lastFrame = thisFrame;
    };
    */
    
  20. 老赵
    admin
    链接

    老赵 2011-06-29 15:24:32

    @Z

    我觉得,看了你的代码就应该知道Jscex的优势了吧,呵呵。

发表回复

登录 / 登录并记住我 ,登陆后便可删除或修改已发表的评论 (请注意保留评论内容)

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

评论内容(大于5个字符):

  1. Your Name yyyy-MM-dd HH:mm:ss

使用Live Messenger联系我