JS位向量快速排序和查找

Question

一、位向量快速排序：
<script type=text/javascript >
var i = 100000, arr = [];
while (i --) {
    arr.push(i + 1);
}
arr.sort(function(){return Math.random() > 0.6});
// -----------------------------------------------
var t = new Date(); 
var i = arr.length, j = 100001, bit = [], jsout = [];
while (i --) {
    bit[arr[i] >> 5] |= (1 << (arr[i] & 0x1f));
}
while (j --) {
    if (bit[j >> 5] & (1 << (j & 0x1f))) {
        jsout[jsout.length] = j;
    }
}
t = new Date() - t;
// ------------------------------------------------
alert("排序时间为：" + t + "毫秒\n");
alert("排序结果为：" + jsout.join("\n"));
</script>
二、位向量快速查找：例题：在1-100000连续正整数中删除5个，然后打乱顺序，请编码快速查找呗删除的5个数。
<script type=text/javascript >
var i = 100000, arr = [];
while (i --) {
    arr.push(i + 1);
}
m = arr.splice(Math.random() * arr.length, 1);
n = arr.splice(Math.random() * arr.length, 1);
o = arr.splice(Math.random() * arr.length, 1);
p = arr.splice(Math.random() * arr.length, 1);
q = arr.splice(Math.random() * arr.length, 1);
arr.sort(function(){return Math.random() > 0.6});
// -----------------------------------------------
var t = new Date(); 
var i = arr.length, j = 100001, k = 0, bit = [], jsout = [j], check = [];
while (i --) {
    bit[arr[i] >> 5] |= (1 << (arr[i] & 0x1f));
}
while (j --) {
    if (bit[j >> 5] & (1 << (j & 0x1f))) {
        jsout[1] = jsout[0], jsout[0] = j;
        k = jsout[1] - jsout[0];
        if (k == 2) {
            check = check.concat([jsout[0] + 1]);
        }
        if (k == 3) {
            check = check.concat([jsout[0] + 1, jsout[0] + 2]);
        }
        if (k == 4) {
            check = check.concat([jsout[0] + 1, jsout[0] + 2, jsout[0] + 3]);
        }
        if (k == 5) {
            check = check.concat([jsout[0] + 1, jsout[0] + 2, jsout[0] + 3, jsout[0] + 4]);
        }
        if (k == 6) {
            check = [jsout[0] + 1, jsout[0] + 2, jsout[0] + 3, jsout[0] + 4, jsout[0] + 5];
        }
    } 
    jsout.length = 2;
    if (check.length == 5) break;
}
if (jsout[0] == 2) {
    check = check.concat([1]);
}
if (jsout[0] == 3) {
    check = check.concat([1, 2]);
}
if (jsout[0] == 4) {
    check = check.concat([1, 2, 3]);
}
if (jsout[0] == 5) {
    check = check.concat([1, 2, 3, 4]);
}
if (jsout[0] == 6) {
    check = [1, 2, 3, 4, 5];
}
check.length = 5;
t = new Date() - t;
// ------------------------------------------------document.write("随机抽取的5个数为：" + m + " 和 " + n + " 和 " + o + " 和 " + p + " 和 " + q + "<br/>");
document.write("找到抽取的5个数为：" + check.join(" 和 ") + "<br/>");
document.write("查找时间为：" + t + "毫秒");
</script>
BTW：
     1、32位系统的运算参数为{32, 5, 0x1F}，64位的为{64, 6, 0x3F}。
     2、查找程式考虑效率采用while--循环，循环体外后面多出了一串if判断不简洁，怎样才能够在循环体内想法省掉呢？。
     3、貌似JS的数组很适合表达位向量空间，可以省略掉如下向量初始化循环，节约了资源：
           var i  = 1 + 集合中最大的数 / 32 ^ 0, bit = new Array(i);
           while (i--) {
                bit[i >> 5] &= ~(1 << (i & 0x1F));
           }

Answer 1

