Suppression d'éléments alternatifs dans une liste <T>

Question

Quel est le moyen le plus efficace pour supprimer des éléments alternatifs (indexés ou indexés) dans un List<T> sans utiliser de variable de liste d'espaces réservés?

Aussi, il serait apprécié si vous pouviez mentionner le coût de chacune de vos réponses.

Je cherche Je ne suis pas sûr de ce que vous entendez par un autre, mais efficace façon de le faire

Merci à l'avance

Answer 1

Si vous appelez RemoveAt pour chaque élément que vous retirez, vous allez déplacer beaucoup de données. Le plus efficace est de déplacer les éléments ensemble que vous souhaitez conserver, puis supprimer les éléments non utilisés à la fin:

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

Edit:
Cette méthode traitera une liste d'un million ints en 15 ms. En utilisant RemoveAt il faudra plus de trois minutes ...

Edit2:
Vous pouvez réellement commencer par pos = 1 et i = 2 (ou 3), le premier élément ne doit pas être copié sur lui-même. Cela rend le code un peu moins évident.

Answer 2

si vous voulez dire « tous les autres éléments » le code suivant: marchera. Il va commencer par enlever le 2ème élément, puis le 4, et ainsi de suite

List<T> list = GetTheList(); 
int i = 1; 
while (i < list.Count) { 
    list.RemoveAt(i); 
    i++; 
} 

Answer 3

Juste pour l'examen d'une solution qui crée une nouvelle liste, une liste ancienne vous pouvez le faire:

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

ou, évidemment

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

selon laquelle l'alternance de votre choix.

EDIT

La réponse est un peu plus rapide. Si vous lisez quelque chose d'autre ici, c'est parce que j'ai mesuré un week-end et le cerveau du week-end est drôle. :( La solution de fermeture est environ 40% plus rapide tandis que la réponse est environ 2 ordres de grandeur plus rapide.Je suppose que cela dépendra de la taille de votre liste!

Answer 4

Et une autre option, similaire à celle de Frank, mais avec l'utilisation des fermetures. Et il est plus rapide que la version de Frank.

bool isEven = true;    
var newList = list.Where(x => isEven = !isEven).ToList(); 

Answer 5

for (int i=myList.length-1; i >= 0; i--) 
    if (i % 2 == 0) 
    myList.Remove(myList[i]); 

Answer 6

Je voudrais utiliser le modèle standard utilisé généralement pour les conteneurs STL. Faites un remove suivi d'un effacement.

de cette façon, vous Ne sera pas t confondre les gens habitués à voir ce modèle.

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()); 

} 

Answer 7

utilisation dépend évidemment, mais vous pourriez avoir un wrapper IList qui multiplie l'indice que vous lui donnez de 2, et les rapports de la longueur de la liste pour être 1/2 (détails) élidés. C'est O (1).

Answer 8

Le chemin vers Nirvana est pavé avec une exécution différée. Ou quelque chose.

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);     
     } 
    } 

Cela fonctionne pour toutes les séquences, pas seulement IList<>. Le coût de l'itération est différé jusqu'à l'itération, ce qui peut être une grande victoire si, à la fin, vous n'avez pas besoin de toucher tous les éléments de la liste.

Dans mes tests simples, les performances lorsque vous parcourez toute la liste ne sont pas très bonnes, alors assurez-vous de profiler votre situation réelle.