How to remove every second element of a SortedDictionary as fast as possible?

Question

I've to remove every second element from a SortedDictionary as fast as possible. The dictionary (SortedDictionary<string, List<string>>) can have up to 20'000 elements. So I came up with this solution:

try
{
    int loop = 0;
    while (true)
    {
        Routes.Remove(Routes.ElementAt(loop).Key);
        loop++;
    }                
}
catch
{
}

Is there an easier / better solution than this? Will the caught exception have an impact on the performance?

Edit: This seems to be a better solution (see comment below):

SortedDictionary<string, List<string>> resizedRoutes = new SortedDictionary<string, List<string>>();
bool b = true;
foreach(KeyValuePair<string, List<string>> route in Routes)
{                                        
    if(b)
    {
        resizedRoutes.Add(route.Key, route.Value);
        b = false;
    }
    else
    {
        b = true;
    }
}
Routes = resizedRoutes;

Please edit/comment if you have a better solution. Thanks.

Answer 1

I doubt it, because you either need to:

1. Remove the items, causing the tree to be rebalanced

2. Add the items to a new tree, causing the new tree to be rebalanced

You can't really avoid it, but it might be more efficient to just iterate through them and put them in a SortedList if you won't be modifying the data very often.

Yes:

Iterate through the items, then add every other item them to a new tree, instead of modifying the current tree. That way you'll avoid the cost of calling ElementAt every time, which is at least logarithmic in an ideal implementation, and linear with LINQ's (which is horrible, because LINQ has no idea about the implementation of your tree).

As for the exception: Yes, it will have a performance hit. But I have no idea how much that is relative to what you're doing, so it may or may not be significant.
But either way, you should not be ignoring exceptions. :)

While you're at it:

Might want to take a look at functional programming. :)