Go Premium for a chance to win a PS4. Enter to Win

x
?
Solved

Which is faster? ForEach or IndexOf.

Posted on 2006-11-15
9
Medium Priority
?
321 Views
Last Modified: 2012-06-22
Hi.

Looking for some information on which method is faster. I'm using a List of Player objects, which rougly contains 10-40 Player objects when the function is called. Speed is an issue, as the socket itself is slow enough.

        /// <summary>
        /// Handles player leaving the room.
        /// </summary>
        /// <param name="token">StringTokenizer</param>
        /// <remarks>
        /// v,2859,1,Sp&AAPIrg Vicev&AAOGrt,
        /// </remarks>
        internal static void HandlePlayerLeaveRoom(int id, StringTokenizer token)
        {
            Player player;

            // Method 1
            player = new Player(id);
            players.Remove(players[players.IndexOf(player)]);
            players.TrimExcess();

            // Method 2
            // Check if player exists.
            players.ForEach(delegate(Player player)
            {
                // Found match.
                if (player.Id == id)
                {
                    // Remove the player.
                    players.Remove(player);
                    players.TrimExcess();
                    return;
                }
            });
        }

Thanks for reading.
0
Comment
Question by:valvet
6 Comments
 

Author Comment

by:valvet
ID: 17952636
As I see it, IndexOf is just another foreach loop, but I'm not sure.
0
 

Author Comment

by:valvet
ID: 17952696
Here's another function, using same concept.

        internal static void HandlePlayerMove(int id, StringTokenizer token)
        {
            Player player;

            // Method 1
            players.ForEach(delegate(Player player)
            {
                // Found a match.
                if (player.Id == id)
                {
                    // Set player position.
                    player.SetPosition(
                        int.Parse(token.nextToken()),
                        int.Parse(token.nextToken())
                        );

                    return;
                }
            });
           
            // Method 2
            // Create new player.
            player = new Player(id);
            player = players[players.IndexOf(player)];
            player.SetPosition(
                int.Parse(token.nextToken()),
                int.Parse(token.nextToken())
                );
        }
0
 
LVL 48

Expert Comment

by:AlexFM
ID: 17953920
Are you sure that method 1 is correct?

player = new Player(id);
players.Remove(players[players.IndexOf(player)]);

IndexOf must return -1.
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 48

Expert Comment

by:AlexFM
ID: 17954133
Anyway, if your Player class has implements comparing which makes this way working, I tnink that method 2 is better.

Method 1:

player = new Player(id);
players.Remove(players[players.IndexOf(player)]);

Pseudo-code:
1. players.IndexOf(player)    O(n)
foreach Player p in players
{
    if (p == player) return index of p;
}

2. players[index]   O(1)

3. Remove( instance )   O(n)

This is still O(n), but requires two list scans: 1 and 3. While Method 2 (ForEach) requires 1 list scan.
Anyway, to be sure for 100%, make test in loop running both methods thousands times, and measure execution time with StopWatch class.
0
 
LVL 4

Expert Comment

by:satish_nagdev
ID: 17954253
hi,
though i've not gone through your code but foreach has -ve effect on performance as far as i've heard.

regards.
satish.
0
 
LVL 12

Accepted Solution

by:
AGBrown earned 800 total points
ID: 17972314
It depends on what Players is, I think. In summary, and generalising fantastically, (fastest) BinarySearch >> Linear Search (for loop) > ForEach (slowest).

Assuming that Players is a List<Player> in .NET 2.0, then IndexOf uses the Comparer for the List<Player> to get the index. This simply does a "for" loop to go through the list in order, and match the item you've supplied using the "Equals" method of the object type you are using. It does this through the Array.IndexOf<T> static method, passing the Lists<T>'s internal storage array as the search array.

Depending on the ratio of Inserts to Searches you are doing in your lists, you might be better with a SortedList (in .NET 2.0). This list uses BinarySearch to locate items in the list, which is on average vastly quicker than a linear search. Similarly, this uses the Array.BinarySearch<T> method, passing the internal array that is maintained in a sorted order by the SortedList class. The effect becomes more pronounced with list size due to the order of the operation: O(log n) for binary search compared to O(n) for linear search, where n is the number of items in the array/list.

If you are using .NET 1.1 you can still use this binary searches, by maintaining the list in the order you required for your searches. You do this by using BinarySearch on the list to get the bitwise complement of the items position, or the items position if it is already in the list. If it isn't in the list then you insert at the position that the complement tells you to do by doing ~i to get the desired position.

ForEach requires the object to return an enumerator via the GetEnumerator method. In its simplest form, an enumerator is similar to a for loop, in that it internally records your current position, and on each interation of your foreach loop (called through the MoveNext method of the enumerator), the position counter is incremented by 1.

ForEach is therefore going to be marginally slower than For, as you have the "overhead" of method calls, and of creating/returning the enumerator object (though IndexOf also has a few method calls). However, you need to ask if this is really going to be significant compared to the other slowest parts of your application, and you can only do that by testing your exact scenario. Interestingly, .NET 2.0 offers a way of speeding up enumerators by using the yield keyword, or by developing your own custom iterators, which can be faster than the default iterators and than using yield.

The quickest search method for lists, by far, is BinarySearch, which neither IndexOf nor ForEach use by default. For that to work you need to maintain an ordered list of some sort (using BinarySearch to do so, either up front or as part of the internal mechanism of a .NET 2.0 SortedList). This can be expensive if you have many many inserts compared to searches, but it might still be faster than doing linear searches each time you want to search.

Does that help?

Andy
0

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Summary: Persistence is the capability of an application to store the state of objects and recover it when necessary. This article compares the two common types of serialization in aspects of data access, readability, and runtime cost. A ready-to…
The article shows the basic steps of integrating an HTML theme template into an ASP.NET MVC project
Please read the paragraph below before following the instructions in the video — there are important caveats in the paragraph that I did not mention in the video. If your PaperPort 12 or PaperPort 14 is failing to start, or crashing, or hanging, …
This lesson discusses how to use a Mainform + Subforms in Microsoft Access to find and enter data for payments on orders. The sample data comes from a custom shop that builds and sells movable storage structures that are delivered to your property. …
Suggested Courses

876 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question