If you look at the condition of If calculated Then in the code below, this is what slowing down the code. While the code provided seem fast with Const initBit = 4 try it with something over 12. I want to be able to use this code (with calculated param as true) with initBit of 20 or more.
Beware that 20 or more might require a gig or more of RAM and/or compiled as x64.
C# code (converted with an online tool from VB.NET):
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Text;
static class Module1
{
public static void Main()
{
Console.WindowHeight = 59;
int initBit = 4;
var sw = Stopwatch.StartNew();
initBits(initBit, false);
sw.Stop();
printResult(sw, false);
sw = Stopwatch.StartNew();
initBits(initBit, true);
sw.Stop();
printResult(sw, true);
Console.Read();
}
private static int maxBits;
private static int[] CountBit;
private static int[] CalculatedBit;
private static int[] MapBit;
private static void initBits(int maxBit, bool calculated)
{
int[] calc = null;
bool calcOk = false;
int calcOkPos = 0;
List<int> calcResult = new List<int>();
int findPos = 0;
maxBits = ((1 << maxBit)) - 1;
calc = new int[maxBits + 1];
CountBit = new int[maxBits + 1];
MapBit = new int[maxBits + 1];
for (var i = 0; i <= maxBits; i++)
{
CountBit[i] = getBitCount(i);
}
calcResult.Add(0);
for (var i = maxBits; i >= 1; i += -1)
{
for (var j = 0; j <= CountBit[i] - 1; j++)
{
calc[j] = getBitValue(i, j);
}
calcOk = false;
if (calculated)
{
findPos = calcResult.IndexOf(calc[0], 0);
while (findPos != -1)
{
calcOk = true;
for (var k = 0; k <= CountBit[i] - 1; k++)
{
calcOk = calcOk && calcResult[findPos + k] == calc[k];
if (!calcOk)
break; // TODO: might not be correct. Was : Exit For
}
if (calcOk)
{
calcOkPos = findPos;
break; // TODO: might not be correct. Was : Exit While
}
findPos = calcResult.IndexOf(calc[0], findPos + 1);
}
}
if (!calcOk)
{
MapBit[i] = calcResult.Count;
for (var j = 0; j <= CountBit[i] - 1; j++)
{
calcResult.Add(calc[j]);
}
}
else
{
MapBit[i] = calcOkPos;
}
}
CalculatedBit = calcResult.ToArray();
calcResult.Clear();
}
private static int getBitCount(int bits)
{
bits = bits - ((bits >> 1) & 0x55555555);
bits = (bits & 0x33333333) + ((bits >> 2) & 0x33333333);
return ((bits + (bits >> 4) & 0xf0f0f0f) * 0x1010101) >> 24;
}
private static int getBitValue(int bits, int pos)
{
for (var k = 0; k <= pos - 1; k++)
{
bits = bits & bits - 1;
}
return bits ^ bits & (bits - 1);
}
private static void printResult(Stopwatch sw, bool calculated)
{
StringBuilder sb = new StringBuilder();
sb.AppendLine(" Calculated : " + calculated.ToString() + Environment.NewLine + " maxBits : " + maxBits.ToString() + " (" + getBitCount(maxBits) + ")" + Environment.NewLine + " CalculatedBit.Length : " + CalculatedBit.Length.ToString());
//if initBit is 6 or less
if (CalculatedBit.Length <= 65)
{
sb.AppendLine(Environment.NewLine + " Started with" + Environment.NewLine + " Number : Value");
for (var i = 0; i <= maxBits; i++)
{
sb.Append(i.ToString().PadLeft(10) + " : ");
for (var j = 0; j <= (CountBit[i] == 0 ? 1 : CountBit[i] - 1); j++)
{
sb.Append(getBitValue(i, j).ToString() + " ");
}
sb.AppendLine("");
}
sb.AppendLine(Environment.NewLine + " Index : Value");
for (var i = 0; i <= CalculatedBit.GetUpperBound(0); i++)
{
sb.AppendLine(i.ToString().PadLeft(9) + " : " + CalculatedBit[i].ToString());
}
sb.AppendLine(Environment.NewLine + " Number : MapBit : CountBit : Value");
for (var i = 0; i <= maxBits; i++)
{
sb.Append(i.ToString().PadLeft(10) + " : " + MapBit[i].ToString().PadLeft(6) + " : " + CountBit[i].ToString().PadLeft(8) + " : ");
for (var k = 0; k <= (CountBit[i] == 0 ? 1 : CountBit[i] - 1); k++)
{
sb.Append(CalculatedBit[MapBit[i] + k].ToString() + " ");
}
sb.AppendLine("");
}
}
sb.AppendLine(Environment.NewLine + " Took: " + sw.ElapsedMilliseconds + "ms" + Environment.NewLine);
Console.Write(sb.ToString());
Debug.Write(sb.ToString());
}
}
Make sure, if you do create a VB.NET project, to "check" the setting "Remove integer overflow checks" in "Advanced Compiler Settings" in the "Compile" tab in the project "Properties" to let the magic of getBitCount function work.
VB.NET code:
Imports System.Text
Module Module1
Sub Main()
Console.WindowHeight = 59
Const initBit = 4
Dim sw = Stopwatch.StartNew
initBits(initBit, False)
sw.Stop()
printResult(sw, False)
sw = Stopwatch.StartNew
initBits(initBit, True)
sw.Stop()
printResult(sw, True)
Console.Read()
End Sub
Private maxBits As Integer
Private CountBit() As Integer
Private CalculatedBit() As Integer
Private MapBit() As Integer
Private Sub initBits(ByVal maxBit As Integer, ByVal calculated As Boolean)
Dim calc() As Integer
Dim calcOk As Boolean
Dim calcOkPos As Integer
Dim calcResult As New List(Of Integer)
Dim findPos As Integer
maxBits = ((1 << maxBit)) - 1
ReDim calc(maxBits)
ReDim CountBit(maxBits)
ReDim MapBit(maxBits)
For i = 0 To maxBits
CountBit(i) = getBitCount(i)
Next
calcResult.Add(0)
For i = maxBits To 1 Step -1
For j = 0 To CountBit(i) - 1
calc(j) = getBitValue(i, j)
Next
calcOk = False
If calculated Then
findPos = calcResult.IndexOf(calc(0), 0)
While findPos <> -1
calcOk = True
For k = 0 To CountBit(i) - 1
calcOk = calcOk AndAlso calcResult(findPos + k) = calc(k)
If Not calcOk Then Exit For
Next
If calcOk Then
calcOkPos = findPos
Exit While
End If
findPos = calcResult.IndexOf(calc(0), findPos + 1)
End While
End If
If Not calcOk Then
MapBit(i) = calcResult.Count
For j = 0 To CountBit(i) - 1
calcResult.Add(calc(j))
Next
Else
MapBit(i) = calcOkPos
End If
Next
CalculatedBit = calcResult.ToArray
calcResult.Clear()
End Sub
Private Function getBitCount(bits As Integer) As Integer
bits = bits - ((bits >> 1) And &H55555555)
bits = (bits And &H33333333) + ((bits >> 2) And &H33333333)
Return ((bits + (bits >> 4) And &HF0F0F0F) * &H1010101) >> 24
End Function
Private Function getBitValue(bits As Integer, pos As Integer) As Integer
For k = 0 To pos - 1
bits = bits And bits - 1
Next
Return bits Xor bits And (bits - 1)
End Function
Private Sub printResult(ByVal sw As Stopwatch, ByVal calculated As Boolean)
Dim sb As New StringBuilder
sb.AppendLine(" Calculated : " & calculated.ToString & Environment.NewLine & " maxBits : " & maxBits.ToString & " (" & getBitCount(maxBits) & ")" & Environment.NewLine & " CalculatedBit.Length : " & CalculatedBit.Length.ToString)
If CalculatedBit.Length <= 65 Then 'if initBit is 6 or less
sb.AppendLine(Environment.NewLine & " Started with" & Environment.NewLine & " Number : Value")
For i = 0 To maxBits
sb.Append(i.ToString.PadLeft(10) & " : ")
For j = 0 To If(CountBit(i) = 0, 1, CountBit(i)) - 1
sb.Append(getBitValue(i, j).ToString & " ")
Next
sb.AppendLine("")
Next
sb.AppendLine(Environment.NewLine & " Index : Value")
For i = 0 To CalculatedBit.GetUpperBound(0)
sb.AppendLine(i.ToString.PadLeft(9) & " : " & CalculatedBit(i).ToString)
Next
sb.AppendLine(Environment.NewLine & " Number : MapBit : CountBit : Value")
For i = 0 To maxBits
sb.Append(i.ToString.PadLeft(10) & " : " & MapBit(i).ToString.PadLeft(6) & " : " & CountBit(i).ToString.PadLeft(8) & " : ")
For k = 0 To If(CountBit(i) = 0, 1, CountBit(i)) - 1
sb.Append(CalculatedBit(MapBit(i) + k).ToString & " ")
Next
sb.AppendLine("")
Next
End If
sb.AppendLine(Environment.NewLine & " Took: " & sw.ElapsedMilliseconds & "ms" & Environment.NewLine)
Console.Write(sb.ToString)
Debug.Write(sb.ToString)
End Sub
End Module
Result:
Calculated : False maxBits : 15 (4) CalculatedBit.Length : 33 Started with Number : Value 0 : 0 1 : 1 2 : 2 3 : 1 2 4 : 4 5 : 1 4 6 : 2 4 7 : 1 2 4 8 : 8 9 : 1 8 10 : 2 8 11 : 1 2 8 12 : 4 8 13 : 1 4 8 14 : 2 4 8 15 : 1 2 4 8 Index : Value 0 : 0 1 : 1 2 : 2 3 : 4 4 : 8 5 : 2 6 : 4 7 : 8 8 : 1 9 : 4 10 : 8 11 : 4 12 : 8 13 : 1 14 : 2 15 : 8 16 : 2 17 : 8 18 : 1 19 : 8 20 : 8 21 : 1 22 : 2 23 : 4 24 : 2 25 : 4 26 : 1 27 : 4 28 : 4 29 : 1 30 : 2 31 : 2 32 : 1 Number : MapBit : CountBit : Value 0 : 0 : 0 : 0 1 : 32 : 1 : 1 2 : 31 : 1 : 2 3 : 29 : 2 : 1 2 4 : 28 : 1 : 4 5 : 26 : 2 : 1 4 6 : 24 : 2 : 2 4 7 : 21 : 3 : 1 2 4 8 : 20 : 1 : 8 9 : 18 : 2 : 1 8 10 : 16 : 2 : 2 8 11 : 13 : 3 : 1 2 8 12 : 11 : 2 : 4 8 13 : 8 : 3 : 1 4 8 14 : 5 : 3 : 2 4 8 15 : 1 : 4 : 1 2 4 8 Took: 1ms Calculated : True maxBits : 15 (4) CalculatedBit.Length : 13 Started with Number : Value 0 : 0 1 : 1 2 : 2 3 : 1 2 4 : 4 5 : 1 4 6 : 2 4 7 : 1 2 4 8 : 8 9 : 1 8 10 : 2 8 11 : 1 2 8 12 : 4 8 13 : 1 4 8 14 : 2 4 8 15 : 1 2 4 8 Index : Value 0 : 0 1 : 1 2 : 2 3 : 4 4 : 8 5 : 1 6 : 4 7 : 8 8 : 1 9 : 2 10 : 8 11 : 1 12 : 8 Number : MapBit : CountBit : Value 0 : 0 : 0 : 0 1 : 1 : 1 : 1 2 : 2 : 1 : 2 3 : 1 : 2 : 1 2 4 : 3 : 1 : 4 5 : 5 : 2 : 1 4 6 : 2 : 2 : 2 4 7 : 1 : 3 : 1 2 4 8 : 4 : 1 : 8 9 : 11 : 2 : 1 8 10 : 9 : 2 : 2 8 11 : 8 : 3 : 1 2 8 12 : 3 : 2 : 4 8 13 : 5 : 3 : 1 4 8 14 : 2 : 3 : 2 4 8 15 : 1 : 4 : 1 2 4 8 Took: 0ms
That code is a kind of a compressed cached dictionary (calculatedBit) that can rebuild a number from 2 information, the position (mapBit) and the number of bits (countBit).
I will use the result (with Calculated : True) provided to explain it.
I passed the value 4 to the method so I'm asking "create the dictionary for number 0 to 15" because 15 = 1111. I start at 15 and loop until 1 (0 is hard-coded to be at position 0 of the calculatedBit). For each number, I'm getting the number of bits that are 1 (and not 0) and I'm getting the value of each bits.
Let say I'm at number 6, (0110), I set countbit(6) = 2 and this array of int 2, 4. I'm looping through the dictionary to find that specific pattern: 2, 4. Since 15 is already cached (1111, countbit 4, and this list 1, 2, 4, 8) and the lookup is telling me that 2, 4 is found at position 2, I set mapbit(6) = 2.
With all that cached information, I can simply rebuild the number without having to call the function getBitValue and getBitCount which are more expensive than a reference in an array.
If I want to rebuild the number 6, I can simply say; get me the position, mapbit(6), and the number of bit to sum, countbit(6) and I can simply do a LINQ call or a loop from 2 to 3 in the arrat calculatedBit and I have my number 6.
In my program, I have a huge loop that want a random bit, that is 1, from a number. I only have to do calculatedbit(mapbit(num) + random.next(0,countbit(num))) to get that random bit. By precalculating everything, I'm gaining 50 to 75% in speed since I don't have to call the getBitValue and getBitCount function millions of time. Which means I don't have to do getBitValue(num, random.next(0,getBitCount(num))).
My problem is that caching above 14 bits (1111111111111) is VERY slow and without the lookup, it can get pretty big. 25 bits can take 2.5 gigs of RAM.
