[algorythmie] remplir un tableau dont on ne connait pas encore la taille

Bonjour,

je rencontre le cas souvent et j'aimerais savoir conmment vous le traitez.
J'ai un tableau normal de taille fixe qui contient des informations, et j'aimerais en faire un sous tableau qui ne contiendrait que les informations correspondant à un certain critère.
Suis-je obligé de faire 2 parcours ?
-l'un pour compter les éléments,
-l'autre pour remplir le tableau aini dimensionné

ou alors je fais un tableau trop grand exprès ? (laissant la fin à null)

Merci

Pourquoi ne pas utiliser les ArrayList ??

;) ha oui, c'est une bonne idée, je les avais totalement oublié ceux la

Ma méthode me demande une String [], il et pour la convertir il suffit d'utiliser la méthode .toArray[] (enfin, j'ai été obligé de faire une cast)

fais quans même attention avec certaines méthde de la classe ArrayList<T> (comme le tri manuel), ça bouffe de la mémoire. Ce n'est pas toujours la structure de données appropriée. Moi je préfère les LinkedList<T>, par exemple la complexité de la méthode add(T t) est nettement inférieure. L'ennui c'est le parcours de ces structures...

Citation:

---

Envoyé par Razgriz

fais quans même attention avec certaines méthde de la classe ArrayList<T> (comme le tri manuel), ça bouffe de la mémoire. Ce n'est pas toujours la structure de données appropriée. Moi je préfère les LinkedList<T>, par exemple la complexité de la méthode add(T t) est nettement inférieure. L'ennui c'est le parcours de ces structures...

---

La complexité de add(T t) d'une ArrayList est en O(1) (tu ajoutes en dernière position, et l'index est mémorisé). Donc tu ne peux pas faire beaucoup moins...

C'est plutôt la complexité du remove(Object o) qui est différente...

Clairement remove(T t) c'est différent.

add(T t) oui c'est en O(1) donc on peut pour ainsi dire pas faire mieux oui, mais celle de add(T t, int index) ça on ne sait pas, faudrait voir l'implémentation. Je me trompe peut-être, mais je crois que dans ce cas c'est le même truc que pour remove(T t)...

Salut,


Attention à ne pas confondre consommation mémoire et temps d'exécution !!!!

Les LinkedList consomment plus de mémoire car elle neccessite de conserver un référence vers les éléments précédents et suivants, en plus d'un objet qui servira de conteneur.

Les ArrayList consomme un peu moins dans le sens où elle utilisent seulement un tableau automatiquement redimensionné, et que chaque objet stocké n'utilisera qu'une référence. Toutefois ce tableau peut être plus grand que neccessaire pour éviter de trop nombreux redimensionnement, mais l'on peut diminuer sa taille au stricte neccessaire avec trimToSize() une fois que la taille de la liste est fixe.


Et les ArrayList ont un gros avantage : étant donné leur structure, les accès indexés sont très rapide, alors qu'il faudra parcourir tous les éléments précédents avec une LinkedList...

Bref, mis à part si l'on souhaite ajouter des éléments en début de liste, ou supprimer des éléments régulièrement, les ArrayList font très bien l'affaire...

a++

Oui désolé pour la confusion apparente entre mémoire et complexité.
C'est vrai que pour le parcours des LinkedList, c'est chiant il faut utiliser un itérateur. Par contre leur structure fait que ajouter un élément ou en supprimer un qui n'est pas en fin de liste (cf ArrayList) est extrêmement souple.

Le gros avantage des ArrayList est l'indexage rapide (avantage sur LinkedList) et la tailel variable (avantage sur tableaux [] )

LinkedList c'est très pratique pour les files fifo et piles lifo...

j'ai un petit problème la dessus en fait :

Code:

---

1 2	final Process p1 =r.exec((String []) cmdParams.toArray());

---

