Insertion fréquente dans la collection triée

Question

J'ai trié la collection (Liste) et je dois la garder triée en tout temps. J'utilise actuellement List.BinarySearch sur ma collection, puis j'insère l'élément au bon endroit. J'ai également essayé de trier la liste après chaque insertion mais la performance est inacceptable.

Y at-il une solution qui donnera de meilleures performances? Peut-être que je devrais utiliser d'autres collections.

(je suis au courant de SortedList mais il est limité à des touches uniques)

Answer 1

PowerCollections a un type OrderedBag qui peut être bon pour ce que vous avez besoin. De la documentation

Insertion, suppression, et levant les yeux un un élément sont tous fait dans log (N) + M temps, où N est le nombre de clés dans l'arbre, et M est le numéro actuel des copies de l'élément étant traitées.

Cependant, pour le .NET 3.5 construit en types, en utilisant List.BinarySearch et l'insertion de chaque élément dans le bon endroit est un bon début - mais qui utilise un tableau interne si votre performance vous baissera à cause de toute la copie » refaire quand vous insérez.

Si vous pouvez regrouper vos insertions dans des lots qui amélioreront les choses, mais à moins que vous ne puissiez descendre à une seule opération de tri après tout votre insertion, vous êtes probablement mieux d'utiliser OrderedBag de PowerCollections si vous le pouvez.

Answer 2

Essayez d'insertions globales en lots, et trier seulement à la fin de chaque lot.

Answer 3

Si vous utilisez .Net 4, vous pouvez utiliser un SortedSet<T>

http://msdn.microsoft.com/en-us/library/dd412070.aspx

Pour .Net 3.5 et inférieur, si un SortedList<TKey,TValue> fonctionne pour vous.

http://msdn.microsoft.com/en-us/library/ms132319.aspx