Discussion :

[marchand_de_sable]

Bonjour à tous.

Après avoir développé une appli, je dois en déterminer la complexité.
Bien que ce problème tienne de l'algorithmie, les fonctions java utilisées lors du développement influence nécessairement ce calcul.
J'ai bien trouvé quelques infos là-dessus sur le site de sun, mais pas toutes celles dont j'avais besoin.

Quelqu'un saurait-il donc me dire quelle complexité ont les méthodes contains(Object), indexOf(Object) dans les classes Vector et ArrayList ?

Quelle classe est à utiliser de préférence ?

D'avance merci.
A+

[adiGuba]

Salut,

Quelqu'un saurait-il donc me dire quelle complexité ont les méthodes contains(Object), indexOf(Object) dans les classes Vector et ArrayList ?

Aucune idée...

Quelle classe est à utiliser de préférence ?

Les deux sont implémenté de la même manière, en gérant un tableau d'objet redimensionné au besoin. La principale différence vient du fait que Vector est thread-safe. Mais généralement pour avoir un List thread-safe on passe par la méthode Collections.synchronizedList()...

Donc en gros il vaut mieux utiliser ArrayList sauf si tu utilises des API qui utilisent encore Vector...

Plus d'info dans la FAQ : Quelles différences entre ArrayList, LinkedList et Vector ?

a++

[marchand_de_sable]

Merci pour ta réponse.

J'avais vu les infos concernant les différentes types de List/Collection, et notamment qu'il est recommandé d'utiliser une ArrayList plutôt qu'un Vector. Cependant, il me semble qu'un Vector propose certaines méthodes dont j'ai besoin qui ne sont pas dans ArrayList (enfin, il me semblait l'avoir remarqué, parce que je ne me souviens plus quelles méthodes c'était).

Je vais continuer à me renseigner. Si quelqu'un a plus d'infos, je suis toujours preneur.
A+

[adiGuba]

Cependant, il me semble qu'un Vector propose certaines méthodes dont j'ai besoin qui ne sont pas dans ArrayList (enfin, il me semblait l'avoir remarqué, parce que je ne me souviens plus quelles méthodes c'était).

Si Vector propose beaucoups plus de méthodes, c'est surtout parce qu'elle provient de Java 1.0, et que l'API de Collections date de Java 1.2. Elle a donc été adapté par la suite pour respecter cette nouvelle API. Elle comporte donc plusieurs méthodes "doublons" tels que add() / addElement() ou remove() / removeElement().

Elle semblent donc plus complexe et fournit mais ce n'est pas forcément le cas...

a++

[marchand_de_sable]

Je ne m'étais pas laissé avoir par les méthodes doublons

Mais il me semblait avoir déjà vu des noSuchMethodError avec une ArrayList sur des méthodes présentes dans Vector (autre que les doublons)...
Mais vu que je ne me souviens pour quoi c'était, et qu'à 1ère vue, les 2 classes sont "équivalentes", quelque chose d'autre à dû m'échapper

Je vérifierai tout ça quand j'aurais le temps, histoire de ne pas mourir bête...

[g_rare]

Quelqu'un saurait-il donc me dire quelle complexité ont les méthodes contains(Object), indexOf(Object) dans les classes Vector et ArrayList ?

Après rapide coup d'oeil au code-source des classes ArrayList et Vector : les méthodes "indexOf", et "contains" [qui utilise "indexOf"] sont de complexité O(n).

[marchand_de_sable]

complexité O(n).

Bref, elles parcourent tout le tableau jusqu'à arriver au bon objet, c'est ça ?

Et en utilisant une autre classe, il n'est pas possible d'optimiser cela ?
Par exemple en utilisant une liste ordonnée selon les noms des objets ou que sais-je encor ?

(Désolé, je ne suis pas spécialiste en algorithmie, et je ne connais pas les méthodes de recherches les plus performantes, ni dans quel cadre elles opèrent...)

[mavina]

All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.

En clair, si tu utilises toujours ca, c'est plus rapide d'utiliser LinkedList apparemment

Fred

[marchand_de_sable]

Merci pour vos réponses.

J'en profite pour poser une question subsidiaire.
La Javadoc signal que selon l'implémentation, les List (ou Collection ?) peuvent être ordonnées ou non.
Pour une List ordonnées, doit-on comprendre que ses éléments sont triées ou au contraire laisser dans l'ordre d'insertion ?

[bbclone]

marchand_de_sable> Quelqu'un saurait-il donc me dire quelle complexité ont les méthodes contains(Object), indexOf(Object) dans les classes Vector et ArrayList ?
g_rare > complexité O(n).

marchand_de_sable> Bref, elles parcourent tout le tableau jusqu'à arriver au bon objet, c'est ça ?

marchand_de_sable> Et en utilisant une autre classe, il n'est pas possible d'optimiser cela ?


c'est normal que c'est du O(n) :-)
dans une List et un Vector tes elements sont stocker suivant l'ordre d'insertion. il ne sont pas trier
une recherche dichotomique (tres performante car sont Grand O est de O(log(n) ;-)) ne peut pas fonctionner sur un truc pas trier.

Si tu est sur que tes elements sont trier, tu peut toujours creer ta propre methode indexOf qui fait une recherche dichotomique par exemple :-)

Mais le choix de sun dans l'implementation de sa methode indexOf est un peu obliger.

[marchand_de_sable]

Je pensais effectivement à une recherche dichotomique sur des éléments ordonnées, je n'en connais pas vraiment d'autre...( ). Mais je me disais que certaines implémentations de List devait déjà faire ça, voir mieux encor !!

[bbclone]

les List (ArrayList, Vector, LinkedList) ne sont pas ordonner! Aucune implementation d'aucune List ne fait par defaut une recherche dichotomique.

alors soit tu extends une de ces classes et tu fait ta propre methode indexOf comme je te l'ai dit avant. Ca peut etre fait tres facilment avec une petite methode recursive.

sinon tu peut aussi utiliser la methode Collections.binarySearch

[marchand_de_sable]

sinon tu peut aussi utiliser la methode Collections.binarySearch

lol
C'est parfait

On était à 2 doigts de réinventer la roue

Merci
++