Удаление альтернативных элементов в Списке <T> - PullRequest
Новая
       46

Удаление альтернативных элементов в Списке <T>

18 голосов
/ 07 марта 2009

Каков наиболее эффективный способ удаления альтернативных (нечетных или даже проиндексированных) элементов в List<T> без использования переменной списка заполнителей?

Также было бы желательно, чтобы вы упомянули стоимость каждого ответа.

Я ищу эффективный способ сделать это

Заранее спасибо

Ответы [ 8 ]

27 голосов
/ 07 марта 2009

Если вы вызываете RemoveAt для каждого удаляемого элемента, вы будете перемещать много данных. Наиболее эффективным является перемещение элементов вместе, которые вы хотите сохранить, а затем удаление неиспользуемых элементов в конце: 

int pos = 0;
for (int i = 0; i < values.Count; i += 2, pos++) {
    values[pos] = values[i];
}
values.RemoveRange(pos, values.Count - pos);

Edit:
Этот метод обработает список из миллиона целых за 15 мс. Использование RemoveAt займет более трех минут ...

Edit2:
Вы можете начать с pos = 1 и i = 2 (или 3), так как первый элемент не нужно копировать самому себе. Это делает код немного менее очевидным.

8 голосов
/ 07 марта 2009

Только для рассмотрения решения, которое создает новый список со списком старый , вы можете сделать это: 

var newList = old.Where((_, i) => i%2 != 0).ToList();

или, очевидно, 

var newList = l.Where((_, i) => i%2 == 0).ToList();

в зависимости от выбора чередования.

EDIT

Ответ немного быстрее. Если вы читаете здесь что-то еще, это потому, что я измерил на выходных, а мозг выходного дня смешной. :( Закрывающее решение примерно на 40% быстрее, пока ответ - приложение. На 2 порядка быстрее. Я полагаю, это будет зависеть от того, насколько большим станет ваш список!

5 голосов
/ 07 марта 2009

И еще один вариант, похожий на вариант Фрэнка, но с использованием замыканий. И это быстрее, чем версия Фрэнка. 

bool isEven = true;            
var newList = list.Where(x => isEven = !isEven).ToList();
2 голосов
/ 07 марта 2009

Путь в Нирвану выложен отложенным исполнением. Или что-то. 

    public static IEnumerable<T> AlternateItems<T>(this IEnumerable<T> source)
    {
        while (source.Any())
        {
            yield return source.First();

            source = source.Skip(1);

            if (source.Any()) source = source.Skip(1);                
        }
    }

Это работает для всех последовательностей, а не только IList<>. Стоимость итерации откладывается до итерации, что может быть большим выигрышем, если, в конце концов, вам не нужно трогать все элементы в списке.

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

2 голосов
/ 07 марта 2009

Я не уверен, что вы подразумеваете под альтернативой, но если вы имеете в виду «любой другой элемент», следующий код будет работать Он начнется с удаления 2-го элемента, 4-го элемента и т. Д. 

List<T> list = GetTheList();
int i = 1;
while ( i < list.Count ) {
  list.RemoveAt(i);
  i++;
}
1 голос
/ 07 марта 2009

Очевидно, что использование зависит, но вы могли бы иметь обертку IList, которая умножает индекс, который вы даете ему на 2, и сообщает, что длина списка равна 1/2 (подробности пропущены). Это O (1).

1 голос
/ 07 марта 2009 
for (int i=myList.length-1; i >= 0; i--)
  if (i % 2 == 0)
    myList.Remove(myList[i]);
0 голосов
/ 07 марта 2009

Я бы использовал стандартный шаблон, обычно используемый для контейнеров STL. Сделайте удаление с последующим стиранием.

Таким образом, вы не будете путать людей, привыкших видеть этот шаблон. 

template<typename T>
struct RemoveEven
{
    RemoveEven():count(0)   {}
    bool operator()(T const&)
    {
        bool    result  =  count%2 == 0;
        count++;
        return result;
    }
    private:
        std::size_t count;
};
int main()
{
    std::list<int>  a;
    a.erase(std::remove_if(a.begin(),a.end(),RemoveEven<int>()),a.end());

}
...