3

我有一个简单的任务：确定将某个数字（字节数组长度）编码为字节数组并编码最终值（实现本文：编码长度和值字节）需要多少字节。

最初我写了一个完成任务的快速方法：

public static Byte[] Encode(Byte[] rawData, Byte enclosingtag) {
    if (rawData == null) {
        return new Byte[] { enclosingtag, 0 };
    }
    List<Byte> computedRawData = new List<Byte> { enclosingtag };
    // if array size is less than 128, encode length directly. No questions here
    if (rawData.Length < 128) {
        computedRawData.Add((Byte)rawData.Length);
    } else {
        // convert array size to a hex string
        String hexLength = rawData.Length.ToString("x2");
        // if hex string has odd length, align it to even by prepending hex string
        // with '0' character
        if (hexLength.Length % 2 == 1) { hexLength = "0" + hexLength; }
        // take a pair of hex characters and convert each octet to a byte
        Byte[] lengthBytes = Enumerable.Range(0, hexLength.Length)
                .Where(x => x % 2 == 0)
                .Select(x => Convert.ToByte(hexLength.Substring(x, 2), 16))
                .ToArray();
        // insert padding byte, set bit 7 to 1 and add byte count required
        // to encode length bytes
        Byte paddingByte = (Byte)(128 + lengthBytes.Length);
        computedRawData.Add(paddingByte);
        computedRawData.AddRange(lengthBytes);
    }
    computedRawData.AddRange(rawData);
    return computedRawData.ToArray();
}

这是一个旧代码，并且以一种糟糕的方式编写。

现在我正在尝试使用按位运算符或BitConverter类来优化代码。以下是按位编辑的示例：

public static Byte[] Encode2(Byte[] rawData, Byte enclosingtag) {
    if (rawData == null) {
        return new Byte[] { enclosingtag, 0 };
    }
    List<Byte> computedRawData = new List<Byte>(rawData);
    if (rawData.Length < 128) {
        computedRawData.Insert(0, (Byte)rawData.Length);
    } else {
        // temp number
        Int32 num = rawData.Length;
        // track byte count, this will be necessary further
        Int32 counter = 1;
        // simply make bitwise AND to extract byte value
        // and shift right while remaining value is still more than 255
        // (there are more than 8 bits)
        while (num >= 256) {
            counter++;
            computedRawData.Insert(0, (Byte)(num & 255));
            num = num >> 8;
        }
        // compose final array
        computedRawData.InsertRange(0, new[] { (Byte)(128 + counter), (Byte)num });
    }
    computedRawData.Insert(0, enclosingtag);
    return computedRawData.ToArray();
}

和BitConverter类的最终实现：

public static Byte[] Encode3(Byte[] rawData, Byte enclosingtag) {
    if (rawData == null) {
        return new Byte[] { enclosingtag, 0 };
    }
    List<Byte> computedRawData = new List<Byte>(rawData);
    if (rawData.Length < 128) {
        computedRawData.Insert(0, (Byte)rawData.Length);
    } else {
        // convert integer to a byte array
        Byte[] bytes = BitConverter.GetBytes(rawData.Length);
        // start from the end of a byte array to skip unnecessary zero bytes
        for (int i = bytes.Length - 1; i >= 0; i--) {
            // once the byte value is non-zero, take everything starting
            // from the current position up to array start.
            if (bytes[i] > 0) {
                // we need to reverse the array to get the proper byte order
                computedRawData.InsertRange(0, bytes.Take(i + 1).Reverse());
                // compose final array
                computedRawData.Insert(0, (Byte)(128 + i + 1));
                computedRawData.Insert(0, enclosingtag);
                return computedRawData.ToArray();
            }
        }
    }
    return null;
}

所有方法都按预期工作。我使用了Stopwatch 类页面中的示例来衡量性能。性能测试让我感到惊讶。我的测试方法执行了 1000 次运行该方法来编码具有 100 000 个元素的字节数组（实际上，只有数组 Sixe），平均时间是：

  • 编码——大约 200 毫秒
  • 编码 2——大约 270 毫秒
  • 编码 3 -- 大约 320 毫秒

我个人喜欢 method Encode2，因为代码看起来更具可读性，但它的性能并不是那么好。

问题：您会建议什么来提高Encode2方法性能或提高Encode可读性？

任何帮助将不胜感激。

============================

更新：感谢所有参与此主题的人。我考虑了所有建议并最终得到了这个解决方案：

