Salut à tous
 
Celà fait plusieurs fois que je soupçonne avoir le même problème: j'ai un tableau de petits objets. Ces petits objets possèdent 2 ou 3 propriétés.
J'ai besoin de mettre ces objets dans un tableau.
 
Pour exemple, le dernier algo est un algo de plus court chemin où j'ai une classe:

Ici <<poids>> représente le poids d'un arc dans un graphe, et <<predecesseur>> est le numéro du sommet précédant sur un plus court chemin.
 
Tous les sommets sont stockés dans une array: RelaxPCC[] sommets; et l'algorithme parcours plusieurs fois cette array pour trouver les plus courts chemins. (algo de Dijkstra)
 
Il me semble que l'array contient des pointeurs (en interne) vers les objets RelaxPCC, ce qui fait que pour accéder au poids par exemple, je me retrouve avec 2 sauts de pointeurs: trouver le pointeur vers l'objet numéro N (premier saut), puis trouver l'adresse où est stocké le poids (deuxième saut).
 
Outre un problème de rapidité sur de très gros graphes, il y a celui de la consommation mémoire: il y a une batterie de pointeurs en trop qui dans ce cas augmentent l'utilisation de mémoire d'1/3 (32+64 bits pour RelaxPPC+ 32bits par pointeur dans l'array). Tout celà ne fait que ralentir encore plus car encombre inutilement le cache CPU. Il me semble que d'utiliser deux arrays (une pour les poids, une pour les prédecesseurs) ne fait qu'empirer.
 
Or il y a plus simple: stocker directement dans l'array (à la C++) alternativement un double et un int avec dans ce cas 1 seul saut de pointeur pour récupérer le poids et une économie d'1/4 de mémoire.
 
Me trompe-je sur la gestion des objets en C Sharp?
Est-ce possible de réduire le nombre de déréférencements?
Est-ce possible de gagner en consommation mémoire?

Vu que c'est une structure, je doute fortement qu'il y ait un pointeur pour accéder aux membres. La taille des membres est connue par le compilo, donc il n'a pas besoin d'un pointeur supplémentaire. Donc en mémoire, l'organisation est déjà telle que tu la décris: un double et un int alternativement (parfois, il peut y avoir du padding pour l'alignement).
C'est en tout cas comme ça avec un compilo C++ et je ne vois pas bien pourquoi ce serait différent en C# ou en Java sur ce point.
 
Si tu veux en être sûr, il faut lire la spec du langage.
Ce qui m'étonne par contre, c'est le fait de représenter un graphe par un tableau.

Ha oui, exact, les lenteurs viennent d'une ArrayList.
Que vais donc changer en array.
 
Si, il s'agit de l'algo de Dijkstra, qui parcours les sommets séquentiellements par adjacence, jusqu'à découvrir petit à petit tous les sommets, et qui place dans une ArrayList les sommets pour lesquels aucun plus court chemin n'est plus possible à trouver.
 
Maintenant que je me rappelle, j'avais aussi utilisé des ArrayList dans d'autres algos, donc à revoir aussi.
 
Pour la conso mémoire c'est à revoir aussi.
 
Merci pour tes éclaicissements, ceci dit comme je peux mettre un objet null dans une case d'une array, je me dit qu'il y a sûrement un pointeur quelquepart.

Petits éclaircissements à la lueurs de mon expérience (je n'ai pas la prétention d'un savoir absolu).
 
