如何在JavaScript中更高效地实现这些基数转字符串的函数？

Question

目前有这两个函数用于将整数转换为给定字符集的字符串，然后返回：

const parseInt = (value, code) => {
  return value.split('').reduce((r, a) => r * code.length + code.indexOf(a), 0)
}

const toString = (value, code) => {
  var digit,
    radix = code.length,
    result = '';

  do {
    digit = value % radix;
    result = code[digit] + result;
    value = Math.floor(value / radix);
  } while (value)

  return result;
}

toString(115, 'abcdefghijklmnop') // => 'hd'

但是，从 C 语言或静态内存分配的角度来看，它们效率低下。 result = code[digit] + result 正在构建一个字符串，一次一个字符，在每次迭代时完全重新生成字符链。

这怎么能精简成这样呢：

可能是预先计算了数组的大小，
从左到右而不是从反方向生成字符串？

在重新实现 toString 之后，您如何更改 parseInt 函数以解决反转 toString 的问题？

还有可能去掉Math.floor吗？如果没有，那没关系，但希望有可能有办法。如果遵守对字符集长度或输入大小的某些限制，如果有办法摆脱 Math.floor，请在评论中提及，我可能会为此提出另一个问题。谢谢！

显然您可以（以某种方式）反转函数并 add a .reverse() 在字符数组上，但理想情况下我们可以通过减去步骤（和重新排列）进行优化，而不是增加额外的步骤。这个要高度优化。

注。解决方案算法输出不必与上述算法相同。输出可以反转，没关系。只是寻找此函数的高度优化变体，它通常完成相同的事情：使用字符集将整数编码为字符串，然后将其反转以取回整数。

Answer 1

使用 radix 编码的严格正数 value 所需的位数由以下公式给出，t运行最接近的整数：

_⌊1 + log_radixvalue_⌋

看了你的问题，我怀疑你想避免浮点运算，所以上面的公式。那么你需要做一个“干运行”来查看你需要多大的存储结果，即通过迭代和整数运算计算上面的表达式。

这就是它的样子：

const parseInt = (value, code) => {
    let result = 0,
        radix = code.length;
    for (let a of value) {
        result = result * radix + code.indexOf(a);
    }
    return result;
}

const baseLog = (base, x) => Math.log2(x) / Math.log2(base);

const toString = (value, code) => {
    let digit,
        radix = code.length,
        result,
        len = 1,
        temp = value;
    
    // Calculate len = Math.max(1, 1 + Math.floor(baseLog(radix, value)))
    while (temp >= radix) {
        len++;
        temp = (temp - temp % radix) / radix;
    }
    // In another language you would allocate the memory here: 
    result = Array(len);
    do {
        digit = value % radix;
        len--;
        // Fill from back to start of array
        result[len] = code[digit];
        value = (value - digit) / radix;
    } while (len);

    return result.join(""); // Convert char-array to string
}

console.log(toString(115, 'abcdefghijklmnop')); // => 'hd'
console.log(parseInt("hd", 'abcdefghijklmnop')); // => 115

对数函数的解释

如果我们问这个问题“我们可以用 binary 写出的具有 8 位数字的最大整数是多少？”那么答案是：

11111111

如果我们问同样的问题，但是对于十六进制数字（还是8位），那么就是：

FFFFFFFF

如果是十进制数字，则为：

99999999

对于一个基数的所有选择，都是基数⁸−1。而当位数为n时，归纳为：

maxvalue = radixⁿ − 1

将1移到等式另一边，然后对两边取对数，得：

log_radix(maxvalue+1) = n

因此，如果我们得到的是值而不是位数，那么我们将得出位数 (n)：

n = ^⌈log_radix(value+1)^⌉

其中（对于整数值）等同于：

n = _⌊1 + log_radixvalue_⌋

如何在JavaScript中更高效地实现这些基数转字符串的函数？

How to more efficiently implement these radix to string functions in JavaScript?

javascript

string

algorithm

integer

radix

对数函数的解释