public static Byte[] Encode6(Byte[] rawData, Byte enclosingtag) {
    if (rawData == null) {
        return new Byte[] { enclosingtag, 0 };
    }
    Byte[] retValue;
    if (rawData.Length < 128) {
        retValue = new Byte[rawData.Length + 2];
        retValue[0] = enclosingtag;
        retValue[1] = (Byte)rawData.Length;
    } else {
        Byte[] lenBytes = new Byte[3];
        Int32 num = rawData.Length;
        Int32 counter = 0;
        while (num >= 256) {
            lenBytes[counter] = (Byte)(num & 255);
            num >>= 8;
            counter++;
        }
        // 3 is: len byte and enclosing tag
        retValue = new byte[rawData.Length + 3 + counter];
        rawData.CopyTo(retValue, 3 + counter);
        retValue[0] = enclosingtag;
        retValue[1] = (Byte)(129 + counter);
        retValue[2] = (Byte)num;
        Int32 n = 3;
        for (Int32 i = counter - 1; i >= 0; i--) {
            retValue[n] = lenBytes[i];
            n++;
        }
    }
    return retValue;
}

最终，我从列表转移到了固定大小的字节数组。现在，针对同一数据集的平均时间约为 65 毫秒。似乎列表（不是按位运算）给我的性能带来了重大损失。

4

2 回答 2

2

这里的主要问题几乎可以肯定是列表的分配，以及插入新元素以及列表最终转换为数组时所需的分配。这段代码可能大部分时间都花在垃圾收集器和内存分配器上。相比之下，使用与不使用按位运算符可能意义不大，我会研究减少您首先分配的内存量的方法。

一种方法是发送对预先分配的字节数组的引用和指向您在数组中的位置的索引，而不是分配和返回数据，然后返回一个整数，告诉您写入了多少字节。处理大型数组通常比处理许多小对象更有效。正如其他人所提到的，使用分析器，并查看您的代码将时间花在哪里。

当然，我提到的优化将使您的代码在本质上更底层，并且更接近您通常在 C 中所做的，但通常在可读性和性能之间进行权衡。

于 2015-03-01T11:15:13.910 回答
2

使用“反向、追加、反向”而不是“在前面插入”，并预先分配所有内容，它可能是这样的：（未测试）

public static byte[] Encode4(byte[] rawData, byte enclosingtag) {
    if (rawData == null) {
        return new byte[] { enclosingtag, 0 };
    }
    List<byte> computedRawData = new List<byte>(rawData.Length + 6);
    computedRawData.AddRange(rawData);
    if (rawData.Length < 128) {
        computedRawData.InsertRange(0, new byte[] { enclosingtag, (byte)rawData.Length });
    } else {
        computedRawData.Reverse();
        // temp number
        int num = rawData.Length;
        // track byte count, this will be necessary further
        int counter = 1;
        // simply cast to byte to extract byte value
        // and shift right while remaining value is still more than 255
        // (there are more than 8 bits)
        while (num >= 256) {
            counter++;
            computedRawData.Add((byte)num);
            num >>= 8;
        }
        // compose final array
        computedRawData.Add((byte)num);
        computedRawData.Add((byte)(counter + 128));
        computedRawData.Add(enclosingtag);
        computedRawData.Reverse();
    }
    return computedRawData.ToArray();
}

我不确定它是否会更快，但这是有道理的 - 现在主要避免了昂贵的“在前面插入”操作，除非只有其中一个（可能不足以平衡两个反向）。

另一种想法是以另一种方式将在前面的插入限制为仅一次：收集所有必须插入那里的东西，然后执行一次。可能看起来像这样：（未测试）

public static byte[] Encode5(byte[] rawData, byte enclosingtag) {
    if (rawData == null) {
        return new byte[] { enclosingtag, 0 };
    }
    List<byte> computedRawData = new List<byte>(rawData);
    if (rawData.Length < 128) {
        computedRawData.InsertRange(0, new byte[] { enclosingtag, (byte)rawData.Length });
    } else {
        // list of all things that will be inserted
        List<byte> front = new List<byte>(8);
        // temp number
        int num = rawData.Length;
        // track byte count, this will be necessary further
        int counter = 1;
        // simply cast to byte to extract byte value
        // and shift right while remaining value is still more than 255
        // (there are more than 8 bits)
        while (num >= 256) {
            counter++;
            front.Insert(0, (byte)num);  // inserting in tiny list, not so bad
            num >>= 8;
        }
        // compose final array
        front.InsertRange(0, new[] { (byte)(128 + counter), (byte)num });
        front.Insert(0, enclosingtag);
        computedRawData.InsertRange(0, front);
    }
    return computedRawData.ToArray();
}

如果它不够好或没有帮助（或者如果这更糟 - 嘿，可能是），我会尝试提出更多想法。

于 2015-03-01T11:22:48.063 回答