Improving encoding cycle

I have this object: Dictionary<byte, BitArray>()

It's filled with values from a huffman tree. To encode each byte of the stream to the huffman binary value I do:

// Bytes are the bytes to be encoded, encoded is the output string
foreach (byte c in Bytes)
{
    encoded += _translationTable[c].ToBitsString();
}

This is the extension method:

//Converts the bitarray in a binary string
public static string ToBitsString(this BitArray bitArr)
{
    string retStr = string.Empty;

    foreach (bool bit in bitArr)
    {
        retStr += (bit) ? "1" : "0";
    }

    return retStr;
}

It takes nearly 3 seconds to encode 64kb of data, is there a way to achieve this result in a faster way?

Jon Skeet
people
quotationmark

It sounds like you're performing string concatenation in a loop. That's a very inefficient way of building a new string. I suspect you want:

var builder = new StringBuilder();
foreach (byte c in Bytes)
{
    builder.Append(_translationTable[c].ToBitsString());
}
var encoded = builder.ToString();

Now that we can see what ToBitsString does, it's easy to rewrite it to accept a StringBuilder to append to:

public static void AppendBitsTo(this BitArray bitArray, StringBuilder builder)
{
    foreach (bool bit in bitArray)
    {
        builder.Append(bit ? "1" : "0");
    }
}

Then the body of the loop would be:

_translationTable[c].AppendBitsTo(builder);

people

See more on this question at Stackoverflow