Как удалить каждый второй элемент SortedDictionary как можно быстрее?

Question

Я должен удалить каждый второй элемент из SortedDictionary как можно быстрее. Словарь (SortedDictionary<string, List<string>>) может содержать до 20'000 элементов. Итак, я придумал это решение:

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

Есть ли более простое / лучшее решение, чем это? Повлияет ли пойманное исключение на производительность?

Изменить: это, кажется, лучшее решение (см. Комментарий ниже):

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;

Пожалуйста, отредактируйте / прокомментируйте, если у вас есть лучшее решение. Благодарю.

Answer 1

Я сомневаюсь, потому что вам нужно:

1. Удалите предметы, в результате чего дерево будет сбалансировано

2. Добавьте элементы в новое дерево, в результате чего новое дерево будет сбалансировано

Вы не можете избежать этого, но, возможно, было бы более эффективно просто просмотреть их и поместить вSortedListесли вы не будете изменять данные очень часто.

Да:

Перебирайте элементы, затем добавляйте каждый другой элемент в новое дерево вместо изменения текущего дерева. Таким образом вы избежите затрат на звонки ElementAt каждый раз, который является по крайней мере логарифмическим в идеальной реализации и линейным с LINQ (что ужасно, потому что LINQ не имеет представления о реализации вашего дерева).

Что касается исключения: да, это будет иметь удар по производительности. Но я понятия не имею, насколько это связано с тем, что вы делаете, поэтому это может быть или не быть значительным.
Но в любом случае, вы не должны игнорировать исключения.:)

Пока вы на это:

Возможно, стоит взглянуть на функциональное программирование.:)

Answer 2

Это достаточно хорошее решение. Если исключение обнаружено, оно прекратит удаление элементов из словаря. Может быть, переставить это, вот так:

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

Это обеспечит невозможность изменения словаря во время удаления элементов.