# Finding patterns in a growing collection

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);

}

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);
}

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++)
{
}
}
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++)
{
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)

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

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
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
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.

## migrated from stackoverflow.comJun 25 '12 at 17:56

This question came from our site for professional and enthusiast programmers.

• I think the relevant code here is only a few lines. But because of all the WriteLining I'm not sure. – Henk Holterman Jun 25 '12 at 17:38
• @HenkHolterman, don't look at the printResult. it's just to see the end result – Fredou Jun 25 '12 at 17:42
• Instead of generating data and then matching it against the pattern, why not generate data that matches by construction? – Ben Voigt Jun 25 '12 at 17:42
• Can you talk through a bit what this code is tryign to do, especially the bit you want optimised. The code is quite complex and the only thing that makes sense of what you are doing is counting the bits... Unfortunately your code has some confusingly named variables (eg maxBits isn't the maximum number of bits as I would have expected but seems to be the maximum value without any bits set higher than maxbits). Cleaning up some of that might make everybody's life easier. – Chris Jun 25 '12 at 18:15
• @Fredou: what is the purpose of your app? Are you facing a problem that requires counting items, searching/retrieving from a collection or is it mostly compression/encoding? Have you considered standard algorithms and data structures suitable for that kind of work? For example, hash|dictionaries|associative arrays, or tree-like data structures? For dictionary-based encoding, study classic algorithms (e.g. Lempel-Ziv, etc). Cheers! – user14433 Jun 26 '12 at 3:04

I found the perfect way! It was right in front of me; I just had to look at the data itself.

Private Sub initBits(ByVal maxBit As Integer)

maxBits = ((1 << maxBit)) - 1
ReDim CountBit(maxBits)
ReDim MapBit(maxBits)

For i = 1 To maxBits
CountBit(i) = getBitCount(i)
Next

Dim StopBit = (maxBits >> 1)
Dim StartBit = maxBits
Dim count As Integer = 0

For i = StartBit To StopBit + 1 Step -2
count += CountBit(i)
Next

ReDim CalculatedBit(count)
count = 1
For i = StartBit To StopBit + 1 Step -2
MapBit(i) = count
For j = 0 To CountBit(i) - 1
CalculatedBit(count) = getBitValue(i, j)
count += 1
Next
Next

Do
count = StartBit
StartBit = StopBit
StopBit = StopBit >> 1
For i = StartBit To StopBit + 1 Step -2
MapBit(i) = MapBit(count)
count -= 2
Next
Loop Until StopBit = 0

For i = 3 To maxBits Step 2
MapBit(i - 1) = MapBit(i) + 1
Next
End Sub


Data:

Number : MapBit : CountBit : Value
0 :      0 :        0 : 0
1 :      1 :        1 : 1
2 :      2 :        1 : 2
3 :      1 :        2 : 1 2
4 :      6 :        1 : 4
5 :      5 :        2 : 1 4
6 :      2 :        2 : 2 4
7 :      1 :        3 : 1 2 4
8 :     12 :        1 : 8
9 :     11 :        2 : 1 8
10 :      9 :        2 : 2 8
11 :      8 :        3 : 1 2 8
12 :      6 :        2 : 4 8
13 :      5 :        3 : 1 4 8
14 :      2 :        3 : 2 4 8
15 :      1 :        4 : 1 2 4 8


The dictionary I made of the odd numbers of the second half in this example: 15, 13, 11 and 9.

The rest is just the same pattern; look at 7, 5, 3 and 1. This mapbit(num) reference are the same as 15, 13, 15 and 15. I do not need to loop through the dictionary like i was doing before; it's a simple logic.

Then the even numbers, which is always mapbit(evennumber) = mapbit(evennumber+1) +1. No need to find the pattern again.

• The question looks intriguing; I wish I understood what it is about though. I suspect that you need a lot less code than you have. Also, storing things in a dictionary rather than an array cannot possibly be faster. – Leonid Aug 16 '12 at 20:12