常用域でO(1)のleftpad

常用領域(追加するスペース/0の数が25個ぐらいだろうという想定)だとO(1)なleftpad実装です。チートです。0とスペース以外を埋めることはない、という割りきりで、それ以外が来たら拒否します。

常用領域外はO(n)ですが、O(n)表記は定数ぶぶんは省略してしまうので表記だけ見ても違いは分からないのですが、同じO(n)でも25個ずつ繋ぐので、最大で25倍速いです。node.js 5.7を利用してます。

	4	8	16	32	64	128
leftpad	12	80	179	320	552	1100
lodash.startPad	60	219	237	257	275	303
チート版	12	15	13	24	31	49

数値は処理時間(mS)なので、短いほど良いという表です。

3/27追加: 要望があったのでlodash.startPad()との比較を追加

コードはPublic Domain(Unlicense)です。

leftpad.js

'use strict';

var padStart = require("lodash").padStart;

var spaces = [
    '',
    ' ',
    '  ',
    '   ',
    '    ',
    '     ',
    '      ',
    '       ',
    '        ',
    '         ',
    '          ',
    '           ',
    '            ',
    '             ',
    '              ',
    '               ',
    '                ',
    '                 ',
    '                  ',
    '                   ',
    '                    ',
    '                     ',
    '                      ',
    '                       ',
    '                        ',
    '                         '];

var zeros = [
    '',
    '0',
    '00',
    '000',
    '0000',
    '00000',
    '000000',
    '0000000',
    '00000000',
    '000000000',
    '0000000000',
    '00000000000',
    '000000000000',
    '0000000000000',
    '00000000000000',
    '000000000000000',
    '0000000000000000',
    '00000000000000000',
    '000000000000000000',
    '0000000000000000000',
    '00000000000000000000',
    '000000000000000000000',
    '0000000000000000000000',
    '00000000000000000000000',
    '000000000000000000000000',
    '0000000000000000000000000'];


// left-pad
function leftpad1(str, len, ch) {
  str = String(str);

  var i = -1;

  if (!ch && ch !== 0) ch = ' ';

  len = len - str.length;

  while (++i < len) {
    str = ch + str;
  }

  return str;
}

// チート版
function leftpad2(str, len, ch) {
  str = String(str);
  var chars;
  if (!ch && ch !== 0) chars = spaces;
  else if (ch === 0) chars = zeros;
  else if (ch === ' ') chars = spaces;
  else throw new Error("ch should be ' ' or 0");

  len = len - str.length;
  if (len < 1) {
    return str;
  } else if (len < 25) {
    return chars[len] + str;
  }
  var len2 = Math.floor(len / 25);
  var pad = chars[len % 25];
  for (var i=0; i<len2; i++) {
    pad += chars[25];
  }
  return pad + str
}

const len = parseInt(process.argv[2], 10);
const count = 1000000;

console.log("pad length", len);

console.log("leftpad1", leftpad1('aaaa', len, 0))
console.time('leftpad1');
for (let i = 0; i < count; i++) {
    leftpad1('aaaa', len, 0);
}
console.timeEnd('leftpad1');

console.log("padStart", padStart('aaaa', len, 0))
console.time('padStart');
for (let i = 0; i < count; i++) {
    padStart('aaaa', len, 0);
}
console.timeEnd('padStart');

console.log("leftpad2", leftpad2('aaaa', len, 0))
console.time('leftpad2');
for (let i = 0; i < count; i++) {
    leftpad2('aaaa', len, 0);
}
console.timeEnd('leftpad2');