Solved

Which is faster? ForEach or IndexOf.

Posted on 2006-11-15
9
267 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
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
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!

 
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

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

We all know that functional code is the leg that any good program stands on when it comes right down to it, however, if your program lacks a good user interface your product may not have the appeal needed to keep your customers happy. This issue can…
Real-time is more about the business, not the technology. In day-to-day life, to make real-time decisions like buying or investing, business needs the latest information(e.g. Gold Rate/Stock Rate). Unlike traditional days, you need not wait for a fe…
In this video, viewers are given an introduction to using the Windows 10 Snipping Tool, how to quickly locate it when it's needed and also how make it always available with a single click of a mouse button, by pinning it to the Desktop Task Bar. Int…
In this brief tutorial Pawel from AdRem Software explains how you can quickly find out which services are running on your network, or what are the IP addresses of servers responsible for each service. Software used is freeware NetCrunch Tools (https…

626 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