ca roulait apparemment sans problèmes sous le Compiler 5.0, mais quand je suis revenu à java 1.4.2, ca me donne une :

Code:

---

1 2	java.lang.ClassCastException

---

du coup, je suis un peu ennuyé... (:mrgreen: je veux bien sur rester en 1.4.2)

Citation:

---

Envoyé par d_token

j'ai un petit problème la dessus en fait :

Code:

---

1 2	final Process p1 =r.exec((String []) cmdParams.toArray());

---

ca roulait apparemment sans problèmes sous le Compiler 5.0, mais quand je suis revenu à java 1.4.2, ca me donne une :

Code:

---

1 2	java.lang.ClassCastException

---

du coup, je suis un peu ennuyé... (:mrgreen: je veux bien sur rester en 1.4.2)

---

oui, normal, toArray() te renvoie un T[] (ou T = String ici) sous 1.5, mais sous java < 1.5, et bien c'est un Object[], donc tu ne peux pas caster en String[]... Tu es obligé de te créer un nouveau tableau de String[] et tu copies tous les éléments en les castant un par un (vive java 1.5, non?)

:mrgreen: ou à bas java 1.4.2

:P je vais rester à la méthode de base : parcourir 2 fois le tableau, une pour la taille, la 2è pour le remplissage !

merci de ta réponse !

Citation:

---

Envoyé par d_token

:mrgreen: ou à bas java 1.4.2

:P je vais rester à la méthode de base : parcourir 2 fois le tableau, une pour la taille, la 2è pour le remplissage !

merci de ta réponse !

---

Pour la taille, il suffit de faire tab.length

Salut,

Citation:

---

Envoyé par ®om

oui, normal, toArray() te renvoie un T[] (ou T = String ici) sous 1.5, mais sous java < 1.5, et bien c'est un Object[], donc tu ne peux pas caster en String[]...

---

Heu... Même sous Java 5.0 toArray() renvoit un Object[] dont le type réel est bel et bien Object[], et ne peux donc pas être casté en String[]. Donc tu dois surement avoir une exception également avec une JVM 5.0...


C'est la méthode toArray(Object[]) (qui est devenu toArray(T[]) dans Java 5.0) qui permet d'obtenir un tableau du bon type.

Citation:

---

Envoyé par ®om

Tu es obligé de te créer un nouveau tableau de String[] et tu copies tous les éléments en les castant un par un (vive java 1.5, non?)

---

Non il suffit d'utiliser la seconde méthode toArray() :

Code Java 1.4 et inférieur :

Code:

---

String[] data = (String[]) cmdParams.toArray( new String[ cmdParams.size() ] );

---

Code Java 5.0 (pas de cast) :

Code:

---

String[] data = cmdParams.toArray( new String[ cmdParams.size() ] );

---

A noter que l'on peut utiliser new String[0], et dans ce cas un nouveau tableau de la bonne taille sera alloué dans la méthode toArray()...

a++

PS : Je te conseille fortement d'utiliser une JVM/JDK correspondant à la version minimum avec laquelle ton application devra être compatible...

Oui, tout à fait, merci adiGuba :)

D'ailleurs, au lieu de ça, ils auraient pu changer la méthode .toArray() pour renvoyer un T[] dans java 1.5... Je ne sais pas pourquoi ils ne l'ont pas fait...

merci à vous deux pour la réponse et merci pour le conseil adiGuba.

En fait, je codais sans le savoir avec le JDK 1.5 (par défault sou eclipse) et quand j'en ai changé ca m'a fait tout drole ;)
Enfin, maintenant, c'est bien paramètré ^^

^^ je sais aussi que pour avoir la taille d'un tableau *.length est pratique, seulement, je ne prend pas tout les éléments, mais seulement ceux dont propriété = true ! (d'ou mon impossibilité de connaitre la taille avant de créer le tableau)

:mrgreen: enfin, grace à vous c'est de l'histoire ancienne

Citation:

---

