Как удалить каждый второй элемент 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; }
    }
}

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