is it possible to optimize that code?

Question

I'm interested in speed, not good looking code, that is why I'm using array and not list(of integer).

I have an array looking like: 0,1,0,1,1,0,1,0,1,1,1,0,0,1

I'm interesting in the position of each number so I can later pick one randomly.

so what I do is looping through the array to take position number of each 1 then creating a new array looking like this: 2,4,5,7,9,10,11,14

is bitwise could be used here? I have no idea

code look like:

Private Function theThing() As Integer()
    Dim x As Integer
    'arIn() would be a parameter
    Dim arIn() As Integer = {0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1}
    Dim ar() As Integer = Nothing
    Dim arCount As Integer = -1

    For x = 1 To arIn.GetUpperBound(0)
        If arIn(x) = 1 Then
            arCount += 1
        End If
    Next

    If arCount > -1 Then
        'using redim preseve is slower than the loop above
        ReDim ar(arCount)

        arCount = 0
        For x = 1 To arIn.GetUpperBound(0)
            If arIn(x) = 1 Then
                ar(arCount) = x
                arCount += 1
            End If
        Next
    End If

    Return ar
End Function

* EDIT *

current solution(10% to 15% faster) is now

Private Function theThing() As Integer
    Dim ar() As Integer = {0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1}
    Dim arLenght As Integer = ar.GetUpperBound(0)
    Dim arCount As Integer = 0
    Dim x As Integer

    For x = 1 To arLenght
        If ar(x) = 1 Then
            ar(arCount) = x
            arCount += 1
        End If
    Next

    dim r As New Random()

    Return ar(r.Next(arCount))
End Function

I don't think it can be optimized more than that, unless someone find a way to do exactly what the solution does but way faster

Before this question, my whole thing was able to do about 25500 run each 10 seconds.

Now, it can do over 32250 all the time, a 21% increase, thanks!

Answer 1

Speed for how many items?

Changing items?

Compile time or execution time?

With what space constraints?

A known strategy is to take a few ones together and write out all combinations and their results: 0000 -> 0001 -> 4 0010 -> 3 0011 -> 3,4 0100 -> 2 0101 -> 2,4 0110 -> 2,3 ...

Why do you want to convert from this binary representation to select a random one bit? That is unlikely to help with performance. Better group them by 8 bits, use a table telling you how many 1s are in the group, and repeat 5 times. then you know how many ones there are. do a random over that and then look up the selected one.

Answer 2

Instead of storing an array of integers, why not put them all into one integer?

oldArray = [0, 1, 1, 0, 1]
newValue =  22     (binary 10110)

If you want to check if a particular bit position is set, do a bitwise comparison with two to the power of that position:

is position 2 set?
value:    10110
4 (2^2):  00100
result:   00100 --> true

is position 0 set?
value:    10110
1 (2^0):  00001
result:   00000 --> false

Do a search for bitwise comparison and you should find a lot of help.

Here are some good Stack Overflow questions which might help:
http://stackoverflow.com/questions/276706/what-are-bitwise-operators
http://stackoverflow.com/questions/47981/how-do-you-set-clear-and-toggle-a-single-bit-in-c

Answer 3

You might find that using For Each and a list initialized to at least the length of the input array is faster than an indexer:

If arIn.Length > 0 Then
  Dim lstOut As New List(Of Integer)(arIn.Length)
  Dim ix As Integer = 0
  For Each val As Integer In arIn
    If val = 1 Then
      lstOut.Add(ix)
    End If
    ix = ix + 1
  End If
  Return lstOut.ToArray()
Else
  Return Nothing
End If

But you'd have to test it.

Answer 4

This is what BitArray was made for.

Answer 5

Few tips on the original algorithm:

1. Try storing the results of arIn.GetUpperBound(0) in a variable. I don't know how VB makes it's loops, but there is a chance that the function gets called once every iteration. You should check that though.
2. That If arCount > -1 is always going to be true. Remove it.

If you wish to keep the same inputs/outputs, then I don't think there is much else that can be improved.

Now if you wanted a function that does the random selection too, then it might be a bit better. I'll write in C# since I know it better. You should be able to understand:

public static int GetRandomSetBit(int[] AllBits)
{
    // Perhaps check here if AllBits is null/empty. I'll skip that for now.

    int L = AllBits.Length;
    int SetBitCount = 0;

    // No point to save a few bytes here. Also - you can make a global array
    // large enough for all occasions and skip allocating it every time.
    // In that case consider automatic resizing and watch out for
    // multithreading issues (if you use several threads).
    int[] GoodPositions = new int[L];

    for ( int i = 0; i < L; i++ )
        if ( AllBits[i] != 0 )
        {
            GoodPositions[SetBitCount] = i;
            SetBitCount++;
        }
     Random r = new Random(); // Should use one global instance
     return GoodPositions[r.Next(SetBitCount)];
}

I'm afraid it won't get any better than that. Not unless you can somehow change the inputs/outputs or requirements.

Answer 6

I find it hard to believe that a redim preserve would be slower than your loop unless it were itself inside the loop.

