Discussion :

[Ed.11]

Bonjour,

Je voudrais récupérer l'index de la dernière occurence d'un objet dans un e ArrayList.
J'ai vu qu'il existait une méthode LastIndexOf, mais je voulais savoir, comment avoir une recherche sur un attribut?

Je m'explique: il s'agit d'une arraylist d'objets dont j'ai créé la classe. Chacun contient un champ identifiant et un champ "flag" (booléen).
Je voudrais avoir l'index du dernier objet ayant un flag à false, et je ne peux pas prévoir à l'avance l'identifiant qu'il aura.

Merci de m'aider

[worm83]

Salut,

Tout simplement :

MonObjet[] tab est ton array :

Code :

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

1
2
3
4
5
6
7
8
int i =0;
 
while(tab[i].Flag == false)
{
 i++;
}
 
return i;

i represente la valeur de ton index.

[ctxnop]

Salut,
J'ai rien sous la main pour vérifier ce que je vais dire et donc je serai peut être à coté de la plaque mais bon...

Je dirais que tu as plusieurs choix :
- dans ton objet (contenant le flag) tu peux surcharger la méthode Equal. Si je me plante pas cette méthode est appelée lorsque tu fais ton LastIndexOf, donc si tu surcharge pour dire que c'est égal en fonction de l'attribut ca devrais fonctionner.
- Dans le même esprit il y a une interface IComparable que tu peux implémenté. Je suis moins sur que ca fonctionne, mais tu peux toujours tenter.

- Le plus simple pour moi (simple != efficace) est de faire un

Code :

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

for(i = MonArrayList.Count - 1; i >= 0; i--)

EDIT:
@worm83 : Il a dit le dernier élément de la liste, pas le premier

[meziantou]

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
object o = null;
for(i = MonArrayList.Count - 1; i >= 0; i--)
{
    if(ta condition)
    {
        o = MonArrayList[i];
        break;
    }
}
// o contient le dernier element correspondant à ta condition

Petite remarque
Pourquoi ne pas utiliser les collection générique : List<T>
Si tu utilises dotnet 3.5 il y a Linq ce qui permet d'écrire quelque chose comme

Code :

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

taList.OfType<TonType>().Last(a => ta condition);

[worm83]

L'avantage d'un simple While par rapport a ta solution meziantou c'est que je ne parcourt pas tout le tableau, j'en sort des que j'ai trouve mon objet.
Celle de ctxnop est equivalente ca dependra de la collection.

[meziantou]

L'avantage d'un simple While par rapport a ta solution meziantou c'est que je ne parcourt pas tout le tableau, j'en sort des que j'ai trouve mon objet.

C'est d'ailleur pourquoi j'ai édité mon message...

[worm83]

J'avais pas vu, désolé

[Ed.11]

Merci!

J'étais partie pour faire un foreach mais je voulais savoir s'il y avait quelque chose de performant... Car je ne connais pas l'efficacité du Garbage Collector. J'ajoute un élément à la liste toutes les x secondes, et l'appli tourne toute la journée, donc ça peut être long

Et justement: est-ce que ta solution meziantou ne posera pas de problème si j'ajoute des messages pendant l'exceution de la boucle? (je fais de la programmation multiil va falloir que je bloque la liste?)

[ctxnop]

Et justement: est-ce que ta solution meziantou ne posera pas de problème si j'ajoute des messages pendant l'exceution de la boucle? (je fais de la programmation multiil va falloir que je bloque la liste?)

La boucle (for ou while) n'est aucunement thread-safe.
Si tu ne fais qu'ajouter des élément en FIN du arraylist, ca ne posera pas de problème. Par contre, une insertion, une suppression ou une modification d'élément est problématique.
Donc pour sécuriser il te faudra synchroniser les thread/processus ayant accès à la liste. Si je me plante pas ca se fera par un lock de MonArrayList.SyncRoot.

Edit:
Ah oui, une ou deux précisions : je pense pas qu'un foreach puisse lire la liste a l'envers et n'est donc pas la bonne solution.
De plus un foreach n'autorise aucune modification de la collection (tu ne peux donc ni modifier un élément, ni en ajouter, ni en supprimer, ou même en déplacer, toute tentative provoquera une exception).

For ou While, les deux sont sensiblement identique. Pas vraiment de différence de perf à ma connaissance. C'est surtout une question d'écriture.
On utilise plus naturellement le for quand on connait à l'avance le nombre d'itération maximum que l'on va faire (typiquement le parcourt d'une collection dont le nombre d'éléments est donné par Count).
Le while est plutot utilisé quand la condition dépend d'un calcul/appel qui à lieu à chaque itération. Ex : while (MaForm.IsVisible) { /* */ }
Dans mon exemple on a aucune idée du nombre d'itération de la boucle.

[meziantou]

