Ce matin, en lisant le code d’un collègue, je suis tombé sur les lignes suivantes :

public static class ListExtension
{
        public static bool RemoveByReversingLast<T>(this List<T> list, T item)
        {
            int idx = list.IndexOf(item);
            if (idx == -1)
                return false;

            list[idx] = list[list.Count - 1];
            list.RemoveAt(list.Count - 1);

            return true;
        }
}

Le but de cette méthode était d’accélérer les performances de la suppression d’élément dans une liste générique lorsque l’on n’a pas besoin de conserver l’ordre de celle-ci.

En effet, en affectant le dernier élément de la liste à la position de l’élément que l’on souhaite supprimer, puis en supprimant le dernier élément de la liste, on évite la reconstruction de la fin de la liste, qui peut être coûteuse.

Néanmoins, j’ai trouvé que ce code avait quelques inconvénients :

Premièrement, il s’agit d’étendre la classe List<T>. Ce qui signifie qu’un contributeur ne remarquant pas la méthode utilisée ici peut être tenté d’utiliser la liste comme une liste classique, sans avoir conscience que cette dernière n’est plus ordonnée.

Quitte à créer une liste non ordonnée, autant réaliser une nouvelle classe ne laissant aucun doute sur son utilisation.

Le deuxième point est de savoir si cette méthode représente effectivement une plus-value significative lors de la suppression.

Pour se faire, j’ai rapidement créé une classe de liste non ordonnée de test surchargeant sa méthode Remove, et une classe de test.

Ci dessous la classe UnorderedList utilisée pour mes tests (ainsi que le test complet ici : UnOrderedListTester.cs ) :

public class UnorderedList<T> : List<T>
{
        public UnorderedList() : base()
        {

        }

        public UnorderedList(int capacity) : base(capacity)
        {

        }

        public UnorderedList(IEnumerable<T> collection)
            : base(collection)
        {

        }

        public new bool Remove(T item)
        {

            int idx = IndexOf(item);
            int last = Count - 1;
            if (idx == -1)
                return false;

            if (idx != last)
                this[idx] = this[last];

            RemoveAt(last);
            return true;

        }
}

Il ne s’agit ici que d’une classe de test et non d’une vraie liste non ordonnée, ne serait-ce que de part l’existence de l’accesseur this[intindex].

Le but étant de benchmarker les performances en suppression, celle ci me semble suffisante.

J’ai fait le choix de toujours supprimer l’élément central de la liste lors de mes tests, de manière à obtenir un résultat pas trop éloigné de celui rencontré lors d’une utilisation standard.

(En effet, toujours supprimer un des premiers éléments semblerait trop avantageux pour la liste non ordonnée , tandis que l’inverse le serait pour la liste classique).

J’ai découpé mon test en 3 parties : De petites listes de 10 éléments, des listes moyennes de 500 éléments, et de grandes listes d’un million d’éléments.

Après avoir lancé plusieurs jeux de test, les résultats sont relativement similaires :

Sur des petites listes, on obtient un gain de performances de l’ordre de 15 à 20%. Ceci dit, les temps de traitements sont tellement courts (1ms pour 20.000 suppressions) qu’à part dans des cas extrêmement spécifiques, cette optimisation est inutile. Pour les listes de taille moyenne, on note un gain de l’ordre de 25%.

Le temps de traitement est 10 fois plus lent (1ms pour 2.000 suppressions) que pour les listes courtes, ceci dit je doute également de l’utilité de cette optimisation dans la majorité des cas.

Finalement, sur des très grosses listes, on obtient un gain d’environ 50% du temps de traitement, et encore, n’ayant pas lancé le test sur un très grand nombre de listes, il est possible que les performances soient bien meilleures.

La suppression étant particulièrement lourde dans ces cas, une optimisation telle que celle-ci devient alors fort utile.

Bilan

Il est parfois possible d’optimiser une action réalisée par une classe du framework .net. Néanmoins, avant de réaliser cette optimisation, on devrait se poser deux questions :

• L’optimisation que je veux réaliser est-elle réellement utile dans mon contexte ?
• L’optimisation que je veux réaliser ne risque-t-elle pas de créer des effets de bord indésirables, ou d’induire en erreur des futurs collaborateurs sur le projet ?

Dans le cas présent, le volume de traitements à effectuer ne nécessitait pas d’optimisation. De plus, cette dernière aurait pu m’induire en erreur sur la nature des objets utilisés (d’autant plus qu’il s’agissait ici d’une méthode d’extension, donc “cachée” dans le code)

Il est toujours tentant pour un développeur de créer, d’optimiser et d‘implémenter des algorithmes, c’est même pour certains (moi le premier) la partie la plus intéressante de ce métier.

Cependant, il faut toujours veiller à ne pas laisser déborder cette “créativité” là où elle pourrait nuire.