13

*这里的“高效”基本上是指较小的尺寸（以减少 IO 等待时间）和快速的检索/反序列化时间。存储时间并不那么重要。

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

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

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

  • 对数字进行零填充，因此每个数字长 2 个字符，例如：

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

  • 以 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 建议对数据使用压缩。将此 LZW 实现与基数 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
4

3 回答 3

4

如果您的范围是 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 作为有效数字）并存储每个存储桶的计数而不是数字本身. 与任何其他方法相比，这可能会为您提供更好的压缩和效率。

于 2012-04-12T01:01:22.837 回答
0

假设（如在您的测试中）压缩所花费的时间比减小大小为您节省的时间更多，那么您的 char 编码是您在没有位移的情况下获得的最小编码。您当前为每个数字使用一个字节，但如果保证它们足够小，您可以在每个字节中放置两个数字。这可能是过度优化，除非这是您的代码中非常热门的一段。

于 2012-04-12T00:32:07.423 回答
0

您可能要考虑使用Uint8Arrayor ArrayBuffer。这篇博文展示了它是如何完成的。复制他的逻辑，这里有一个例子，假设你有一个现有的Uint8Array名为arr.

function arrayBufferToBinaryString(buffer, cb) {
    var blobBuilder = new BlobBuilder();
    blobBuilder.append(buffer);
    var blob = blobBuilder.getBlob();
    var reader = new FileReader();
    reader.onload = function (e) {
        cb(reader.result);
    };
    reader.readAsBinaryString(blob);
}
arrayBufferToBinaryString(arr.buffer, function(s) { 
  // do something with s
});
于 2012-04-12T00:52:49.103 回答