论left-pad函数的实现

@shengxinjing 2016-03-24 04:33:59发表于 shengxinjing/my_blog 前端

论left-pad的实现

这两天微博上看到左耳朵耗子吐槽了一下node社区的left-pad的代码,原po链接

01

我也思考了一下 怎么用实现一个left-pad比较合适,上图代码确实比较搓
leftpad功能,就是字符串前面拼指定字符到固定长度,比如
leftpad('hello',20,'1'),就要返回'111111111111111hello'

版本1 用数组+join


function leftpad(str, len, ch) {
    if (!ch && ch !== 0) ch = ' ';
    var len = len - str.length;
    return Array(len).join(ch) + str;
}

版本2 用一个带length属性的对象去实现join,免去了创建arr的步骤,性能应该回好点


function leftpad(str, len, ch) {
    if (!ch && ch !== 0) ch = ' ';
    var len = len - str.length;
    return Array.prototype.join.call({
        length:len
    },ch)+str;
}

如果把Array.prototype.join缓存到外部变量里,多次使用速度更快

var _join = Array.prototype.join
function leftpad(str, len, ch) {
    if (!ch && ch !== 0) ch = ' ';
    var len = len - str.length;
    return _join.call({
        length:len
    },ch)+str;
}


版本3 二分法

上面复杂度都是O(N)的,既然核心思路是把字符串重复n次,可以用二分法,比如把s,重复20次,拼在str前面,大概过程如下

total = ''
ch = 's'
20是偶数
    ch变成ss
    长度变成10
        10是偶数
            ch变成ssss
            长度变成5
                5是奇数
                    total += ch(total变成ssss)
                    ch变成ssssssss(8个)
                    长度变成2
                        2是偶数
                            ch继续变成(ssssssssssssssss)(16个s)
                            长度变成1
                                total= total+ch(4个加16个)
                                结束代码 拼接str 返回

代码如下

function leftpad(str, len, ch) {
    if (!ch && ch !== 0) ch = ' ';
    var len = len - str.length,
        total = ''
    while (true) {
        // 如果len是基数,total上就加一个ch
        if (len % 2 == 1) total += ch;
        if (len == 1) return total + str;;
        // 每次ch都变成chch
        ch += ch;
        //长度减半
        len = parseInt(len / 2);
    }

}

最后写完这些,看了耗子大神微博贴的代码,突然想起求余和除以二取整,可以用 按位与len&1 和右移len>>1代替,囧,还是代码写的太少,没想到

最后代码


function leftpad(str, len, ch) {
    if (!ch && ch !== 0) ch = ' ';
    var len = len - str.length,
        total = ''
    while (true) {
        // 如果len是基数,total上就加一个ch
        if (len & 1 == 1) total += ch;
        if (len == 1) return total + str;;
        // 每次ch都变成chch
        ch += ch;
        //长度减半
        len = len>>1;

    }

}


最后再优化一下循环


function leftpad(str, len, ch) {
    if (!ch && ch !== 0) ch = ' ';
    var len = len - str.length,
        total = ''
    while (len) {
        // 如果len是基数,total上就加一个ch
        (len & 1) && (total += ch)
        // 每次ch都变成chch
        ch += ch;
        //长度减半
        len = len >> 1;

    }
    return total + str

}


大家可以尝试用python实现一下(不要用自带的rjust),本文仅提供一个思路,很小的一个功能函数,可能还会有很多更好的优化和实现,欢迎大家多指教写代码过程中还是要多思考,共勉
喜欢请star