Bonjour
J'ai n valeurs à sauver dans un tableau. Ces valeurs sont identifiées par un index. Malheureusement, comme cette index n'est pas entre 0 et n-1, déclarer un tableau int[] array= new array[index_max] n'est pas franchement efficace.
On peut evidemment utiliser une hashtable, mais malheureusement, c'est vite très lent, devant à chaque fois créer un objet (new Integer(index)).
Existe-il une autre methode, très rapide, permettant soit de sauvegarder une structure sans devoir creer un new pour chaque index, ou simplement de faire le mapping entre 2 valeurs (et alors, le ième index introduit est mappé avec la valeur i).
D'avance merci

tu es sûr que ton new Integer est lent ? tu as mesuré ?
 
Si *vraiment* (mais je demande le contexte exact) ça impacte, tu refais ta propre table de hachage sur cle entières.

Pas mesuré... mais la création d'un nouvel objet n'est jamais très rapide... Et là, il ne s'agit pas de programmer un site web ou un simple applet, mais de simulation demandant une assez grande efficacité (on parle en heure de calcul).

et ben mesure.
 
(c'est sur ce genre d'affirmation qu'on se prend des fessées)

en cas de besoin, dans je sais plus quel projet de commons d'apache (je miserais sur collections), ils ont écrit les implémentations de ArrayList et HashMap pour tous les types primitifs ...

Hummm, un vector tout bêtement ferait l'affaire non??
Ensuite elementAt(i) contient la valeur placée en ième position... j'ai dû passer à côté de quelque chose, ça me paraît trop simple.

Lemicky > oui, tu as raté soit le fait qu'il veut une versoin creuse soit les collisions inhérentes à une table de hachage.

 
Euh... désolé, mais je vois mal comment une allocation mémoire avec assignation pourrait être aussi rapide qu'une assignation toute simple.  
Et c'est ce qui se trouve dans tous les bouquins que j'ai lu.
Alors je veux bien m'amuser à mesurer... mais j'aurais tendance à m'attendre très fortement au résultat. Et même si ce n'est que 50% plus lent... c'est déjà énorme lorsque l'on parle de simulation, avec un milliard de données à traiter...

 
+1
 
Dire que les allocations new sont lentes, a part faire un systeme temps reel, je vois pas en quoi un appel a new peut ralentir ton programme. Ne serait-ce que l'optimisation d'une ligne de code dans ton programme, je suis sur que tu gagnes ce que tu perds avec le new  
Etre exigeant sur la vitesse a ce point, tu as autant a passer en C.  

Bon... essayons d'y voir plus clair:
- Contestez vous le fait que x= new Integer(i) soit plus lent que x=i?
 Si oui, alors dites moi sur quelle base? Il me semble évident qu'une affectation est plus rapide qu'une allocation mémoire...
 Si non, alors oui, je suis d'accord avec vous, sur le fait que dans la majorité des cas, c'est pas obligatoirement hyper grave. Sauf que là, je parle du traitement de 100 millions de valeurs. Je parle de grosses simulations... et donc, lorsque vous executez rien que 1mio de fois une ligne de code, avoir un new ralentit les choses...
 
Concernant l'aspect Java VS C, je bosse sur un projet. Parce que mon travail s'intègre à un tout, je ne peux pas bosser dans un autre language. Même si, je le sais, C aurait été plus rapide...
 
P.S: A titre d'indication, j'ai assigné chaque cellule d'un tableau de int. Et j'ai alloué chaque cellule d'un tableau de integer. La différence de temps? un new rallentit d'un facteur 58! C'est pas franchement négligeable...

bon bah refait ta table de hachage.
 
Mais ton approche de l'optimisation est particulière. Quand à se gargariser sur les chiffres de ta simul, avec ton approche de la chose, de toutes façons, soit tu as beaucoup à apprendre soit elle ne sera pas aussi efficace qu'elle ne pourrait.
 
(oui, c'est une attaque personnelle)

 
Pardon ?
Tu me dis (de manière pas très diplomatique), qu'un new c'est pas un problème. Je te dis que cela en est un lorsqu'il est executé plusieurs (centaines de) milliers de fois.
Tu me réponds que non... Je te prouve le contraire et tu m'attaques personnellement?
Mon approche de la chose? J'étudie mon code et j'essaye de virer les instructions qui me le ralentisse inutilement. C'est quoi ton approche? Considérer qu'un new n'a aucun influence alors que cela ne correspond en rien à la réalité (pratique comme théorique).
Alors passe au point de Godwin directement si cela te chante, mais vérifie ce que tu clames avant...

je clame qu'un microbenchmark n'est pas représentatif d'un profil complet.
 
Maintenant, tu as raison, ça semble être assez prohibitif, probablement à cause du viellissement.

Ok. Alors toi qui a une vision très globale de la chose.
Explique moi soit théoriquement, soit pratiquement (avec code à l'appui), comment un x= new Integer(i) peut etre aussi rapide que x=i?  
 
Je vois pas en quoi cela te pose un problème que je cherche à virer mes new, si je le peux?
 
Par curiosité, tu as déjà bossé dans la simulation? Tu as une expérience personnelle qui te permet d'affirmer que généralement, plusieurs news, au milieu de qq lignes de code, répétées plusieurs milliers de fois ne sont jamais le problème?
 
Parce que là, sincèrement, je ne vois pas du tout le but de ta démarche, si ce n'est l'attaque personnelle
 
 
 

je pense que nraynaud ne conteste pas ton affirmation en elle-même, mais plutot ta manière de la justifier. Les mécanismes d'optimisation au runtime de la jvm font que ton "benchmark" n'est peut-être pas aussi fiable que tu le penses.

non, j'ai pas bossé dans la simulation.
 
J'ai bossé dans le traitement de la vidéo en temps réel (et en vision répartie), si mon CV te passionne.
 
On peut capitaliser sur certaines allocations, le but est toujours de partir dans cette démarche avant de se lancer dans un développement d'une table de hachage soi-même (qui, elle aussi va allouer de toutes façons).
 
Et oui, je connais des gens qui se sont pris de *grosses* fessées sur des préjugés (tels que "le C c'est plus rapide", mais aussi sur les perfs d'un GC).

 
Tout a fait d'accord avec cela. Je ne considère pas le résultat de mon test (sur demande de nraynaud) comme une vérité absolue.
Mais personne ne peut remettre, je crois, en cause le fait qu'un new (ou toute autre allocation mémoire) soit une chose dont on ne doive pas se préoccuper, lorsqu'elle se trouve au milieu d'une boucle largement utilisée. Et donc... j'essaye d'améliorer cela. Et personne pour l'instant n'a peu m'aider dans ce sens là.
 
Et tout cela ne donne aucun raison de m'attaquer personnellement (et de le revendiquer), comme si j'étais le plus grand con du monde. Il me semble que l'on est quand meme ici sur ce forum pour partager des informations, pas pour mesurer qui a la plus grosse et qui programme mieux que le voisin. Peut-etre qu'il n'y a pas moyen d'enlever ces news (sauf en passant à java 1.5, qui permet de passer une clef à une map sans qu'elle soit de type objet. Version que je ne peux malheureusement pas utiliser pour l'instant).
Merci
 
P.S: Aucun préjugés de mon coté. Ne me fais pas payer pour les autres...

non, pas du tout. c'est *exactement* le même graphe mémoire. par combinaison de generics et d'autoboxing.
 
 
(en fait, c'est peut-être pas pareil parce qu'il est possible qu'ils aient viré la puissance de 2 sur la longueur de la map, mais c'est un autre sujet)

Non, le boxing est implicite, mais il est quand même la

 
Autant pour moi. Si vous en êtes sur.

certain :  
http://java.sun.com/j2se/1.5.0/doc [...] oxing.html

Merci bcp!

Ok, je n'avais pas vu que les indexs n'étaitent pas concommitants.
Ben moi j'opterais pour 2 tableaux :
int[] tabIndex=new Array[nbMax];
monObject[]tabObj=new Array[nbMax];
 
et tu mets ton objet monObject de la façon suivante :
tabIndex[i]=indexObjet;
tabObj[i]=monObjetaIndexObjet;
 
Au fait tes n valeurs, c'est quoi? un objet, des int? t'en fais quoi de ton tableau ensuite? Car ça pourrait aider à trouver un mécanisme adapté.
 
Oui, non? je suis encore à côté de la plaque?

Finalement, je vais utiliser une hastable, pour faire la mapping, au début (je peux alors travailler en index locaux). Je ne vois pas plus simple
Et pour la structure, utiliser un CRS (les valeurs ne devant qu'etre lu, et pas modifiées).
Pour répondre à la dernière question: Il s'agit de tableau de double, à certains doivent etre lu et modifié, d'autres uniquement lu.

acces en  O(n), mais le monsieur il a dit que n est enorme, donc non.

je viens de réfléchir à cette histoire (oui, je rumine comme mon psy dit, mais ça me permet parfois de trouver des analyses un peu intéressantes).
 
Or il se trouve que faire une insertion dans une HashMap, c'est faire une allocation du petit chainon (HashMap$Entry,  16 octets, instances non-recylcables) de la liste chainée (HashMap.java ligne 739, fonction addEntry()), réduisant le coût relatif d'une allocation de l'Integer.

Intéressant... je vais regarder cela.
Actuellement, la version actuelle ne demandant pas une modification de la matrice sparse, mais uniquement une lecture, je pensais la convertir en CRS (http://www.cs.utk.edu/~dongarra/etemplates/node373.html).
A suivre... (j'ai actuellement d'autres problème, avec l'algorithme lui-meme)

korben > oui, carrément si tu n'as pas d'insertions, vecteur à 2 lignes et recherche des éléments par dichotomie.

C'est vrai que *certains* projets ont besoin d'optimisation supplémentaire, mais quand on programme en Java, habituellement on commence par utiliser des méthodes génériques, et la HashMap convient très bien pour créer des "SparseTable" ou "SparseMatrix". Ensuite on regarde dans leprojet les véritables goulots d'étranglement, et on pense éventuellement à remplacer les génériques par des versions spécialisées. Un micro-benchmark ne sert à rien si cela conduit à complexifier un projet et qu'on passe à côté de l'essentiel des optimisations nécessaires. En particulier remplacer une "sparse table" par un énorme tableau sera un véritable gachi énormément plus couteux en performance qu'une HashTable.
Le "new Integer()" semble couteux au prime abord, cependant ce type de microallocation est trs bien pris en charge par la JVM qui gère d'énorme quantités de ces allocations et sait aussi les gérer de façon efficace, car ce sont des objets de taille fixe très faciles à manipuler par le garbage collector (d'autant que la classe java.lang.Integer contient aussi des optimisations péciales pour les valeurs les plus communément utilisées afin d'utiliser le partage d'instances, puisque les objets Integer sont non mutables, chaque changement de valeur d'une variable référence obligeant à référencer une autre instance.)
Souvent on règle bien des problèmes de performance en évitant de trop imbriquer les micro-méthodes les unes dans les autres, et en créant des méthodes de taille suffisante, avec un peu de pratique pour que le code reste maintenable, on le fait sur les véritables goulots d'étranglement, et uniquement sur les parties stables du code qui n'ont pas vocation à être modifiées car leur design est entièrement défini par la fonctionnalité qui n'admet pas d'autre comportement. Mais là aussi on ne le fait qu'après des phases de test très rigoureuses: il n'est rien de pire que d'optimiser un projet trop tôt: c'est l'enfer ensuite à maintenir et faire évoluer et on va laisser passer pleins de bogues avec des tas de cas non testés dont on n'a même pas soupçonné au départ qu'ils étaient possibles ou qui pouvaient sembler ridicules.
le propre de Java est justement de justement utiliser un profilage de l'application à l'exécution en fonction de l'utilisation réelle et non en fonction d'une plateforme théorique. Aussi le design de programmation par "délégation" est souvent celui qui conduit le plus vite à la bonne solution, au code le plus stable, et qui permet le plus facilement de revoir et d'adapter des structures de données ou de code en fonction d'un objectif global donné et non d'un comportement local. On fait en fait les meilleurs gains de performance en travaillant au niveau global plutôt qu'au niveau local, et cela avec beaucoup moins d'effort. La modélisation est donc primordiale sur tout le reste (et si on a parfois besoin de micro-optimisations, il est toujours temps d'en parler et proposer ces optimisations des librairies du JRE sur les bug-reports de Java, où celle-ci sera évaluée sur bien plus de plateformes et de cas que vous ne pourrez souvent en utiliser tout seul.)
Concernnt les sparse-table et sparse-matrix, il n'existe aucune stratégie d'optimisation toute faite répondant à tous les cas, car justement le comportement statistique dépend de chaque cas particulier. la méthode par HashMap est la plus générique et marche le mieux dans la grande majorité des cas, même si on peut imaginer des optimisations locales dans un cas particulier (après un benchmark réel, pas sur une simple supposition: certaines optimisations apparentes dans un micro-benchmark ont un effet négatif sur les performances d'une application complète car ces optimisations se font au détriment d'autres, notamment si elle conduit à utiliser des objets apparemment plus simples mais de taille variable et non fixe comme ici, et dont la taille maximale n'est pas maitrisée, comme peut l'être un Vector utilisé là où il faudrait une collection chainée).
D'une façon générale, plus la structure de donnée globale à manipuler est grosse, plus on a intéret à ne pas optimiser localement les données et à utiliser les méthodes génériques (sinon on s'expose à de sérieux problèmes de déploiement et de dépassement de ressources à l'exécution, avec un surcroit de travail pour la VM et le garbage collector qui aura bien plus de contraintes s'il doit manipuler de nombreux objets mutables de taille variable qu'il ne peut que déplacer avec de couteuses copies et réallocations).
Laissez donc les "new Integer()" (et l'autoboxing en Java 6) faire leur travail vite et bien.

Moi aussi j'aime le pâté

Mais remonter un thread vieux de 4 ans c'était pas obligatoire

Sauf que la HashMap n'utilise pas une liste chainée mais bien un tableau (via un vecteur réallouable) pour stocker les références aux Map.Entry, qui sont ordonnées dynamiquement par la fonction de hachage (qui est autoadaptative en fonction du taux de remplissage).
Le coût n'est pas une allocation systématique de 16 octets par appel mais beaucoup moins.
C'est justement l'intérêt d'utiliser une table de hachage: on évite de manipuler de gros tableaux, et on profite du comportement adaptatif très utile sur une aplication complète qui a très souvent de grandes différences de comportement local sur ses données (certaines étant volumineuses et très "compactes", d'autres très petites et partielles). Le coût relatif du "new Integer()" est très faible (et ces allocations fixes étant très faciles à manipuler par le GC) en proportion du gain énorme que procure les tables de hachage en terme de mémoire globale, de réallocations, et de travail pour le GC: l'optimisation se reporte sur le niveau global qui est toujours le plus significatif.

Le pâté au café? Ca doit pas êre bien bon...
Quant au thread s'il est remonté, c'est par hasard, dans une citation depuis un lien externe qui y faisait référence. La date importe peu, le sujet est resté d'actualité (et n'est pas d'ailleurs spécifique à Java, cette question sur les design pattern étant toujours largement discutée).

Avoue, t'es un multi de Jovalise ou de Magicbuzz?

c'est qui ce gars là ?
 
En plus il comprend pas les posts auquel il répond

J'ai parfaitement compris de quoi ça parlait. Pas la peine de railler sur quelqu'un comme ça.
Peut-être que je ne suis plus venu ici depuis longtemps, pourtant j'ai été parmi les premiers utilisateurs de ce forum (il y des années, je ne me souviens plus de la date mais ça date du début des années 1990 (1993 je crois), au temps où Hardware.fr était d'abord visité par des passionnés qui se rencontraient autrement que seulement devant un clavier pour se balancer des insultes en langage SMS (le SMS n'existait pas encore, on parlait encore français,  on était content encore avec nos PC 386DX2 sous DOS/Windows3 et les tous premiers Unix-like puisque Linux n'existait pas non plus, au mieux avec 32Mo de RAM à plus de 10000 FRF pièces, bien avant le Pentium, et on se connectait avec des modems qui n'atteignaient même pas les 32 kbit/s avec une facture à la durée et de chères notes de téléphone, ou de RNIS ensuite pour monter à 64kbit/s).

tu veux dire 2000 ?

Je ne me rappelle plus quand je suis venu ici, mais peut-être que c'était sur un autre réseau avant qu'on décide de venir sur Hardware.fr (peut-être qu'Hardware.fr n'existait pas encore non plus, ou ce n'était qu'une petite boutique) De toute façon ça fait longtemps, et comme je l'ai dit j'ai oublié la date, ce que je sais c'est qu'à l'époque je me connectais à l'Internet via Compuserve avec une facture en dollars US. Et j'ai été le premier sur les projets distribués comme SETI@home qui a amené beaucoup de monde ici.

ok, ça arrive à tout le monde de se tromper donc je vais t'expliquer de quoi je parlais : je parlais des listes chainées qui sont sous les buckets dans la map pour gérer les collisions.

et donc, le fait que tu sois un vieux con aigri t'autorise donc à remonter des posts vieux de 4 ans et faire des pâtés illisibles hors-sujets ?

un vecteur indexé par hachage c'est bien plus rapide et cela garantie la stabilité des performances quel que soit le volume utilisé dans la structure 'parse' (en plus le hachage peut-être multidimensionnel, sans qu'il y ait de relation dépendante entre les dimensions sources et les dimensions des index de la structure de stockage).