Aucune des collections n'est thread-safe sauf celles qui se trouvent dans l'espace de nom : System.Collections.Concurrent (nouveau dans dotnet 4).

je pense pas qu'un foreach puisse lire la liste a l'envers

foreach utilise l'énumerateur de la collection (qui lit généralement les données dans le sens "normal")

J'avais pas vu, désolé

Vu ta vitesse de réaction, je n'avais pas encore modifié ma réponse.

[B.AF]

Je voudrais récupérer l'index de la dernière occurence d'un objet dans un e ArrayList.
J'ai vu qu'il existait une méthode LastIndexOf, mais je voulais savoir, comment avoir une recherche sur un attribut?

Je m'explique: il s'agit d'une arraylist d'objets dont j'ai créé la classe. Chacun contient un champ identifiant et un champ "flag" (booléen).
Je voudrais avoir l'index du dernier objet ayant un flag à false, et je ne peux pas prévoir à l'avance l'identifiant qu'il aura.

Le mieux que tu puisse faire c'est d'utiliser un collection générique et d'utiliser Linq. Là tu utilises une collection qui n'est pas appropriée à ce que tu en fais. Donc tu vas faire des contorsions qui restent hazardeuses. Il vaut mieux revenir un plan au dessus et utiliser une collection typée

[worm83]

La tu cerne un autre problème B.AF, mais tu a raison la MSDN préconise l'utilisation de collection Génériques si l'on ne contrôle pas le nombre de données contenues dans le tableau. Qui plus est Linq To Object est magique

[B.AF]

La tu cerne un autre problème B.A.F, mais tu a raison la MSDN préconise l'utilisation de collection Génériques si l'on ne contrôle pas le nombre de données contenues dans le tableau.

Un problème de code qui découle d'un problème de conception n'est pas un problème, il sera résolu avec la résolution du problème de conception.

Déjà; l'array list, n'est pas trié. (cf entre autres les explications de ctxnop)
Ce qui veut dire qu'il faut itérer. Or précisemment, itérer c'est ce qui consomme du temps sur des collections importantes.

Quant à la recommandation c'est faux, depuis le 2.0 Microsoft préconise le recours aux listes typées pour la performance.

create strongly typed collections that provide better type safety and performance than non-generic strongly typed collections.

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
 
    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++)
                {
 
                    x[i] = i%2 == 0 ? new A() {Prop1 = true, Prop2 = "Whatever"}:
                         new A() {Prop1 = false, Prop2 = "And ever"};
 
                }
                return x;
            }            
        }
 
 
 
 
        static void Main(string[] args)
        {
            var a1  = A.GetThousands();
            var d1 = DateTime.Now;
            List<A> al1=new List<A>(a1);
            var o1 = al1.Last(x => x.Prop1);
            var d2 = DateTime.Now;
            Console.WriteLine(d2.Subtract(d1).Milliseconds);
            Console.Read();
         }

[cinemania]

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]

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)

[ctxnop]

Bah ca n'a rien de tordu de vouloir parcourir une liste depuis sa fin. C'est typiquement ce qui est fait dans le cadre d'une liste FIFO et même d'une stack. C'est bien pour ca qu'on à inventer les listes double-chainées et qu'on peut décrémenter les itérateurs en C++.
Après, le fait que ce ne soit pas prévu de base dans le framework est une autre histoire et ce n'est de toute façon pas bloquant (cf. les codes ci-dessus).

Quand à l'utilisation de Linq je ne suis pas convaincu. Je suis tout à fait d'accord pour dire que ca simplifie l'écriture de ce genre de chose (sélection d'un élément dans une liste) mais il cherche avant-tout l'efficacité et je ne suis pas sûr qu'une selection via Linq soit une opération O(n) comme celles qu'on propose.

Il faut également prendre en compte que sa liste est a priori accessible par plusieurs thread/processus et qu'il est probable qu'il n'ait pas choisit le type. Cependant s'il peut changer le type de sa liste ca ferait pas de mal, (déjà une liste générique éviterai les casts).

[jonathan3357]

Et pourquoi les fonctions Last() ou First() ... ne répondent pas au besoin ? Je pense que c'est les méthodes les plus optimisées dans ce type de recherche, et en plus avec le typage dynamique du Framework 4.0, j'imagine que tout peut se faire très très simplement sans avoir a faire des for/foreach ... nan ?

[Edit]

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
 
List<dynamic> laListe = new List<dynamic>();
            for (int i = 0; i < 10; 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" });
 
            foreach (dynamic d in laListe)
                Console.WriteLine("{0}", d);
 
            dynamic elt = laListe.Last(d => d.Flag == 1);
 
            Console.WriteLine("Dernier élément avec Flag = 1 : ");
            Console.WriteLine(elt);

[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.

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]

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

[B.AF]

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.