Dernière occurence dans un ArrayList.

**ctxnop** · 19/08/2010, 15h15

Ce que tu cites c'est du Linq, comme je le disais plus haut je doute que ca soit aussi efficace qu'un for/while.
Je ne conteste pas la puissance de Linq, ca reste une pure merveille. Mais est-ce adapté dans son cas ?
Il dit vouloir le plus efficace possible.
Le coût de la méthode for/while est O(n), quel est celui de la recherche par Linq ? La documentation ne le précise pas.

Rien n'indique non plus qu'il puisse taper du Linq, les développements en .Net 2.0 sont encore très très nombreux.

EDIT: Cette réponse concerne le post de jonathan3357
Concernant celle de B.AF :
J'ai loupé un épisode, tu parles de quelle recommandation ? C'est quoi qui est faux ?
Sinon, le code que tu as tapé pour donner le temps d'exécution ne donne pas pour autant la complexité de l'opération. Surtout que le test est complètement biaisé puisque un élément sur deux correspond à la condition de recherche et donc il y a maximum deux passage dans la boucle d'itération, qu'il y ai 2 éléments ou 300 milliards.
J'aimerai plutôt connaitre la comparaison asymptotique. La complexité si tu préfère.
C'est une opération O(n) aussi ? Mieux ? moins bien ? La documentation de Linq sur la méthode Last notamment ne l'indique pas... C'est peut-être plus efficace, mais sans la complexité on ne peut pas vraiment en juger.
Le fait est qu'il ne précise pas que sa liste doit être triée ou non, donc je considère qu'elle ne l'est pas et n'a pas de raison de l'être. Mais comme je l'ai également dis, s'il peut changer son ArrayList pour une liste typé ca ne sera que mieux. Ca évite les Boxing/unboxing et allège la syntaxe.

**jonathan3357** · 19/08/2010, 15h28

Pour tester la différence de perf :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 
System.Collections.ArrayList laListe = new System.Collections.ArrayList();
            for (int i = 0; i < 100000; i++)
                if (i % 2 == 0)
                    laListe.Add(new { Flag = (i%3==0 ? 1 : 0), Test = 45, Id = i });
                else
                    laListe.Add(new { Flag = (i % 3 == 0 ? 1 : 0), Id = i, AutreVar=45, t2 = "Encore un test" });
 
 
            Object[] lstObj = laListe.ToArray();
            List<dynamic> lstList = lstObj.ToList<dynamic>();
 
            for (int i2 = 0; i2 < 10; i2++)
            {
                int lastFlag = -1;
 
                Stopwatch sw1 = new Stopwatch();
                sw1.Start();
                for (int i = 0; i < lstObj.Count(); i++)
                    if ((lstObj[i] as dynamic).Flag == 1)
                        lastFlag = i;
                sw1.Stop();
                //Console.WriteLine("Dernier élément avec Flag = 1 : " + lstObj[lastFlag].ToString());
                Console.WriteLine("[Array]Temps de recherche : " + sw1.ElapsedMilliseconds);
 
 
 
                Stopwatch sw2 = new Stopwatch();
                sw2.Start();
                dynamic elt2 = lstList.Last(d => d.Flag == 1);
                sw2.Stop();
                Console.WriteLine("[List]Temps de recherche : " + sw2.ElapsedMilliseconds);
            }

Résultat :

[Array]Temps de recherche : 94
[List]Temps de recherche : 31
[Array]Temps de recherche : 51
[List]Temps de recherche : 18
[Array]Temps de recherche : 49
[List]Temps de recherche : 18
[Array]Temps de recherche : 50
[List]Temps de recherche : 17
[Array]Temps de recherche : 49
[List]Temps de recherche : 18
[Array]Temps de recherche : 51
[List]Temps de recherche : 18
[Array]Temps de recherche : 50
[List]Temps de recherche : 19
[Array]Temps de recherche : 50
[List]Temps de recherche : 19
[Array]Temps de recherche : 50
[List]Temps de recherche : 18
[Array]Temps de recherche : 50
[List]Temps de recherche : 18

