0

I am creating a Fingerprint Verification System in which I have to match fingerprints using records in database. I have used foreach loop to to so but it is taking almost 40 seconds for only 350 records. I want to speed it up. I want my foreach loop to convert into for loop but I am facing some difficulties in initializing the for loop. Here is my code.

foreach (KeyValuePair<decimal, MemoryStream> tt in profileDic)
{
    this.Invoke(new Function(delegate()
    {
        textBox1.Text += "\n" + tt.Key.ToString();
    }));
    temp = new DPFP.Template(tt.Value);

    Verificator = new DPFP.Verification.Verification();
    featuresForVerification = ExtractFeatures(Sample, DPFP.Processing.DataPurpose.Verification);
    if (featuresForVerification != null)
    {
        DPFP.Verification.Verification.Result result = new DPFP.Verification.Verification.Result();
        Verificator.Verify(featuresForVerification, temp, ref result);

        #region UI Envoke
        this.Invoke(new Function(delegate()
        {
            if (result.Verified)
            {
                MessageBox.Show("FAR " + result.FARAchieved + "\n" + tt.Key.ToString());
            }
            else
            {
                //MessageBox.Show("No Match");
            }
        }));
        #endregion
    }
    this.Invoke(new Function(delegate()
    {
        progressBar1.Value += 1;
    }));
    Thread.CurrentThread.Priority = ThreadPriority.Highest;
}

I am confused at the first line foreach (KeyValuePair<decimal, MemoryStream> tt in profileDic). Can someone tell me how I can iterate through every item in Dictionary object profileDic using a for loop. I am not sure how to get KeyValuePair<decimal, MemoryStream> tt in profileDic when using a for loop.

JohnLBevan
  • 22,735
  • 13
  • 96
  • 178
Delicate Hiba
  • 63
  • 1
  • 5
  • 13
  • 7
    What makes you think a `for` loop will improve the speed? Have you run a profiler to find out which part is actually slow? – James Thorpe Jul 07 '17 at 07:38
  • In addition to @JamesThorpe, you might also want to check your database, if your queries aren't up to speed it won't improve a lot. – Blaatz0r Jul 07 '17 at 07:39
  • i searched for it here https://stackoverflow.com/a/365658 – Delicate Hiba Jul 07 '17 at 07:39
  • That's just the actual act of iterating - usually whatever you're doing within the loop is several orders of magnitude slower, especially if you're talking off to a database etc – James Thorpe Jul 07 '17 at 07:41
  • actually i am getting data from database just single time. i am loading that data in to dictionary object and then matching processing on that object – Delicate Hiba Jul 07 '17 at 07:41
  • @DelicateHiba, the url that you specified talks about a list not a dictionary. "for loops on List are a bit more than 2 times cheaper than foreach loops on List." – Blaatz0r Jul 07 '17 at 07:42
  • you can see my code that is taking 40 seconds to complete 350 iterations. can you tell me which code is taking more time? – Delicate Hiba Jul 07 '17 at 07:43
  • ok how i can speed it up then? – Delicate Hiba Jul 07 '17 at 07:44
  • 2
    `Verificator = new DPFP.Verification.Verification();`; does this line work? If so, `Verificator` is an object, not a class, so should be called `verificator`. Do you need to reinitiatlise that object each iteration, or does it allow you to reuse the same object, making multiple calls to `Verify` without the previous call affecting results? – JohnLBevan Jul 07 '17 at 07:45
  • 2
    _"can you tell me which code is taking more time?"_ No, but a good profiler can. Look at Ants or dotTrace for example. – James Thorpe Jul 07 '17 at 07:45
  • 1
    Beginners Guide to Performance Profiling (in Visual Studio) https://msdn.microsoft.com/en-us/library/ms182372.aspx – JohnLBevan Jul 07 '17 at 07:46
  • I agree with the chorus: 40 seconds for 350 elements in your dictionary sounds excessive, and the foreach loop is not likely to be a significant part of that time. Please profile your code to find where the time is spent. – dumetrulo Jul 07 '17 at 07:48
  • There are a couple of methods here that we don't know the details of, like `ExtractFeatures()` and `Verify()`. Making it hard to guess what might be wrong. I'd say as others and run a profiler, and double check the sql execution plans. – scheien Jul 07 '17 at 07:49
  • @JohnLBevan now i'm reusing the ole Instance of Verificator that you suggested but the time is still the same. – Delicate Hiba Jul 07 '17 at 07:51