Envoyé par ®om

D'ailleurs, au lieu de ça, ils auraient pu changer la méthode .toArray() pour renvoyer un T[] dans java 1.5... Je ne sais pas pourquoi ils ne l'ont pas fait...

---

A cause des limitations des Generics et pour des raisons de compatibilitées...

Les Generics ne sont valables qu'a la compilation et sont "perdus" à l'exécution.

Cela a quelques désavantages :

• Tous les casts sont toujours présents mais seulement cachés au developpeur (et donc c'est un peu moins performant même si la différence doit être vraiment minime).
• On ne peut pas utiliser les types primitifs, mais seulement des objets.
• On ne peut pas connaitre le type exact avec lequel la classe a été paramétré lors de l'exécution.

Ainsi le code suivant :

Code:

---

1 2 3

List<String> list = new ArrayList<String>(); list.add("Hello World"); String s = list.get(0);

---

Est strictement identique lors de l'exécution au code suivant :

Code:

---

1 2 3

List list = new ArrayList(); list.add("Hello World"); String s = (String) list.get(0);

---

Mais également des avantages :

• Une compatibilitée parfaite avec les codes compilées avec les anciennes API. Ainsi toutes les classes Generics peuvent être utilisées avec des API qui n'était pas concus pour à l'origine. Cela permet ainsi de les utiliser massivement dans des classes existantes sans casser la compatibilité. Et d'ailleurs il y a de forte demande pour les utiliser encore plus (en particulier dans Swing et ses modèles).
• Cela permet également plus de notions, comme les variances (hériter/implémenter un ou plusieurs type de base), les wilcards (qui permet de limiter l'utilisation des méthodes générics) ou encore les méthodes generics indépendantes.
• Un code unique : pas de multiple copie automatique du code par le compilateur ou la JVM : c'est le même code qui est utilisé quel que soit le type paramétré...

A titre d'information les Generics du C# ont pris exactement la solution inverse de celle de Java. et dispose donc désormais de deux API de collections : une standard datant de .NET 1.0, et celle de .NET 2.0 qui utilise les Generics...

Pour plus de détail : http://lroux.developpez.com/article/...ge_5#Lgenerics

a++

Citation:

---

Envoyé par adiGuba

A cause des limitations des Generics et pour des raisons de compatibilitées...

---

Rien n'empêchait de faire une nouvelle méthode .toArray() qui soit générique, et quand la généricité n'est pas utilisée, ça renvoie un Object[]...

Citation:

---

Envoyé par adiGuba

Les Generics ne sont valables qu'a la compilation et sont "perdus" à l'exécution.

Cela a quelques désavantages :

• Tous les casts sont toujours présents mais seulement cachés au developpeur (et donc c'est un peu moins performant même si la différence doit être vraiment minime).
• On ne peut pas utiliser les types primitifs, mais seulement des objets.
• On ne peut pas connaitre le type exact avec lequel la classe a été paramétré lors de l'exécution.

---

Pourtant, avec une méthode générique, tu peux "récupérer" le type:

Code:

---

1 2 3

public <T> T methode(List<T> list) { T t = list.get(0); }

---

Citation:

---

Envoyé par ®om

Rien n'empêchait de faire une nouvelle méthode .toArray() qui soit générique, et quand la généricité n'est pas utilisée, ça renvoie un Object[]...

---

Mais il est impossible de connaitre le type paramétré puisqu'il est perdu : donc c'est impossible.

Citation:

---

Envoyé par ®om

Pourtant, avec une méthode générique, tu peux "récupérer" le type:

---

Non : tu connais juste T mais pas son type exact. Or c'est ce dont tu as besoin pour créer un tableau.

Le code suivant ne compile pas parce qu'il est impossible de connaitre le type exacte de T à l'exécution :

Code:

---

1 2 3 4 5

class Test<T> { public T[] toArray() { return new T[5]; } }

---

a++