javascript - 使用 Javascript 在 localStorage 中存储大型整数数组的最有效方法

Question

*"Efficient" here basically means in terms of smaller size (to reduce the IO waiting time), and speedy retrieval/deserialization times. Storing times are not as important.

我必须在浏览器的 localStorage 中存储几十个整数数组，每个数组有 0-50 范围内的 1800 个值——也就是说，作为一个字符串。

显然，最简单的方法就是JSON.stringify，但是，考虑到数据的范围是众所周知的，这会添加很多不必要的信息。这些数组之一的平均大小约为 5500 字节。

这是我尝试过的其他一些方法(结果大小，以及最后反序列化 1000 次的时间)

• 对数字进行零填充，使每个数字的长度为 2 个字符，例如:

  [5, 27, 7, 38] ==> "05270738"
  

• base 50 编码:

  [5, 11, 7, 38] ==> "5b7C"
  

• 仅使用该值作为字符代码(添加 32 以避免开头出现奇怪的控制字符):

  [5, 11, 7, 38] ==> "%+'F" (String.fromCharCode(37), String.fromCharCode(43) ...)
  

这是我的结果:

                  size     Chrome 18   Firefox 11
-------------------------------------------------
JSON.stringify    5286          60ms         99ms
zero-padded       3600         354ms        703ms
base 50           1800         315ms        400ms
charCodes         1800          21ms        178ms

我的问题是是否有更好的方法我还没有考虑过？

更新
MДΓΓБДLL 建议对数据使用压缩。 Combining this LZW implementation以 50 为基数和 charCode 数据。我还测试了 aroth 的代码(将 4 个整数打包成 3 个字节)。我得到了这些结果:

                  size     Chrome 18   Firefox 11
-------------------------------------------------
LZW base 50       1103         494ms        999ms
LZW charCodes     1103         194ms        882ms
bitpacking        1350        2395ms        331ms

Answer 1

如果您的范围是 0-50，那么您可以将 4 个数字打包成 3 个字节(每个数字 6 位)。这将允许您使用约 1350 个字节存储 1800 个数字。这段代码应该可以做到:

window._firstChar = 48;

window.decodeArray = function(encodedText) {
    var result = [];
    var temp = [];

    for (var index = 0; index < encodedText.length; index += 3) {
        //skipping bounds checking because the encoded text is assumed to be valid
        var firstChar = encodedText.charAt(index).charCodeAt() - _firstChar;
        var secondChar = encodedText.charAt(index + 1).charCodeAt() - _firstChar;
        var thirdChar = encodedText.charAt(index + 2).charCodeAt() - _firstChar;

        temp.push((firstChar >> 2) & 0x3F);    //6 bits, 'a'
        temp.push(((firstChar & 0x03) << 4) | ((secondChar >> 4) & 0xF));  //2 bits + 4 bits, 'b'
        temp.push(((secondChar & 0x0F) << 2) | ((thirdChar >> 6) & 0x3));  //4 bits + 2 bits, 'c'
        temp.push(thirdChar & 0x3F);  //6 bits, 'd'

    }

    //filter out 'padding' numbers, if present; this is an extremely inefficient way to do it
    for (var index = 0; index < temp.length; index++) {
        if(temp[index] != 63) {
            result.push(temp[index]);
        }            
    }

    return result;
};

window.encodeArray = function(array) {
    var encodedData = [];

    for (var index = 0; index < dataSet.length; index += 4) {
        var num1 = dataSet[index];
        var num2 = index + 1 < dataSet.length ? dataSet[index + 1] : 63;
        var num3 = index + 2 < dataSet.length ? dataSet[index + 2] : 63;
        var num4 = index + 3 < dataSet.length ? dataSet[index + 3] : 63;

        encodeSet(num1, num2, num3, num4, encodedData);
    }

    return encodedData;
};

window.encodeSet = function(a, b, c, d, outArray) {
    //we can encode 4 numbers in 3 bytes
    var firstChar = ((a & 0x3F) << 2) | ((b >> 4) & 0x03);   //6 bits for 'a', 2 from 'b'
    var secondChar = ((b & 0x0F) << 4) | ((c >> 2) & 0x0F);  //remaining 4 bits from 'b', 4 from 'c'
    var thirdChar = ((c & 0x03) << 6) | (d & 0x3F);          //remaining 2 bits from 'c', 6 bits for 'd'

    //add _firstChar so that all values map to a printable character
    outArray.push(String.fromCharCode(firstChar + _firstChar));
    outArray.push(String.fromCharCode(secondChar + _firstChar));
    outArray.push(String.fromCharCode(thirdChar + _firstChar));
};

这是一个简单的例子:http://jsfiddle.net/NWyBx/1

请注意，通过对生成的字符串应用 gzip 压缩可能会进一步减少存储大小。

或者，如果您的数字顺序不重要，那么您可以简单地使用 51 个桶进行桶排序(假设 0-50 包括 0 和 50 作为有效数字)并存储每个桶的计数而不是数字本身。与任何其他方法相比，这可能会给您带来更好的压缩和效率。