4 Answers4

2

I have to match [entries against a list]. I have used foreach loop to do so but it is taking almost 40 seconds for only 350 records. I want to speed it up. I want my foreach loop to convert into for for loop [...]

At such a point it is a good idea to just step back and think about what we are doing here in general. Performance optimization usually comes on two levels: algorithms and workflow.

Essentially, the problem to be solved here is to find an entry in a potentially large set of records. There may be two causes why this is slow:

  • the list is very large, and iterating it takes ages
  • the list may not be that large, but the routine is called quite often

The list is very large

If we remember our knowledge about the so-called Big-O notation and think about it, we may quickly find that an array search takes O(n) while a hash set search for example would only take O(1) in normal cases, only in the worst case we will be again down to O(n). Not bad!

By some lucky coincident (and by the help of the cheat sheet linked above) we find out that a Dictionary<K,V> or alternatively a database index is more or less what we want: A dictionary is basically a "pimped" hash set, and a database index is typically a B-Tree, which performs with Θ(log(n)). The final decision if we should use a dictionary or a database table mostly depends on the amount of data we are talking about.

As a practical example, I recently had a piece of code on my table that iterated through a list in the same linear manner. The code did this inside of two other, nested loops. The algorithm took 4 hours to complete. After introducing two dictionaties at strategic places I had it down to under a minute. I leave it to the amused reader to calculate the percentage.

Hence, the real question to ask is not "is for faster than foreach?" (no) but instead we should ask: "How can I reorganize my data structures and optimize the algorithms involved to make it perform?"

The code is called quite often

That's another, but related problem. In some cases the data structures can't really be optimized, or it would cause way too many changes in the code. But when we closely look at what the profiler is telling us, we may find that the costly rountine is called 800.000 times in 15 seconds and that these calls alone contribute a fair amount to the total time.

If we look even closer, we may find that we call the routine with a very limited set of input data, so that essentially a large portion of the calls may just be omitted by caching the results of the costly operation. I just had such a case last week where I was able to reduce the amount of database calls down to 5% of the original amount. One can imagine what that did to overall performance.

In this second case we therefore should ask ourselves a slightly different question: "Why are we doing this at all? How can we change the logical workflow to avoid most of these calls? Is there maybe a completely different way to achieve the same results?".

Summary (TL;DR)

There are two basic approaches with every performance optimization:

  • Algorithmic or "low level": Quicksort or Bubblesort? Tree, List or HashSet?
  • Workflow and Logic: Why do we have to call that particular costly routine 5 million times?
JensG
  • 13,148
  • 4
  • 45
  • 55
0

Instead of changing it to Foreach Loop from For Loop, You might actually want to add like Exit For or Break; in c# once you already find the result.

Fernan Vecina
  • 144
  • 1
  • 8
0

What biometric system are you using? This kind of work should be done in biometric device. But if you really need to find a person directly in database, you should not use C# collections, but database itself.

Every fingerprint has its minutiaes. There are unique features of fingerprint. There are some algorithms that transform this into storable data for example in database. This could look like md5 hash.

Next, when you have records in database with minutiaes, you can just ask database for this value.

It should work like that: you get minutias (or complete data that can be stored directly in database) and then ask database for this value, something like:

SELECT *
FROM users
WHERE fingerprint = :your_data

Database operations are far more faster than iterating throug any collection in any way.

Adam Jachocki
  • 1,897
  • 1
  • 12
  • 28
0

To answer your stated question: to replace a foreach loop with a for loop, replace:

foreach (KeyValuePair<decimal, MemoryStream> tt in profileDic) 
{
    //...
}

with

