Bienvenue à Blogs CodeS-SourceS Identification | Inscription | Aide

Un tri pour IEnumerable<T>

Tout le monde utilise régulièrement la méthode Sort des Lists, ou encore celle des tableaux (Array.Sort). Mais pour une collection très générale, qui n'implémenterait que IEnumerable, il n'existe rien de pratique (je ne parle pas de C# 3.0 bien sur).

Voici un petit tri qui fonctionne avec n'importe quelle collection pourvu qu'elle soit IEnumerable. Cette fonction n'instancie aucune collection, il faudrait utiliser des collections pour atteindre une complexité en O(n * log(n)), ce qui reviendrait à peu de choses près à convertir le IEnumerable en tableau et à trier le tableau.

En tout cas, à défaut d'être efficace, ce code montre une des nombreuses utilisations que l'on peut faire du mot clé yield return. Voici le code :

public static class EnumerableSort
{
    public static IEnumerable<T> Sort<T>(IEnumerable<T> toSort, Comparison
<T> comparer)
    {
        IEnumerator
<T> enumerator = toSort.GetEnumerator();
        if
(!enumerator.MoveNext())
            yield break
;

        // Le pivot est enumerator.Current
        foreach (T item in Sort(EnumerateBefore(toSort, comparer, enumerator.Current), comparer))
            yield return
item;

        yield
return enumerator.Current;

        foreach
(T item in Sort(EnumerateAfter(toSort, comparer, enumerator.Current), comparer))
            yield return
item; 
    }

    private static IEnumerable<T> EnumerateBefore<T>(IEnumerable<T> toSort, Comparison
<T> comparer, T limit)
    {
        foreach (T item in
toSort)
            if
(comparer(item, limit) < 0)
                yield return
item;
    }

    private static IEnumerable<T> EnumerateAfter<T>(IEnumerable<T> toSort, Comparison
<T> comparer, T limit)
    {
        foreach (T item in
toSort)
            if
(comparer(item, limit) > 0)
                yield return
item;
    }
}

Attention : cette fonction risque d'oublier des éléments si vous avez plusieurs éléments identiques (mais il faut de toutes petites modifications pour que cela marche). Vous pourrez quand même noter que pour que cela fonctionne, il faut également que la collection s'énumère toujours dans le même ordre.

Il est très facile de transformer cette fonction en extension method de C# 3.0 :

    public static IEnumerable<T> Sort<T>(this IEnumerable<T> toSort, Comparison<T> comparer)

En C# 3.0, vous aurez cependant accès à la méthode d'extension OrderBy qui fait quasiment la même chose.

Publié mardi 3 avril 2007 10:49 par RaptorXP
Classé sous : , ,
Ce post vous a plu ? Ajoutez le dans vos favoris pour ne pas perdre de temps à le retrouver le jour où vous en aurez besoin :

Commentaires

# un quicksort un peu "slow"

A vue de nez, cette implémentation est au moins quadratique en terme de complexité ;)

Pour obtenir un temps O(n log n), il faudrait effectuer des copies des sous-collections et ne pas s'en tenir à des collections paresseuses.

En règle générale, il faut faire gaffe quand on définit des énumérables en termes d'autres énumérables. On peut se retrouver à manipuler beaucoup plus d'éléments qu'on ne croit en raison des énumérations intermédiaires.

mardi 3 avril 2007 14:13 by gkevorkian

# re: Un tri pour IEnumerable<T>

Effectivement, après reflection, la complexité est plutôt quadratique.

Du coup il existe des implémentations plus simples qui ont la même complexité et qui n'instancient pas de collections non plus.

mardi 3 avril 2007 15:02 by RaptorXP

# re: Un tri pour IEnumerable<T>

Pourquoi ne pas directement utiliser une List

<T> qui a déjà la méthode "Sort" prenant en paramètre un IComparer<T>??

mardi 3 avril 2007 15:40 by ZeBobo5

# re: Un tri pour IEnumerable<T>

J'essaye justement de fournir une méthode générale qui fonctionne avec d'autres collections que des List

<T> et des tableaux. Après, c'est sur qu'il serait plus performant et même plus rapide à coder de copier le IEnumerable dans une liste ou un tableau et de de le trier avec Sort (mais c'était pour changer un peu ^^).

Pour gkevorkian : en fait la complexité est n*log(n)^2 ce qui est un peu mieux que n^2

mardi 3 avril 2007 15:58 by RaptorXP

# re: Un tri pour IEnumerable<T>

RaptorXP, ça fait un bout de temps que j'ai quitté l'université et l'analyse d'algo c'est un peu lointain :) mais là j'ai quelques doutes. S'il s'agissait d'une simple énumération récursive sur un arbre binaire, vous auriez raison, je pense (chaque noeud faisant un yield pour tous les noeuds du sous-arbre dont il est racine, ce qui est le cas de la méthode Sort), mais ici il faut aussi prendre en compte le travail effectué par les méthodes EnumerateBefore() et EnumerateAfter().

n*log(n)^2 sur une liste en accès séquentiel, ça me paraît trop beau pour être vrai :)

PS: Je signale au passage cet article intéressant sur les itérateurs:

http://blogs.msdn.com/wesdyer/archive/2007/03/23/all-about-iterators.aspx

mardi 3 avril 2007 18:23 by gkevorkian
Les commentaires anonymes sont désactivés

Les 10 derniers blogs postés

- Merci par Blog de Jérémy Jeanson le 10-01-2019, 20:47

- Office 365: Script PowerShell pour auditer l’usage des Office Groups de votre tenant par Blog Technique de Romelard Fabrice le 04-26-2019, 11:02

- Office 365: Script PowerShell pour auditer l’usage de Microsoft Teams de votre tenant par Blog Technique de Romelard Fabrice le 04-26-2019, 10:39

- Office 365: Script PowerShell pour auditer l’usage de OneDrive for Business de votre tenant par Blog Technique de Romelard Fabrice le 04-25-2019, 15:13

- Office 365: Script PowerShell pour auditer l’usage de SharePoint Online de votre tenant par Blog Technique de Romelard Fabrice le 02-27-2019, 13:39

- Office 365: Script PowerShell pour auditer l’usage d’Exchange Online de votre tenant par Blog Technique de Romelard Fabrice le 02-25-2019, 15:07

- Office 365: Script PowerShell pour auditer le contenu de son Office 365 Stream Portal par Blog Technique de Romelard Fabrice le 02-21-2019, 17:56

- Office 365: Script PowerShell pour auditer le contenu de son Office 365 Video Portal par Blog Technique de Romelard Fabrice le 02-18-2019, 18:56

- Office 365: Script PowerShell pour extraire les Audit Log basés sur des filtres fournis par Blog Technique de Romelard Fabrice le 01-28-2019, 16:13

- SharePoint Online: Script PowerShell pour désactiver l’Option IRM des sites SPO non autorisés par Blog Technique de Romelard Fabrice le 12-14-2018, 13:01