Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I have this piece of code that is running too slow. I was wondering if anyone can help me optimize it as I can't seem to find any more shortcuts. I'm not sure if using List<> is going to help me but I need complex operation such as Union and Overlap.

Also, List is desirable because I don't know how many unique partitions an Image Region is going to be before running.

u1.length = 13254 which is the number of distinct elements in RevisedListMeanH RevisedListMeanH.Count = 90000

The purpose of the first piece of code is to group together pixels via horizontal comparison and vertical comparison. This runs for about 70 seconds.

The second portion combines both vertical and horizontal pixel blocks into a 2D-block. This section runs for about 120 seconds. My goal is to have both of these loops complete under 10 seconds.

These numbers are from a 300x300 pixel region comparisons of a 4000x3000 image.

watch.Start();            
for (int s = 0; s < u1.Length; s++ )//iterate through uniquelist
{
    List<int> ConnectedBlocksH = new List<int>();
    List<int> ConnectedBlocksV = new List<int>();

    float[] RH = RevisedListMeanH.ToArray();
    float[] RV = RevisedListMeanV.ToArray();

    for (int a = 0; a < RevisedListMeanH.Count; a++)//iterate through bitmap with res
    {
        if (u1[s] == RH[a])
        {
            ConnectedBlocksH.Add(a);//add the index

        }
    }
    for (int a = 0; a < RevisedListMeanV.Count; a++)//iterate through bitmap with res
    {
        if (u1[s] == RV[a])
        {
            ConnectedBlocksV.Add(a);//add the index

        }
    }
    ArrayOfConnectedBlocksH[s] = ConnectedBlocksH;//where the data IS
    ArrayOfConnectedBlocksV[s] = ConnectedBlocksV;//where the data IS
}
watch.Stop();
long asasasdda = watch.ElapsedMilliseconds; //71 sec
watch.Reset();

 watch.Start();
//if intersects then union the two lists
//iterate through both list
List<List<int>> ListOfConnectedBlocks = new List<List<int>>();
for (int a = 0; a < ArrayOfConnectedBlocksH.Length; a++ )
{
    HashSet<int> i = new HashSet<int>(ArrayOfConnectedBlocksH[a]);
    //trigger means it scanned and there was no overlap to add to the group
    while (true)
    {

        bool trigger = true;
        for (int b = 0; b < ArrayOfConnectedBlocksV.Length; b++)
        {
            if (i.Overlaps(ArrayOfConnectedBlocksV[b]))
            {
                i.UnionWith(ArrayOfConnectedBlocksV[b]);//combines all overlaps into one group
                ArrayOfConnectedBlocksV[b].Clear();//merged so just remove
                trigger = false;
            }

        }
        if (trigger)
        {
            break;
        }
        trigger = true;
        for (int c = 0; c < ArrayOfConnectedBlocksH.Length; c++)//now cycle through horizontal
        {
            if (i.Overlaps(ArrayOfConnectedBlocksH[c]))
            {
                i.UnionWith(ArrayOfConnectedBlocksH[c]);//combines all overlaps into one group
                ArrayOfConnectedBlocksH[c].Clear();//merged so just remove
                trigger = false;
            }

        }//first cycle to get T0

        if(trigger)
        {
            break;
        }
    }

    if (i.Count != 0)
    {
        ListOfConnectedBlocks.Add(i.ToList<int>());
    }
}

watch.Stop();
long asasasda = watch.ElapsedMilliseconds;//122 seconds

______EDIT____ This is what I came up with and it runs in 100ms

        Dictionary<float, List<int>> ArrayOfConnectedBlocksH = new Dictionary<float, List<int>>();
        Dictionary<float, List<int>> ArrayOfConnectedBlocksV = new Dictionary<float, List<int>>();

        watch.Start();

        var distinct1 = new HashSet<float>();

        for (int s = 0; s< RevisedListMeanH.Count; s++){
            if (distinct1.Add(RevisedListMeanH[s]))//is distinct
            {
                ArrayOfConnectedBlocksH.Add(RevisedListMeanH[s], new List<int>(){s});                   
            }
            else //is not distinct
            {
                ArrayOfConnectedBlocksH[RevisedListMeanH[s]].Add(s);
            }
        }
        distinct1.Clear();

        for (int s = 0; s < RevisedListMeanV.Count; s++)
        {
            if (distinct1.Add(RevisedListMeanV[s]))//is distinct
            {
                ArrayOfConnectedBlocksV.Add(RevisedListMeanV[s], new List<int>() { s });
            }
            else //is not distinct
            {
                ArrayOfConnectedBlocksV[RevisedListMeanV[s]].Add(s);
            }
        }

        watch.Stop();
        long asasasdda = watch.ElapsedMilliseconds; 

For the second section of the code, I decided to use a linkedlist so I can remove items and iterate without screwing up the enumerator. I just used a while loop and decremented until 0. The speed was reduced to about 60 seconds instead of 120 seconds.

I don't see a way of avoiding O(n^2) time as I need to iterate each item over a list of same size. However it is slightly less than O(n^2) as I am able to remove some loops as I deleted the items that I have already scanned over.

