Удаление альтернативных элементов в ListT

18

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

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

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

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

    
задан abhilash 07.03.2009 в 14:05
источник
  • Что вы подразумеваете под альтернативным? –  Mehrdad Afshari 07.03.2009 в 14:10
  • Вы хотите удалить каждый другой элемент, т. е. все элементы с четным индексом или все элементы с нечетным индексом? –  R. Martinho Fernandes 07.03.2009 в 14:13
  • да, даже индексированные или нечетные индексы. –  abhilash 07.03.2009 в 14:17
  • Люди, (и людьми, которые я особенно имею в виду с высшим представителем), мы должны научиться поднимать такие вопросы. Если бы вопрос был достаточно интересен для нас, чтобы не торопиться, чтобы не участвовать в нем? –  AnthonyWJones 07.03.2009 в 14:38
  • @ AnthonyWJones, я поддержал, как только ОП поставил вопрос яснее. –  JaredPar 07.03.2009 в 15:11

8 ответов

26

Если вы вызываете 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:
Этот метод обработает список из миллиона ints за 15 мс. Используя RemoveAt, это займет три минуты ...

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

    
ответ дан Guffa 07.03.2009 в 14:22
источник
  • Я думаю, что это будет работать, только если количество элементов в списке четное. –  tvanfosson 07.03.2009 в 14:26
  • Я думаю, мне просто нужно начинать с 1 не 0, тогда этот код будет работать –  AnthonyWJones 07.03.2009 в 14:35
  • @tvanfosson: Нет, я проверил, что код работает как для четного, так и для нечетного числа элементов. @AnthonyWJones: Если вы хотите удалить четные индексы вместо нечетного, вы начинаете с 1 вместо 0. –  Guffa 07.03.2009 в 14:43
  • +1 веселое решение. Что немного беспокоит это (и мое) решение, так это то, что он не изменит размер базового массива независимо от того, сколько раз он называется и, следовательно, сокращается. –  JaredPar 07.03.2009 в 14:50
  • @Martin, к сожалению, не O (1), поскольку удаление вызывает смещение элементов в массиве. Смещение может быть очень дорогостоящим: blogs.msdn.com/jaredpar/archive/2008/04/07/... –  JaredPar 07.03.2009 в 22:23
Показать остальные комментарии
7

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

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

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

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

в зависимости от выбранного вами варианта.

ИЗМЕНИТЬ

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

    
ответ дан flq 07.03.2009 в 14:22
источник
  • Я думаю, вы добавили код F # там :) –  JaredPar 07.03.2009 в 14:39
  • Не уверен, что вы это иронизируете? Это, безусловно, код C #, я попробовал его, прежде чем я разместил его здесь. Честно говоря, я немного удивлен, что это не получается, учитывая, что это самый простой ответ всего ... –  flq 07.03.2009 в 14:47
  • Это не отвечает ни одному из требований OP. Он хочет удалить элементы из списка, который этот код не делает. Он хочет производительности, которые этот код также не дает. –  Hosam Aly 07.03.2009 в 14:56
  • Отказ от этого - простой, и итератор часто именно то, что вам нужно. –  rjh 07.03.2009 в 14:57
  • @Frank, я думал, что _ был незаконным идентификатором в C #, потому что C # требовал минимум одного альфа-символа. Узнавайте что-то новое каждый день. –  JaredPar 07.03.2009 в 15:04
Показать остальные комментарии
5

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

bool isEven = true;            
var newList = list.Where(x => isEven = !isEven).ToList();
    
ответ дан Martin Jonáš 07.03.2009 в 16:34
источник
2

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

List<T> list = GetTheList();
int i = 1;
while ( i < list.Count ) {
  list.RemoveAt(i);
  i++;
}
    
ответ дан JaredPar 07.03.2009 в 14:16
источник
  • Когда вы удаляете элемент в начале, все остальные будут сдвигаться вниз. Это, безусловно, не устранит альтернативные элементы и может привести к исключению в зависимости от того, пересчитывается ли защита на каждом шагу, т. Е. List.Count будет меняться. –  tvanfosson 07.03.2009 в 14:24
  • @tvanfonsson: Код выглядит хорошо для меня? –  AnthonyWJones 07.03.2009 в 14:31
  • @Anthony - когда вы удаляете элемент в позиции 2, элемент в позиции 3 сдвигается на 2, 4 смены на 3 и т. д., поэтому следующий элемент, который удаляется, фактически находится в позиции 5 в исходном списке, не позиция 4. –  tvanfosson 07.03.2009 в 14:33
  • Он работает, но он очень неэффективен. Чтобы обработать список из 1000 целых чисел, вы будете перемещаться близко к одному MB данных ... –  Guffa 07.03.2009 в 14:38
  • @tvanfosson: этот код, похоже, полагается на поведение, которое вы описываете как часть решения. Обратите внимание, что i увеличивается только на 1 итерацию, в сочетании с перемещением позиции, которую вы описываете, будет удаляться только каждый другой элемент, как и ожидалось. –  AnthonyWJones 07.03.2009 в 14:41
Показать остальные комментарии
2

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

    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<> . Стоимость итерации откладывается до итерации, что может быть большой победой, если в конце вам не нужно касаться всех элементов в списке.

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

    
ответ дан Jay Bazuzi 07.03.2009 в 17:47
источник
1
for (int i=myList.length-1; i >= 0; i--)
  if (i % 2 == 0)
    myList.Remove(myList[i]);
    
ответ дан tsilb 07.03.2009 в 16:41
источник
1

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

    
ответ дан wowest 07.03.2009 в 17:29
источник
  • Умный! Но хрупкий. –  Alex Reynolds 07.03.2009 в 17:34
0

Я бы использовал стандартный шаблон, обычно используемый для контейнеров 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());

}
    
ответ дан Martin York 07.03.2009 в 17:07
источник