Solved

Which is faster? ForEach or IndexOf.

Posted on 2006-11-15
9
258 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
9 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
Free Tool: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

 
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 200 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

Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

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.

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…
Exception Handling is in the core of any application that is able to dignify its name. In this article, I'll guide you through the process of writing a DRY (Don't Repeat Yourself) Exception Handling mechanism, using Aspect Oriented Programming.

820 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