• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 344
  • Last Modified:

Which is faster? ForEach or IndexOf.

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
valvet
Asked:
valvet
1 Solution
 
valvetAuthor Commented:
As I see it, IndexOf is just another foreach loop, but I'm not sure.
0
 
valvetAuthor Commented:
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
 
AlexFMCommented:
Are you sure that method 1 is correct?

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

IndexOf must return -1.
0
Get expert help—faster!

Need expert help—fast? Use the Help Bell for personalized assistance getting answers to your important questions.

 
AlexFMCommented:
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
 
satish_nagdevCommented:
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
 
AGBrownCommented:
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
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

Featured Post

Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now