* En C# on parle de référence, et pas de pointeur.
Un pointeur tu peux le faire bouger dans ta mémoire (ce qui implique que tu connaisse l'organisation de la mémoire)
Une référence en .Net ça ne pointe que sur des objets d'un type bien définis, dans des zones mémoires dont l'organisation est complètement opaque.
 
* Les variables que contiennent ta structure ne sont pas des références. Quand tu les instancies, tu ne fais pas "new", ce sont des types primitifs. Quand tu fais int a = 5; int b = 5; a++;, tu sais que le a++ ne modifie pas la valeur de b. Ils sont bêtement recopiés par l'opérateur "=", et donc directement contenus dans ta structure.
 
* Niveau mémoire, je te conseille de faire des tests avec une structure et avec une classe. Tu penses sans doute qu'une classe c'est plus lourd. Oui, c'est vrai dans l'absolu d'une implémentation C++, mais l'implémentation de .Net est différente. Je n'ai pas de site qui l'explique bien, mais quand tu instancies deux objets A et B de la même classe, en mémoire, tout la classe n'est pas recréée en mémoire. Seule ses parties modifiables (champs/évènements) sont multiples. La partie commune (définitions des méthodes/propriétés) n'est créée qu'une seule fois. Pour les structures, le fonctionnement est différent. Désolé de ne pas pouvoir t'en dire plus, mais c'est l'avantage et l'inconvénient des langages de haut niveau comme .Net et Java : ne pas s'intéresser à ce qui se passe en dessous.
 
* Pour les ArrayList : oui, t'as complètement raison, c'est clairement à éviter quand tu veux des bonnes perfs sur des tableaux assez gros. Si tu as une idée de la volumétrie, tu pourrais faire un tableau statique de noeuds plutôt qu'un tableau dynamique. (ou 'n' tableaux statiques)
 
* Sinon ta solution d'utiliser deux tableaux d'info sur tes noeuds au lieux d'un tableau de noeuds, bah à la limite pourquoi pas. C'est l'avantage de l'objet : tu peux faire deux implémentations différente et garder le même code au niveau supérieur. Si tu essayes, partage tes résultats. Ca m'intéresse.

Donc, après quelques tests, la bonne solution est d'utiliser une struct et non une class. Dans ce cas il n'est plus possible de mettre null dans une case de tableau. De même un tableau d'int ne peut en fait contenir null.
 
Quand à arraylist... elle convertit la struct (type valeur) en object (type nullable). On se retrouve donc encore avec des pointeurs.
 
Je parle de pointeurs puisque en principe une référence ne peut être nulle. C'est un pointeur bridé car en effet l'arithmétique de pointeurs n'est pas disponible.

Ok: la théorie rejoint la pratique; c'est à vue d'oeil plus rapide.
Résolu.

pourquoi n'utilises tu pas les Generics ? un petit List<RelaxPCC> et ca devrait faire l'affaire

Heu... ben non. Je connais par avance le nombre de noeuds du graphe, donc je peux allouer un tableau statique. Si j'utilise une liste (enfin je suppose que List<> représente une liste simplement ou doublement chaînée -- j'ai pas de compilo sous la main pour vérifier en ce moment) j'ai 1 ou 2 pointeurs de plus par noeud.
 
Pour ceux que ça interesse, j'ai fait quelques expériences avec les ArrayList, ce n'est pas comme leur nom laisserait penser une liste de tableaux, mais ce qu'on appelle un tableau dynamique. C'est à dire que le tableau supporte l'opération Ajouter, en doublant si necessaire la taille du tableau interne et en recopiant les éléments déjà présents. On montre que cet algorithme utilise une taille mémoire au pire de O(2n) et l'opération Ajouter est en moyenne en O(3n).
 
Une autre solution, plus rapide avec presque la même quantité de mémoire, consiste à faire une liste chaînée simple de tableaux (et un pointeur sur le dernier tableau). Ces derniers sont alloués à chaque fois avec une taille double lorsque l'on doit ajouter un élément qui fait déborder. Lorsque l'on doit avoir accès à un élément par son index, la liste est recopiée dans un seul grand tableau de taille double (comme l'arraylist). Cette structure supporte aussi l'opération Vider (en O(log(n)) caché par le GC, qui supprime tous les éléments), et l'opération Economiser (en O(n) qui restreint la taille du tableau interne au nombre d'éléments). La conséquence étant qu'une série d'Ajouter puis un Economiser prends au total O(2n) opérations. Les autres opérations sont de même ordre de grandeur que celles d'une ArrayList, c'est à dire pas très interessantes. Je ne compte pas la mize à zéro (valeurs par défaut) des éléments d'un tableau CSharp, mais ça revient (à un facteur 2 près...) au même.

Il n'y a pas de types primitifs en C#. Les types "primitifs" (int, double,...) sont en fait des alias vers des objets de type System.Int32, System.Double, etc...
 
Sinon, nargy, pour ce genre de question, je te conseille fortement de regarder le source MSIL de tes programmes, c'est une mine d'or et on comprend beaucoup de choses en le parcourant (par exemple, on peut s'apercevoir que les delegates et les events sont exactement la même chose, sauf que les events n'exposent que 2 accesseurs : add et remove, correspondant respectivement aux opérateurs += et -=)

Allez, pour illustrer, la preuve par MSIL que les types primitifs sont des alias. Une petite addition toute conne :

namespace primitif
{
    class Program
    {
        static void Main(string[] args)
        {
            int a = 3;
            int b = 12;
            Console.WriteLine("a+b={0}", a + b);
        }
    }
}

et le code MSIL correspondant :

Ligne 6 : On constate que les locales a et b sont en fait des Int32
Ligne 17 : Le résultat de l'addition est boxé en Int32
D'une limpidité sans faille. Je ne saurais que trop recommander de se mettre au MSIL, ça sert toujours.

hmmm... le code est interessant en effet..
 
ceci dit, je ne l'analyse pas de cette façon, si le résultat de l'addition est boxé c'est parceque WriteLine prends des objets en paramètre (pointeurs/références vers les valeurs) et non des <<types-valeur>>.

Oui et non.
Oui, il aurait été plus exact de parler de types valeur (ValueType).
Non, ce ne sont pas des classes en interne. Ce sont bien des types 'primitifs' (y'a une meilleure traduction pour "built-in types" ?)
C'est le boxing qui donne l'illusion que ce sont des classes et permet de s'en servir comme tel.
+1 pour nargy.
http://msdn.microsoft.com/library/ [...] xingPG.asp