Je pense que la différence n'est pâs négligeable, sans compter que l'implémentation est bien plus facile

**cinemania** · 19/08/2010, 15h29

effectivement si ton critère est la performance, une collection typée est préconisée, car tu va alors implanter toi même pendant la recherche la logique d'égalité des éléments, plutôt que d'appeler soit un membre qu'on est sure de trouver comme Equals ou de faire appel à un delegate.

les generics ont l'avantage de facilité le code, mais pas forcément de générer le code le plus performant... tout dépend de l'usage qui est fait, c'est toujours pareil.

quand à l'utilisation de Linq, elle a des avantages et inconvénients.
Quand à savoir si un Last s'exécute en partant de la fin où s'il scan tous les éléments un par un, avant de retourner le dernier élément, je me garderais bien de me prononcer, car même en Linq to Object, cela dépend du provider.

de manière générale, de toute façon dès lors que tu effectue une recherche sur une liste, qui nécessite une itération, il faut faire une synchronisation au moment d'entrer dans le process de recherche, et non à chaque opération atomique de recherche.
c'est également vrai avec une recherche avec un for/while, car si on vient altérer la liste ou le tableau pendant que tu est en train de le scanner, rien ne dit que le dernier élément réel, ne va pas être ajouté/inseré dans la liste a un index supérieur, après que tu soit descendu dans des index inférieurs. Dans ce cas, à l'instant t où tu renvoie ton résultat il est "faux".

note : dans une liste non triée, la recherche est au mieux en O(n).
dans une liste triée, une recherche dichotomique peut réduire pas mal la complexité, et dans une skiplist, la recherche se fera en O(log n), malheureusement à ma connaissance il n'existe pas d'implantation de la skiplist dans aucun des framework actuels... pourtant cette structure de données à déjà 10 ans... il serait temps...

**ctxnop** · 19/08/2010, 15h35

Envoyé par jonathan3357

Pour tester la différence de perf

Toi aussi ton test est faux

Même remarque que pour celui de B.AF les éléments de ta liste son ordonnés :
{ VRAI, FAUX, VRAI, FAUX, ....}
Donc que l'on recherche du début ou de la fin, un élément vrai ou un élément faux, il n'y a que deux passage dans la boucle.

