What to use for fast searching...... (.Net Framework Insights)

[ThatThatGuy]

One day i sat on researching what might be the fastest way to search for a particular... object in a List<T>....

The Searching Techniques i used....
was.....
For Loop
For Each Loop
While Loop
List<T>.Contain s //no intension retrieve index but only for checking
List<T>.Find Index // using Predicate
List<T>.FindInd ex ///using Lambda Expressions.
LINQ

I filled a List of type Rectangle..... will 10.6 million Rectangle objects....
and then searched for a known rectangle object and here are the results

For Loop 552 milliseconds
For Each 610 milliseconds
While Loop 594 milliseconds
List<T>.Contain s 203 milliseconds
List<T>.Find Index(Predicate ) 219 milliseconds
List<T>.FindInd ex(Lambda) 172 milliseconds
LINQ 781 milliseconds


and the award goes to List<T>.FindInd ex with Lambda Expressions...

LINQ happens to the most slowest and FindIndex with Lambda Expressions is the most fastest....

check it out.....

this test was done on a

Core2Duo 2.00 Ghz .... 2GB RAM machine

[tlhintoq]

You say you looked for a known item.
Did you look for the *last* item added to the List<>?
If you looked for any other item, then your values represent only a partial search.

[ThatThatGuy]

no i didnt looked for the last item .....i picked up a random item from the list....

[tlhintoq]

no i didnt looked for the last item .....i picked up a random item from the list....

Then your test is pretty much invalid.
Searching for the 10th item in one way, and the 5,000th item through a different technique is naturally going to take different amounts of time.

[ThatThatGuy]

No it's not like that .... that im checking he 5 th or 10 th item....
download the source (attached) and have a look at the source.....

[tlhintoq]

Where to begin?
First of all it doesn't create 10.6 million rectangles.

        private void button1_Click(object sender, EventArgs e)
        {// Fill
            lstRects.Clear();
            for (int intRCount = 0; intRCount < 4000; intRCount++)
            {
                for (int intCCount = 0; intCCount < 4000; intCCount++)
                {
                    lstRects.Add(new Rectangle(intRCount, intCCount, 15, 15));
                }
            }
            Console.WriteLine("Listcount: " + lstRects.Count.ToString());
        }

4000 * 4000 = 16,000,000 = 16 million rectangles

Weird way to calculate the time. Try using actual DateTime objects.

        private void button2_Click(object sender, EventArgs e)
        {// for...loop
            //int intStart = (DateTime.Now.Second*1000)+ DateTime.Now.Millisecond;
            DateTime StartTime = DateTime.Now;

            for (int intCount = 0; intCount < lstRects.Count; intCount++)
            {
                if (lstRects[intCount] == new Rectangle(1400, 1400, 15, 15))
                {
                }
            }
            DateTime EndTime = DateTime.Now;
            int Difference = (EndTime - StartTime).Milliseconds;
           //int intEnd = (DateTime.Now.Second*1000)+ DateTime.Now.Millisecond;
           //textBox1.Text = Convert.ToString(intEnd - intStart)+" milliseconds";
            textBox1.Text = string.Format("{0} milliseconds", Difference);
        }

You are only searching until you find the 1,960,000-th element out of 16 million. (1400x1400) If you want to check it against the last item look for 3999, 3999, 15, 15

You aren't stopping your search when you find the match.

            for (int intCount = 0; intCount < lstRects.Count; intCount++)
            {
                if (lstRects[intCount] == new Rectangle(1400, 1400, 15, 15))
                {
                }
            }

Therefor you aren't timing how long it takes to find anything. You are timing how long it takes to iterate through 16m elements and nothing more.

In some of your checks you are make another 16m rectangles as part of the search process.

            for (int intCount = 0; intCount < lstRects.Count; intCount++)
            {
                if (lstRects[intCount] == new Rectangle(1400, 1400, 15, 15))
                {
                }
            }

That throws off the actual search time because now it is "search and create" time.

Cleaning up your "For...Loop " method to something like this

        private void button2_Click(object sender, EventArgs e)
        {// for...loop
            //int intStart = (DateTime.Now.Second*1000)+ DateTime.Now.Millisecond;
            DateTime StartTime = DateTime.Now;
            DateTime EndTime = new DateTime();
            for (int intCount = 0; intCount < lstRects.Count; intCount++)
            {
                if (lstRects[intCount] == new Rectangle(1400, 1400, 15, 15))
                {
                    EndTime = DateTime.Now;
                    break;// Break out of the for loop
                }
            }
            int Difference = (EndTime - StartTime).Milliseconds;
           //int intEnd = (DateTime.Now.Second*1000)+ DateTime.Now.Millisecond;
           //textBox1.Text = Convert.ToString(intEnd - intStart)+" milliseconds";
            textBox1.Text = string.Format("{0} milliseconds", Difference);
        }

Changes my results from 478 ms to iterate through all 16m, to only 176ms because I stop when I find the match

[ThatThatGuy]

i think youre right.......... ............... .......