for (var i=0; i < profileDic.Count, i++) 
{
    KeyValuePair<decimal, MemoryStream> tt = profileDic.ElementAt(i);
    //...
}

To use this you'd also need to include a using System.Linq; statement in your code. That said, this assumes that the order of elements in your dictionary will not change; which is not guaranteed (unless you're using a SortedDictionary or OrderedDictionary). A better approach is therefore:

[decimal[]]keys = profileDic.Keys;
for (var i=0; i < keys.Count, i++) 
{
    KeyValuePair<decimal, MemoryStream> tt = profileDic[keys[i]];
    //...
}

But this adds more overhead / likely pushes the for loop's time over that of the foreach loop / is a micro-optimisation that won't solve your real performance issue.


Per comments, the loop is likely not your problem, but what's occurring within that loop (if in this part of the code at all).

We don't know enough about your code to comment on it, so it's likely best that you investigate yourself; e.g. using the performance analysis techniques described here: https://msdn.microsoft.com/en-us/library/ms182372.aspx

I've refactored your code to make it more readable (i.e. by pulling the UI updates into their own methods, so they don't clutter the main thread).

I also moved those operations which look like they wouldn't need to be updated each iteration outside of your loop... but without knowing your code this is pure guesswork / so no guarantees.

Finally I removed your code to alter the priority of the current thread at the end of each iteration. Playing with thread priorities is not a good way to fix slow code; there are only certain cases where it's appropriate, and seeing it's context here I'm over 99% certain that this is not one of those cases.

//...
featuresForVerification = ExtractFeatures(Sample, DPFP.Processing.DataPurpose.Verification); //since this appears unaffected by our profileDic values, let's initialise once
if (featuresForVerification != null)
{
    DPFP.Verification.Verification verificator = new DPFP.Verification.Verification();
    foreach (KeyValuePair<decimal, MemoryStream> tt in profileDic)
    {
        string key = tt.Key.ToString(); //we use this a lot, so let's only convert it to string once, then reuse that
        UIReportCurrentKey(key);
        temp = new DPFP.Template(tt.Value); 
        DPFP.Verification.Verification.Result result = new DPFP.Verification.Verification.Result();
        verificator.Verify(featuresForVerification, temp, ref result);
        UIReportMatch(result, key);
        //if a match were found, would we want to keep comparing, or exit on first match?  If the latter, add code to record which record matched, then use break to exit the loop
        UIIncremementProgressBar();
    }
} else {
    throw new NoFeaturesToVerifyException("The verfication tool was not given any features to verify");
    //alternatively set progress bar to complete / whatever other UI actions you have /
    //whatever you want to happen if no features were selected for comparison
}


//...

#region UI Updaters
/*
    I don't know much about winforms updates; have a feeling these can be made more efficient too, 
    but for the moment just shoving the code into its own functions to make the main method less
    cluttered with UI logic.
*/

// Adds the key of the item currently being processed to the UI textbox
private void UIReportCurrentKey(string key) 
{
    this.Invoke(new Function(delegate()
    {
        textBox1.Text += "\n" + key;
    }));
}
private void UIReportMatch(DPFP.Verification.Verification.Result result, string key) 
{
    if (result.Verified) 
    {
        this.Invoke(new Function(delegate()
        {
                MessageBox.Show("FAR " + result.FARAchieved + "\n" + key);
        }));
    } 
    /* 
    else 
    {
        this.Invoke(new Function(delegate()
        {
                MessageBox.Show("No Match");
        }));        
    } 
    */
}
private void UIIncremementProgressBar() 
{
    this.Invoke(new Function(delegate()
    {
        progressBar1.Value++;
    }));
}

#endregion UI Updaters

#region Custom Exceptions
public class NoFeaturesToVerifyException: ApplicationException 
{ //Choose base class appropriately
    public NoFeaturesToVerifyException(): base() {}
    public NoFeaturesToVerifyException(string message): base(message) {}
    //...
}
#endregion Custom Exceptions
JohnLBevan
  • 22,735
  • 13
  • 96
  • 178