share|improve this question
    
I personally get rather annoyed when I see List.Add() in a loop inside an if, because to me that means its just begging for an .AddRange() and a .Where(), but the fact that you're adding the index makes that far too difficult. Still, creating two arrays each iteration and growing them one by one in the inner loops is certainly worth looking carefully at when trying to determine what's slowing you down. –  Magus Mar 10 at 19:35

3 Answers 3

up vote 1 down vote accepted

Some suggestions which might make it faster:


Move your ToArray() statements outside the loop so that you only execute them once and then reuse them:

float[] RH = RevisedListMeanH.ToArray();
float[] RV = RevisedListMeanV.ToArray();

for (int s = 0; s < u1.Length; s++ )//iterate through uniquelist
{
    ... etc ...

In the second loop, you convert a List to a HashSet:

HashSet<int> i = new HashSet<int>(ArrayOfConnectedBlocksH[a]);

You could avoid that by making ArrayOfConnectedBlocksH[a] i.e. ConnectedBlocksH a HashSet instead of a List to begin with.


Might it be any faster if you cached the Length and Count property values instead of calling them repeatedly? For example:

for (int s = 0, int length = u1.Length; s < length; s++ )

The basic problem in your first loop is that you are iterating a lot of elements, and doing u1.Length * (RevisedListMeanH.Count + RevisedListMeanV.Count) comparisons.

It might be faster although more complicated to do the following.

Convert your u1 list to a list of index/value pairs:

List<KeyValuePair<int,float>> u1Values = new List<KeyValuePair<int,float>>();
for (int s = 0; s < u1.Length; s++ )
    u1Values.Add(new KeyValuePair<int,float>(s, u1[s]));

Sort your index/value pairs by value:

u1Values.Sort((kvp1, kvp2) => kvp1.Value.CompareTo(kvp2.Value));

Do the same with your RevisedListMeanH and RevisedListMeanV lists.

Now that your all arrays are sorted by value, it is easier/cheaper to find which elements match: you can do it by iterating through all the arrays once; something like:

int u = 0; // index into u1Values
int v = 0; // index into vValues

for (;;)
{
    int i = u1Values[u].Value.CompareTo(vValues[v].Value);
    if (i == 0)
    {
        // matches!
        int s = u1Values[u].Key;
        ArrayOfConnectedBlocksV[s].Add(vValues[v].Key);//add the index
        // which do we increment now: ++u or ++v?
    }
    else if (i > 0)
    {
        // u1Values[u] is too big
        if (++v == u1Values.Count)
            break;
    }
    else
    {
        if (++u == vValues.Count)
            break;
    }
}
share|improve this answer
    
Thanks for the feedback I have found a solution. This runs about 100 ms instead of 70 seconds. This is for the first section. Thank you for your inputs. –  Bwang22 Mar 11 at 0:23

First of, I'm gonna give you a basic idea...

Instead of doing 2 loops over two different arrays, check their sizes first. Create a loop for the smaller of both array sizes. In that loop you will process that Array, and then create another loop for the remainder of unprocessed data.

This can be done for your two double fors you have in there. This way you could reduce the complexity from O(n+m) to O(n+(m-n))

The pseudo code is this...

if(Arr1 > Arr2)
{ 
   process(Arr1, Arr2);
}
else if (Arr2 > Arr1)
{
   process(Arr2, Arr1);
}
else //They're the same size!
{
  for(idx = 0; idx != count(any will do); ++idx)
  {
     //process Arr1
     //process Arr2
   }
}
share|improve this answer

Your mileage may vary, but LINQifying a bit makes it a heck of a lot more readable...

        watch.Start();

        // if intersects then union the two lists
        // iterate through both list
        var listOfConnectedBlocks = new List<List<int>>();

        foreach (var i in ArrayOfConnectedBlocksH.Select(t1 => new HashSet<int>(t1)))
        {
            // trigger means it scanned and there was no overlap to add to the group
            while (true)
            {
                var trigger = true;

                foreach (var t in ArrayOfConnectedBlocksV.Where(i.Overlaps))
                {
                    i.UnionWith(t); // combines all overlaps into one group
                    t.Clear(); // merged so just remove
                    trigger = false;
                }

                if (trigger)
                {
                    break;
                }

                trigger = true;

                // now cycle through horizontal
                foreach (var t in ArrayOfConnectedBlocksH.Where(i.Overlaps))
                {
                    i.UnionWith(t); // combines all overlaps into one group
                    t.Clear(); // merged so just remove
                    trigger = false;
                }

                // first cycle to get T0
                if (trigger)
                {
                    break;
                }
            }

            if (i.Any())
            {
                listOfConnectedBlocks.Add(i.ToList());
            }
        }

        watch.Stop();
        var asasasda = watch.ElapsedMilliseconds; // ? seconds
    }
share|improve this answer
    
Thanks I'll add more Linq to my code. Just beginning to use them. But it does Linq does seem slow if its used in loops. –  Bwang22 Mar 11 at 0:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.