Code Is Art

文章列表

2009-06-11 10:09

function merge(array,start,middle,end) {
            var n1 = middle - start + 1,
                n2 = end - middle,
                left = Array(n1),
                right = Array(n2),
                i, j, k;

                for (i = 0; i < n1; i++ ) {
                    left[i] = array[start + i];
                }

                for (j = 0; j < n2; j++) {
                    right[j] = array[middle + 1 + j];
                }

               left[left.length]     =
   right[right.length] = Number.MAX_VALUE;

                i = j = 0;

                for (k = start; k <= end; k ++) {
                    if (left[i] <= right[j]) {
                        array[k] = left[i];
                        i++;
                    } else {
                        array[k] = right[j];
                        j++;
                    }
                }
        }

        function mergeSort(array,start,end) {
            var middle;

            if (start < end) {
                middle = Math.floor((start + end)/2);

                mergeSort(array,start,middle);
                mergeSort(array,middle + 1,end);

                merge(array,start,middle,end)
            }

            return array;
        }

        /*====Test====*/
        var nums = [3,4,1,5,999,234,90,33,222];
        alert(mergeSort(nums,0,nums.length - 1)); //->1,3,4,5,33,90,222,234,999

基本原理可阅读这篇文章，非常的详细，用Javascript实现也轻而易举。

类别：算法 | 评论(0) | 浏览()

算法学习(1):插入法排序

2009-06-09 23:25

类别：算法 | 评论(0) | 浏览()

Object构造函数浅析(兼对Douglas Crockford原型继承实现方式的质疑)

2009-05-12 18:54

Douglas Crockford曾经做了一个名为"Advanced JavaScript"的演讲,关于原型继承(Prototypal Inheritance),他是这样实现的:

var oldObject = {
    firstMethod: function () {...},
    secondMethod: function () {...}
};

var newObject = object(oldObject);
      newObject.thirdMethod = function () {...};

var myDoppelganger = object(newObject);
     myDoppelganger.firstMethod();

并且提到(第12页幻灯片):

“Using the object function, we can quickly produce new objects that have the same state and behavior as existing objects.”
(通过使用object函数，我们能够快速的生成一个属性和方法与已存在对象相同的对象)

幻灯片地址：http://yuiblog.com/assets/crockford/advancedjavascript.zip

果真如此吗？

Object构造函数内部实现

运行Object()时，到底内部是怎么实现的呢？我们翻开Ecma_262文档来看一下(第96页):

new Object ( [ value ] )
When the Object constructor is called with no arguments or with one argument value, the following
steps are taken:
1. If value is not supplied, go to step 8.
2. Ifthetypeof value isnotObject,gotostep5.
3. If the value is a native ECMAScript object, do not create a new object but simply return value.
4. If the value is a host object, then actions are taken and a result is returned in an implementation-
dependent manner that may depend on the host object.
5. Ifthetypeof value is String, return ToObject(value).
6. Ifthetypeof value is Boolean, return ToObject(value).
7. Ifthetypeof value is Number, return ToObject(value).
8. (The argument value was not supplied or its type was Null or Undefined.)
Create a new native ECMAScript object.
The [[Prototype]] property of the newly constructed object is set to the Object prototype object.
The [[Class]] property of the newly constructed object is set to "Object".
The newly constructed object has no [[Value]] property.
Return the newly created native object

从第3条我们可以看到，调用Object(someObj)并不会产生一个新的对象，而是返回原始的someObj，于是我们有理由相信，上面Douglas Crockford的代码中:

     oldObject === newObject === myDoppelganger

这3个变量，引用的是同一个对象。

测试

我们稍微修改一下Douglas的代码，使之可运行:

var obj1 = {
    'p1' : 'obj1-p'
};

var obj2 = Object(obj1);
     obj2['p2'] = 'obj2-p';

var obj3 = Object(obj2);
     obj3['p3'] = 'obj3-p';

alert(obj1 === obj3); //-> true
alert(obj1.p2);           //-> obj2-p
alert(obj1.p3);           //-> obj3-p

可以看出，obj1，obj2，obj3引用的确实是同一个对象。Douglas老头写这个幻灯片的时候打瞌睡去了吗？

类别：Javascript | 评论(3) | 浏览()

JavaScript小技巧(1):妙用Array.prototype.slice方法

2009-04-23 21:48

Javascript中，Array对象的slice方法通常用于获得数组的一部分.常规的使用我就不探讨了，我们谈点特别的。

1.复制数组

用slice方法来复制一个数组实在是太方便了。看代码：
var a = [1, 2, 3];
var b = a.slice();
console.log(b); //-> [1, 2, 3]

没错，我们只要简简单的slice一下，不传递任何参数，就得到了一个新的数组。
当然，复制数组还有其他简便的方式，比如运用concat方法:

var a = [1, 2, 3];
var b = [].concat(a);
console.log(b); //->[1, 2, 3]

选哪种方法取决于你的喜好了:-)

2.将"类数组对象"转换成数组对象

所谓类数组对象，就是具有数组的某些特征，最基本的就是拥有索引元素和长度属性，比如function对象的
arguments对象，还有通过dom方法getElementsByTagName()获得的Html元素集。它们都具有数组的特征，比如可以通过下标访问以及拥有length属性，但是它们又不是真正的数组，不具备数组对象的其他方法（如push,pop,concat,slice,splice等）。