De plus, tu compare la recherche [Linq sur liste typé forte] avec la recherche [itération sur tableau d'objet]
Or depuis le début on dit que les liste typé forte sont plus performantes du fait notamment qu'il n'y a pas d'opération de Boxing/Unboxing connues pour être très couteuse en performance.

**ctxnop** · 19/08/2010, 15h42

Envoyé par cinemania

note : dans une liste non triée, la recherche est au mieux en O(n).
dans une liste triée, une recherche dichotomique peut réduire pas mal la complexité, et dans une skiplist, la recherche se fera en O(log n), malheureusement à ma connaissance il n'existe pas d'implantation de la skiplist dans aucun des framework actuels... pourtant cette structure de données à déjà 10 ans... il serait temps...

Merci de la précision, je me demandais si y'avait pas un moyen d'obtenir une recherche en O(log(n)) sur une liste non triée, j'ai maintenant ma réponse (même si je suis pas contre une source :p)

**B.AF** · 19/08/2010, 15h48

Envoyé par ctxnop

Ce que tu cites c'est du Linq, comme je le disais plus haut je doute que ca soit aussi efficace qu'un for/while.
Je ne conteste pas la puissance de Linq, ca reste une pure merveille. Mais est-ce adapté dans son cas ?
Il dit vouloir le plus efficace possible.
Le coût de la méthode for/while est O(n), quel est celui de la recherche par Linq ? La documentation ne le précise pas.

Rien n'indique non plus qu'il puisse taper du Linq, les développements en .Net 2.0 sont encore très très nombreux.

Fais les deux.

Dans son cas, de toutes les façons, le array list et l'itération vont demander :
- Un Cast
- Un risque sur le fait que l'élément soit vraiment le dernier

Ce à quoi il faudrait vraiment utiliser une Queue<T> qui elle va garantir une pile fifo cohérente.

Quant au for while, chez moi, ça prend 3ms en linq ou avec un for qui utilise une indexation inverse (partir du dernier).

A partir du moment ou tu mets le dernier en position aléatoire, le linq devient plus performant (vu que l'itération est elle plus ou moins longue) car linéaire, donc prédictible.

Quoi qu'il en soit on peut rendre l'ordre aléatoire :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
 
 class Program
    {
 
        public class A
        {
            public bool Prop1
            {
                get; set;
            }
            public string Prop2
            {
                get; set;
            }
 
            public static A[] GetThousands()
            {
                var x = new A[100000];
                for (int i = 0; i < 100000; i++)
                {
                    Random r=new Random();
                    x[i] = r.NextDouble() * 100<5? new A() { Prop1 = true, Prop2 = "Whatever" } :
                         new A() {Prop1 = false, Prop2 = "And ever"};
 
                }
                return x;
            }
 
        }
 
 
 
 
        static void Main(string[] args)
        {
            var a1  = A.GetThousands();
 
 
            List<A> al1=new List<A>(a1);
            var d1 = DateTime.Now;
            var o1 = al1.Last(x => x.Prop1);
            var d2 = DateTime.Now;
            Console.WriteLine(d2.Subtract(d1).Milliseconds);
 
 
            Queue<A> aq1 = new Queue<A>(a1);
            d1 = DateTime.Now;
            var o2 = aq1.Last(x => x.Prop1);
            d2 = DateTime.Now;
            Console.WriteLine(d2.Subtract(d1).Milliseconds);
            Console.Read();
 
        }
    }

Et là je reste dans le 3ms.

**Sehnsucht** · 19/08/2010, 15h53

Bonjour,

Voilà le code source (via Reflector) de la méthode Last (sans paramètre):

Code C# :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 
public static TSource Last<TSource>(this IEnumerable<TSource> source)
{
    if (source == null)
    {
        throw Error.ArgumentNull("source");
    }
    IList<TSource> list = source as IList<TSource>;
    if (list != null)
    {
        int count = list.Count;
        if (count > 0)
        {
            return list[count - 1];
        }
    }
    else
    {
        using (IEnumerator<TSource> enumerator = source.GetEnumerator())
        {
            if (enumerator.MoveNext())
            {
                TSource current;
                do
                {
                    current = enumerator.Current;
                }
                while (enumerator.MoveNext());
                return current;
            }
        }
    }
    throw Error.NoElements();
}

De ce que j'en comprend (moi et la compléxité... enfin c'est complexe quoi

) si le type sous-jacent de la source implémente IList la recherche ce fait en temps constant O(1) par contre ça devient O(n) dans le cas contraire en nécessitant le passage par l'énumérateur/itérateur.

Je ne sais pas si ça va vraiment aider, par contre

et j'espère ne pas avoir dit de boulette sur les histoires de compléxité.

**B.AF** · 19/08/2010, 15h58

Envoyé par ctxnop

Toi aussi ton test est faux

Même remarque que pour celui de B.AF les éléments de ta liste son ordonnés :
{ VRAI, FAUX, VRAI, FAUX, ....}
Donc que l'on recherche du début ou de la fin, un élément vrai ou un élément faux, il n'y a que deux passage dans la boucle.

De plus, tu compare la recherche [Linq sur liste typé forte] avec la recherche [itération sur tableau d'objet]
Or depuis le début on dit que les liste typé forte sont plus performantes du fait notamment qu'il n'y a pas d'opération de Boxing/Unboxing connues pour être très couteuse en performance.

Je suis d'accord, j'ai randomisé les itérations, mais au début c'était uniquement pour la performance versus la taille de la collection, pas sur le tri.

Le boxing/unboxing est nécessairement là puisque sa règle de filtre se base sur une propriété de l'objet, donc il est nécessaire à chaque fois de faire

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
if (((SonType)tableau[i]).SaProp)
{
(...)
}

si tu veux utiliser une boucle. Donc le coup de boxing / unboxing est bien là.

Pour l'ordre dans la List<T< :

Envoyé par MSDN

On average, this method is an O(n log n) operation, where n is Count; in the worst case it is an O(n ^ 2) operation.

--> Quicksort

**jonathan3357** · 19/08/2010, 16h01

Envoyé par B.AF

Fais les deux.

Dans son cas, de toutes les façons, le array list et l'itération vont demander :
- Un Cast
- Un risque sur le fait que l'élément soit vraiment le dernier

Ce à quoi il faudrait vraiment utiliser une Queue<T> qui elle va garantir une pile fifo cohérente.

Quant au for while, chez moi, ça prend 3ms en linq ou avec un for qui utilise une indexation inverse (partir du dernier).

A partir du moment ou tu mets le dernier en position aléatoire, le linq devient plus performant (vu que l'itération est elle plus ou moins longue) car linéaire, donc prédictible.

Quoi qu'il en soit on peut rendre l'ordre aléatoire :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
 
 class Program
    {
 
        public class A
        {
            public bool Prop1
            {
                get; set;
            }
            public string Prop2
            {
                get; set;
            }
 
            public static A[] GetThousands()
            {
                var x = new A[100000];
                for (int i = 0; i < 100000; i++)
                {
                    Random r=new Random();
                    x[i] = r.NextDouble() * 100<5? new A() { Prop1 = true, Prop2 = "Whatever" } :
                         new A() {Prop1 = false, Prop2 = "And ever"};
 
                }
                return x;
            }
 
        }
 
 
 
 
        static void Main(string[] args)
        {
            var a1  = A.GetThousands();
 
 
            List<A> al1=new List<A>(a1);
            var d1 = DateTime.Now;
            var o1 = al1.Last(x => x.Prop1);
            var d2 = DateTime.Now;
            Console.WriteLine(d2.Subtract(d1).Milliseconds);
 
 
            Queue<A> aq1 = new Queue<A>(a1);
            d1 = DateTime.Now;
            var o2 = aq1.Last(x => x.Prop1);
            d2 = DateTime.Now;
            Console.WriteLine(d2.Subtract(d1).Milliseconds);
            Console.Read();
 
        }
    }

Et là je reste dans le 3ms.

N'utilise pas DateTime, c'est pas précis du tout ... avec datetime, il me met aussi 3ms pour un traitement de 1 000 000 000 d'objets qui me prenait bien une 10ene de minutes. L'objet Stopwatch est plus précis, mais je crois qu'il y en a encore plus précis que ça, mais le je connais pas.

**ctxnop** · 19/08/2010, 16h15

C'est pas con ca le passage par reflector pour le code source.
Par contre ce n'est pas la bonne méthode

Celle-ci retourne le dernier élément de la liste, c'est tout. Cette opération est toujours à temps constant.
Il faut prendre la méthode Last qui prend une recherche en paramètre.

Le code se comprend tout à fait en lisant simplement la documentation.
ce qui implémente IList est normalement (je dis bien normalement car IList est une interface et rien n'empêche qui que ce soit d'implémenter une IList sans pour autant respecter cette règle) préalloué a la manière d'un tableau. Quand il n'y a plus de place on réalloue le tableau pour en refaire.
En conséquence on a à tout moment tous les éléments qui se suivent en mémoire et donc on peut les indexer sans recherche.
Alors que si ca implémente uniquement IEnumerable ce sont des éléments énumérables mais pas forcément regroupés en mémoire (liste-chainées). En conséquence on doit passer d'un élément à un autre pour atteindre un élément précis (ce qui correspond à une opération O(n)). Et vu qu'en .Net les énumérateurs semblent ne pas pouvoir parcourir la liste dans le sens inverse, les deux méthode deviennent extrêmement inefficace s'il s'agit un IEnumerable mais pas IList.

(Puisque Linq utilisera un énumérateur pour parcourir la liste complète, et que MonEnumerable[i] parcourt également la liste complète pour atteindre l'élément)

Si on veux comparer l'efficacité de Linq il ne faut pas le faire face à un ArrayList. Pour le moment on ne sait toujours pas (l'auteur ne s'étant pas manifesté, on a du lui faire peur avec nos formules de complexité

) si il peut ou non changer de type. S'il peut changer de type alors on peut comparer Linq à IList<T>, mais c'est tout. Et vu ce que je vois du code de Linq les deux sont équivalents. La différence se jouera sur le temps perdu via l'appel d'une fonction ce qui est totalement négligeable.

**B.AF** · 19/08/2010, 16h53

Envoyé par ctxnop

Si on veux comparer l'efficacité de Linq il ne faut pas le faire face à un ArrayList. Pour le moment on ne sait toujours pas (l'auteur ne s'étant pas manifesté, on a du lui faire peur avec nos formules de complexité

) si il peut ou non changer de type. S'il peut changer de type alors on peut comparer Linq à IList<T>, mais c'est tout. Et vu ce que je vois du code de Linq les deux sont équivalents. La différence se jouera sur le temps perdu via l'appel d'une fonction ce qui est totalement négligeable.

C'est vrai qu'on boucle dans le vide. Jamais les collections n'auront semblé si complexe !!!!

Pour la précision Datetime, ok, j'ai fait acte de fainéantise ! (stopwatch me donne les mêmes résultats).

De toutes les façons concernant Linq, il faut aussi considérer l'élément de comparaison utilisé. Sachant qu'à priori, Linq utilise dans les exemples donnés une itération for basé sur les indexes et que les clauses where sur l'objet utilise un if sans recréer d'itérateur.
A partir du moment ou il y a IList et pas de prédicat par ex. ; il prend de facto le count-1.

J'aurai tendance à dire que sur un objet trivial (2 propriétés) et sur une collection de faible taille, le rapport est nul.

Sur des objets plus complexes où il sera possible de filtrer ou d'aggréger pour extraire un set d'arrivé, je pense que Linq reste préférable pour la lisibilité quite à concéder un peu de performance. (Forcémment, en passant par Linq il y aura toujours l'aspect Framework qui viendra effectivement ponctionner de la performance)

Là encore, j'aurai tendance à préférer un code clair et surtout une performance linéaire qu'un algorithme spécifique de tri.
Globalement, je pense qu'il vaut mieux en 3.5 et en 4.0 utiliser des implémentations de IComparer pour optimiser les sort le cas échéant que d'itérer des collections. Après, je comprends aussi qu'en étant plus "close to the metal" se soit le meilleur moyen d'être performant. C'est un choix d'archi, en connaissance de cause. Donc, je sais bien que je "n'ai pas raison".

Sinon messieurs, soyons honnête :
Nous avons complêtement déliré et sommes sorti du sujet.
Cependant, je dois dire que j'ai pris pas mal de plaisir à vous lire.

**ctxnop** · 19/08/2010, 17h02

Je suis plutôt d'accord avec ta conclusion, je préfère aussi un code propre et quand on doit chercher la performance on a pas toujours le choix.
Et oui aussi, on est sorti de la question

Mais c'est toujours un peu amusant et ca enseigne de choses, alors tant pis.

**cinemania** · 19/08/2010, 17h07

le problème des listes et de la complexité de recherches dans celles ci ne date pas d'hier, c'est un problème aussi vieux que l'informatique et que les structures de données.

la complexité et calculabilité sont cependant des domaines assez peu étudiés et répandus, aussi il y a fort à parier qu'on l'ai un peu noyé

**B.AF** · 19/08/2010, 17h18

Envoyé par cinemania

la complexité et calculabilité sont cependant des domaines assez peu étudiés et répandus, aussi il y a fort à parier qu'on l'ai un peu noyé

Oui ou aider : il est parti avec une pierre en direction du premier pont !

Ca me fait penser au sketch de Coluche :

c'est les mecs que, quand tu leur poses une question, une fois qu'ils ont fini de répondre, tu comprends plus la question que t'as posée !

**ctxnop** · 19/08/2010, 17h21

Tout à fait ca

Vous pensez qu'il faut appeler les secours avant qu'il succombe à la noyade ?
Oh et puis zut d'abord, comme tu viens de le dire cinemania, le problème de la complexité est très vieux, on y est tous confronté un jour ou l'autre de manière plus ou moins frontale, ca lui fera une introduction en la matière ^^'

**B.AF** · 19/08/2010, 17h41

Envoyé par ctxnop

le problème de la complexité est très vieux, on y est tous confronté un jour ou l'autre de manière plus ou moins frontale, ca lui fera une introduction en la matière ^^'

Ou un traumatisme à vie aussi...

**ctxnop** · 19/08/2010, 17h55

Bah si c'est le cas on a plus qu'a l'achever et cacher le corps sous le tapis

**B.AF** · 19/08/2010, 21h02

**Ed.11** · 20/08/2010, 09h27

Ne vous inquiétez pas, j'ai commencé par voir la complexité en prépa et ça ne s'est pas arrangé en école d'ingé... (buh les parcours/ajouts/tris d'arbre >.<). . c'est très intéressant comme sujet =)

Par contre il s'avère que je n'avais jamais fait de C# avant mon stage. Celui-ci durant 10 semaines, j'ai pas eu de temps pour voir les bases (surtout les timers et la programmation multi-threadée...).

J'ai apris l'existence des listes "presonnalisées" y'a environ une semaine je n'en ai plus qu'une avant d'avoir finit. Sachant que j'ai aussi mon rapport à ça m'embêterait beaucoup de devoir refaire toute la structure du programme :/

Je ne sais pas si ça change quelque-chose, mais pour récupérer l'état d'un atrtribut, je ne fais pas Objet.attribut mais objet.méthode-qui-récupère-l'attribut().

L'objet contient effectivement 2 attributs, mais la liste peut être longue (un élément toutes les 10 secondes). Je ne sais pas à quel point le Garbage Collector est performant. Cette liste est accessible depuis plusieurs threads:
- un thread qui ajoute les éléments toutes les 10 secondes.
- un thread qui à chaque réception d'un message change le flag de l'élément correspondant dans la liste.
- un autre qui toutes les 30 secondes regarde quel est le dernier élément ayant un flag à false, et le dernier élément reçu. Après je fais un calcul de délai (je passe) et je l'enregistre dans un fichier et l'envoi sous forme d'un autre message sur le réseau.

N'empêche, ça a l'air tellement plus facile avec List<A> ou Queue<A> =_=

(et petite précision, je suis une fille :p)

**ctxnop** · 20/08/2010, 09h36

Envoyé par Ed.11

N'empêche, ça a l'air tellement plus facile avec List<A> ou Queue<A> =_=
(et petite précision, je suis une fille :p)

Nan pas possible, tu ments juste pour avoir plus d'aide, tout le monde sait que les filles dans l'informatique ce n'est qu'une légende urbaine

Plus sérieusement, si tu as le contrôle totale du projet, changer ton ArrayList par une List<T> ou une Queue<T> se fera en 5 minutes via les outils de refactorisation intégrés et quelques compilation. Ces objets sont très très proche du ArrayList, mais sont typé plus fortement ce qui les rend plus performants et simple a manipuler.

Faire des méthodes pour récupérer un membre d'une classe (en .Net on parle plus de membre que d'attribut, ce dernier mot signifie autre chose en .Net) n'a pas grande importante. Une propriété étant transformée à la compilation en une ou deux méthode (get/set). C'est surtout une question de standard d'écriture.

Dernière occurence dans un ArrayList.

C#

Discussions similaires

Partager

Partager