In which case, for raw speed, don't count the number of 1's in arIn just to set the size of ar. Since ar can never be bigger than arIn, just set it to the same size and redim-preserve at the end (won't be slower since it's outside the loop and will always be trimming, not expanding - VB hopefully can do this in-place rather than allocating more memory). In addition, cache size of arIn in case VB calculates it each time through the loop (likely if ReDim's are allowed).

Private Function theThing() As Integer()
    Dim x As Integer
    'arIn() would be a parameter
    Dim arIn() As Integer = {0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1}
    Dim ar(arIn.GetUpperBound(0)) As Integer
    Dim arCount As Integer
    Dim arInCount As Integer

    arCount = 0
    arInCount = arIn.GetUpperBound(0)
    For x = 1 To arInCount
        If arIn(x) = 1 Then
            ar(arCount) = x
            arCount += 1
        End If
    Next

    ReDim Preserve ar(arCount)
    Return ar
End Function

Alternatively, you could remove the redim altogether if you tweak slightly what's returned. Make the return array one bigger than the input array and use the first element to control which parts of the array you'll select randomly.

For your sample, the returned array would be:

{8,2,4,5,7,9,10,11,14,?,?,?,?,?,?} (? values are irrelevant).
 ^ <-------+--------> <----+---->
 |         |               |
 |         |               +-- These are unused.
 |         |
 |         +-- These are used.
 |
 +-- This is the count of elements to use.

That code would be:

Private Function theThing() As Integer()
    Dim x As Integer
    'arIn() would be a parameter
    Dim arIn() As Integer = {0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1}
    Dim ar(arIn.GetUpperBound(0)+1) As Integer
    Dim arCount As Integer
    Dim arInCount As Integer

    arCount = 0
    arInCount = arIn.GetUpperBound(0)
    For x = 1 To arInCount
        If arIn(x) = 1 Then
            ar(arCount) = x
            arCount += 1
        End If
    Next

    ar(0) = arCount
    Return ar
End Function

Then, in your code which selects a random value from ar, instead of:

rndval = rnd(ar.GetUpperBound)

use:

rndval = rnd(ar(0) + 1)

Answer 7

Maybe you can squeeze the maximum performance by using a conversion table. And then apply the algorithm below:

Sorry I'm not fluent on VB anymore, so I'll have to write C#. Here's a piece of the whole code, as the entire lookupTable would have 256 items.

using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        var input = new byte[] { 0x5A /*01011010b*/, 0xE4 /*11100100b*/ };
        var output = new List<int>();
        var lookupTable = new int[][] { new int[0] /*00000000b*/
                                           , new int[] { 8 }    /*00000001b*/
                                           , new int[] { 7 }    /*00000010b*/
                                           , new int[] { 7,8 }  /*00000011b*/
                                           , new int[] { 6 }    /*00000100b*/
                                           , new int[] { 6,8 }  /*00000101b*/
                                           , new int[] { 6,7,8 }  /*00000111b*/
                                          };
        int offset = 0;
        foreach (var value in input)
        {
            foreach (var position in lookupTable[(int)value])
            {
                output.Add(position + offset);
            }
            offset += 8;
        }
    }
}

Answer 8

Disable Overflow Checking.
Project Properties -> Compile -> Advanced Compile Options -> Remove Integer Overflow Checks.
If you need overflow checking for the rest of the project you may move the code to a new project (for example a DLL) and disable overflow checking for that new project.

Also make sure that you are running a release build(optimizations enabled) and you are not debugging it.

EDIT: I get 8.5s (12s if I declare the array inside the For I'm using for testing) for calling the function 50 millons times. If you are getting only 32000 either you are using very large inputs or something is slowing down your code. For example if you are counting the time inside the program and you are running it in a profiler you will get wrong results as profiling can slowdown the program dramatically. Also glitches like this http://stackoverflow.com/questions/383735/slow-methods-calls may affect performance.

Answer 9

If it's easy to generate a prime number slightly larger than the length of your array (depending on the size of it, this may or may not be easy), and you don't care about completely uniformly random, then you can generate a random number in that range and generate that cycle. It should find an answer within a few iterations (based on the density of 1s). Source code in c# since I don't remember vb syntax:

int RandomInArray(int[] ar)
{
    int p = GenerateSlightlyLargerPrime(ar.Length);

    int x = random.nextInt(p);
    int i = x;
    do
    {
       if (i < ar.Length && ar[i] == 1)
           return i;
       i = (i + x) % p;
    } while (i != x);
    return -1;
}

Note that this isn't 100% uniformly random, but it should be fairly close.

Answer 10

I think that when Recursive cited BitArray, he meant something like this:

using System.Collections.Generic;
using System;
using System.Collections;

class Program
{
    static void Main(string[] args)
    {
        var input = new BitArray(new byte[] { 0x5A /*01011010b*/
                                        , 0xE4 /*11100100b*/ });
        var output = new List<int>();
        var offset = 1;
        foreach (var bit in input)
        {
            if (bit)
            {
                output.Add(offset);
            }
            offset++;
        }
    }
}

Answer 11

I have tried a different approach. The idea is to keep getting a random entry and exit when an entry corresponding to 1 is found. This solution is not perfect because some randoms are not used which may or may not break the randomness. In addition, the speed greatly depends on the density of "1"s. Code is as follow:

public static int GetRandomSetBit(int[] AllBits)
{
    int L = AllBits.Length;
    Random r = new Random();    // Better use a global instance as this hurt performance a lot
    do
    {
         selected = r.Next(L);

    } while (AllBits[selected] == 0);
    return selected;
}

In my PC, if the creation of the Random object is moved into global, it can run 50000000 trials in around 11s if there are 5 "1"s out of 30. If there are up to 15 "1"s, the time it takes is shortened to around 5s.

Comparing with the code as suggested by Vilx, his code can run 50000000 trials in my PC around 13s