位向量快速查找代码简洁如下：<script type=text/javascript >
var i = 100000, arr = [], m = n = o = p = q = 0;
while (i --) {
    arr.push(i + 1);
}
m = arr.splice(Math.random() * arr.length, 1);
n = arr.splice(Math.random() * arr.length, 1);
o = arr.splice(Math.random() * arr.length, 1);
p = arr.splice(Math.random() * arr.length, 1);
q = arr.splice(Math.random() * arr.length, 1);
arr.sort(function(){return Math.random() > 0.6});
// -----------------------------------------------
var t = new Date(); 
var i = arr.length, j = 100001, k = d = 0, bit = [], jsout = [j], check = [];
while (i --) {
    bit[arr[i] >> 5] |= (1 << (arr[i] & 0x1f));
}
while (j --) {
    if (bit[j >> 5] & (1 << (j & 0x1f))) {
        jsout[1] = jsout[0], jsout[0] = d = j;
        k = jsout[1] - jsout[0];
        if (k == 2) {
            check[check.length] = j + 1;
        } else if (k > 2) {
            while (-- k) {
                check[check.length] = j + k;
            }
        }  
    } 
    jsout.length = 2;
    if (check.length == 5) break;
}
if (d) {
    while (d --) {
        check[check.length] = d;
    }
}
check.length = 5;
t = new Date() - t;
// ------------------------------------------------
document.write("随机抽取的5个数为：" + m + " 和 " + n + " 和 " + o + " 和 " + p + " 和 " + q + "<br/>");
document.write("找到抽取的5个数为：" + check.join(" 和 ") + "<br/>");
document.write("查找时间为：" + t + "毫秒");
</script>
以上简洁下下对性能影响不大。其实，简洁的代码往往效率低下。

Answer 2

再次修改：<script type=text/javascript >
var i = 100000, arr = [], m = n = o = p = q = 0;
while (i --) {
    arr.push(i + 1);
}
m = arr.splice(Math.random() * arr.length, 1);
n = arr.splice(Math.random() * arr.length, 1);
o = arr.splice(Math.random() * arr.length, 1);
p = arr.splice(Math.random() * arr.length, 1);
q = arr.splice(Math.random() * arr.length, 1);
arr.sort(function(){return Math.random() > 0.6});
// -----------------------------------------------
var t = new Date(); 
var i = arr.length, j = 100001, k = d = 0, bit = [], jsout = [j], check = [];
while (i --) {
    bit[arr[i] >> 5] |= (1 << (arr[i] & 0x1f));
}
while (j --) {
    if (bit[j >> 5] & (1 << (j & 0x1f))) {
        jsout[1] = jsout[0], jsout[0] = d = j;
        k = jsout[1] - jsout[0];
        if (k == 2) {
            check[check.length] = j + 1;
        } else if (k > 2) {
            while (-- k) {
                check[check.length] = j + k;
            }
        }  
    } 
    jsout.length = 2;
    if (check.length == 5) break;
}
if (check.length < 5) {
    while (d --) {
        check[check.length] = d;
        if (check.length == 5) break;
    }
}
t = new Date() - t;
// ------------------------------------------------
document.write("随机抽取的5个数为：" + m + " 和 " + n + " 和 " + o + " 和 " + p + " 和 " + q + "<br/>");
document.write("找到抽取的5个数为：" + check.join(" 和 ") + "<br/>");
document.write("查找时间为：" + t + "毫秒");
</script>
在firefox下12毫秒左右

Answer 3

删掉循环体内多余语句“sout.length=2”效率提高明显，在firefox下查找时间缩短到了8毫秒左右。<script type=text/javascript >
var i = 100000, arr = [], m = n = o = p = q = 0;
while (i --) {
    arr.push(i + 1);
}
m = arr.splice(Math.random() * arr.length, 1);
n = arr.splice(Math.random() * arr.length, 1);
o = arr.splice(Math.random() * arr.length, 1);
p = arr.splice(Math.random() * arr.length, 1);
q = arr.splice(Math.random() * arr.length, 1);
arr.sort(function(){return Math.random() > 0.6});
// ----------------------------------------------------------------------------
var t = new Date(); 
var i = arr.length, j = 100001, k = d = 0, bit = [], jsout = [j, 0], check = [];
while (i --) {
    bit[arr[i] >> 5] |= (1 << (arr[i] & 0x1f));
}
while (j --) {
    if (bit[j >> 5] & (1 << (j & 0x1f))) {
        jsout[1] = jsout[0], jsout[0] = d = j;
        k = jsout[1] - jsout[0];
        if (k == 2) {
            check[check.length] = j + 1;
        } else if (k > 2) {
            while (-- k) {
                check[check.length] = j + k;
            }
        }  
    }
    if (check.length == 5) break;
}
if (check.length < 5) {
    while (d --) {
        check[check.length] = d;
        if (check.length == 5) break;
    }
}
t = new Date() - t;
// -----------------------------------------------------------------------------
document.write("随机抽取的5个数为：" + m + " 和 " + n + " 和 " + o + " 和 " + p + " 和 " + q + "<br/>");
document.write("找到抽取的5个数为：" + check.join(" 和 ") + "<br/>");
document.write("查找时间为：" + t + "毫秒");
</script>