尽管大多数时候我们并不要求它们是一个真正的数组，但有时候确实非常需要（相信你碰到过),Douglas Crockford也说，没有把arguments对象实现成一个真正的数组对象是Javascript语言设计的一个错误。那么怎么把这些"类数组对象"快速转换成一个数组呢？用slice方法吧!

但是我们无法直接在这些"类数组对象"上运用slice方法，因为他们压根就不是数组！ok，那我们就采用apply调用的方式，如下:

var realArray = Array.prototype.slice.apply(arrayLike);

我们来实践一下:

function test(a, b, c) {
    arguments = Array.prototype.slice.apply(arguments);

    console.log(arguments instanceof Array);
}

test(1, 2, 3); //-> true

再看一个例子:

var elements = document.getElementsByTagName('*');
      elements = Array.prototype.slice.apply(elements);

console.log(elements instanceof Array); //->true

更狠的:
var someObj = {
    '0' : 'hello',
    '1' : 'world',
    'length' : 2
};

var arrayObj = Array.prototype.slice.apply(someObj);
console.log(arrayObj); //-> ['hello','world']

可以看到，只要“类数组对象”具有索引元素和length，slice方法就能把它们转换成一个真正的数组。

如果你觉得Array.prototype.slice.apply()的写法太麻烦了，好办，我们可以绑定到Array.prototype上面

Array.prototype.makeArray= function (arrayLike) {
   if ( !arrayLike || !arrayLike.length || !/^\d+$/.test('' + arrayLike.length) ) {
        return []; //如果arrayLike为undefined，或者它没有length属性，或者它的length属性不是数字，返回空数组
    }

    return this.slice.apply(arrayLike);
};

这样，我们就能以下面的方式调用了:

var realAray = [].makeArray(arrayLike);

似乎和上面复制数组的方式相似:-)

ok，让我们和以前繁琐的处理方式说拜拜吧!

Update

多谢Erik提醒，我找到Ecma_262文档，查看了slice方法的内部实现方式,指南如下:

15.4.4.10 Array.prototype.slice (start, end)
The slice method takes two arguments, start and end, and returns an array containing the elements
of the array from element start up to, but not including, element end (or through the end of the array
if end is undefined). If start is negative, it is treated as (length+start)where length is the length of
the array. If end is negative, it is treated as (length+end)where length is the length of the array. The
following steps are taken:

1. Let A be a new array created as if by the expression new Array().

   创建一个新数组A。

2. Call the [[Get]] method of this object with argument "length".
  调用当前对象的[[Get]]方法，参数为'length'.

3. Call ToUint32(Result(2)).
  将Result(2),即length,转换为无符号32位整数。

4. Call ToInteger(start).
  将start转换成整数。

5. If Result(4) is negative, use max((Result(3)+Result(4)),0); else use min(Result(4),Result(3))
   如果start为负数，使用0和(length + start)中较大的一个;否则，使用start和length中较小的一个。

6. Let k be Result(5).
  将 k 赋值为第5步计算结果,即 k = start.

7. If end is undefined, use Result(3); else use ToInteger(end).
   如果end未定义(没有传递第二个参数),那么end值为length，否则，将第二个参数转换成整数并赋值给end

8. If Result(7) is negative, use max((Result(3)+Result(7)),0); else use min(Result(7),Result(3))
  如果end为负，将赋值为 0 和 (length + end) 中较大的一个;否则，赋值为 end 和 length中较小的一个。

9. Let n be 0.
  将n赋值为0.

10. If k is greater than or equal to Result(8), go to step 19.
   如果 k, 即start,大于等于第8部结果，即end，转到第19步.

11. Call ToString(k).
   将K 转换成字符串。

12. If this object has a property named by Result(11), go to step 13; but if this object has no    property named by Result(11), then go to step 16.
   如果该对象拥有属性K，转到第 13 步;如果没有，转到第16步。

13. Call ToString(n).
    将n转换成字符串.

14. Call the [[Get]] method of this object with argument Result(11).
    调用当前对象的[[Get]]方法，参数为第11步结果，即k.

15. Call the [[Put]] method of A with arguments Result(13) and Result(14).
    调用数组A的[[Put]]方法,参数为n和k

16. Increase k by 1.
     k增加1.

17. Increase n by 1.
     n增加1

18. Go to step 10.
     转到第10步

19. Call the [[Put]] method of A with arguments "length" and n.
     调用数组A的[[put]]方法,参数为'length' 和 n.

20. Return A.
      返回数组A.

从上面我们可以看出，slice方法返回的是一个新数组，被转换的对象必须拥有length属性，如果没有length属性，其行为是未定义的，第2步并没有指明如果读取length属性失败怎么办，所幸的是，Mozilla和IE都将返回一个空数组而不是抛出异常。

还有一个意外是，当读取转换对象某个索引属性值失败时，比如读取Obj[1],但是obj并没有属性1，按照指南，新数组将不会新增元素，但是Mozilla和IE都不一而同的给新数组push了一个undefined.

看代码:
   var testObj = {
        '1' : 'hell',
        '3' : 'world',
        'length' : '4'
   }

   Array.prototype.slice.apply(testObj); //-> [undefined,'hell',undefined,'world']

类别：Javascript | 评论(2) | 浏览()