Bonjour à tous,

Je suis en train de réaliser un petit logiciel, il s’agit en fait d’une sorte de petit « défis ».

Ce logiciel (que je réalises en Java) a un fonctionnement assez simple, il consiste à analyser des pages web. Voici son fonctionnement :

Je lui donne une URL de départ (qui est dans mon cas une recherche sur google), il va analyser le résultat (la page HTML retournée), il récupère toutes les URLS présentes sur la page, et relance la procédure pour chacune des URLS trouvées.

Voici quelques précisions techniques concernant le logiciel :

-J’utilises des Thread pour effectuer les recherches, permettant de lancer pleins de recherches en même temps.

-Ces threads se réfèrent tous à une méthode « synchronized » pour le retour des urls trouvées.

-Ces urls sont stockées dans une ArrayList.

-Je ne rajoute une url dans l’ArrayList que si elle n’est pas déjà présente (histoire d’éviter de visiter plusieurs fois le même site).

Et bien entendu, si je publie ici c’est qu’un souci se pose :

Au début j’ai un nombre de page/seconde assez impressionnant (proche de 600), mais au plus j’avance au moins ça va vite. J’en ai analysé la cause et il semble que ce soit la taille de l’ArrayList (près de 90 000 éléments après 1 minute) qui pose soucis, plus précisément, la recherche d’url dedans (le moment où je vérifie si elle est présente). Mon but étant bien entendu de visiter le plus de sites possibles, je souhaiterais aller plus loin et tenter d’optimiser ce processus.

J’ai déjà quelques pistes mais je voudrais voir avec vous s’il existe des solutions.

### PISTES EN JAVA ###

Question : comment enregistrer un grand nombre de chaine de caractères et pouvoir vérifier si une chaine est présente dans cette liste ?

-Utiliser un SGBD.

-Utiliser un autre langage (C ?)

-Réaliser moi-même mon modèle de donnée pour en optimiser le fonctionnement (en supposant qu’il soit possible de faire quelque chose de plus optimisé que les méthodes de l’API)

-Utiliser une méthode de HASH pour diminuer la taille des chaines.

### PISTES MATHEMATIQUES ###

Question : comment réduire le nombre d’éléments à stoquer ?

-Je n’ai pas de réel piste autre que, ne rien stoquer et prendre le risque de re-visiter le même site une multitude de fois

Ce post sera présent dans le forum Java et dans le forum Mathématique car je penses que la question a un réel intérêt à être vue sous les deux angles.

Merci d’avances

Lien vers le sujet Java : https://openclassrooms.com/forum/sujet/optimisation-arraylist-contains

Salut,

Si je ne dis pas de bêtises, une recherche d'élément se fait en O(n) pour un ArrayList. Ce qui est lent quand l'array devient grand. Tu pourrais à la place utiliser un HashMap, sauf erreur de ma part la recherche s'y fait en O(1). Rien que ça devrait largement améliorer tes résultats. Tu peux voir une comparaison des différentes structures ici : http://infotechgems.blogspot.com/2011/11/java-collections-performance-time.html

La taille des chaînes ne change pas grand-chose.

Mathématiquement si tu veux avoir une détection de doublons parfaite, tu n'as pas beaucoup d'autres choix que ceux-ci, en particulier si tu ignore le nombre d'éléments que tu vas devoir tester, ou que l'univers des possible est trop grand.

Bonjour,

Merci beaucoup, je connais pas mal l'API Java dans les fonctionnalités qu'elle propose, mais j’avoue ne pas suffisamment connaitre les caractéristiques des différents éléments présents en elle. Comme par exemple cette différence dans la complexité entre les différentes listes proposées par la classe List.

Concernant les Hash, c'est une technique que j'ai testé et décidé de laisser tomber. J'ai essayé avec Sha1 (suffisant pour mes expérimentations) et une observation est à faire :

Sha1 retourne des chaines de caractère de taille constante, quel que soit la taille de la chaine d'entrée, résultat : parfois ça raccourcit mes urls. Mais parfois ça les rallonges, en ajoutant ça au temps de calcul du hash et bien que après des tests, il est vérifié que l'on gagne (un tout petit peut) du temps de calcul sur des chaines courtes pour la comparaison, le total ne me fait pas gagner de temps, voir même en perdre.

Je vais faire des tests sur un set de 100.000 url récolté précédemment, en mettant en concurrence ArrayList avec d'autres types de Liste.

Je reviendrais vers ce post quand j'aurais des chiffres,

Merci, bonne semaine

Non mais les HashMaps c'est pas un truc à implémenter toi-même, c'est une classe de l'API : https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html

Par exemple tu définis ta HashMap comme Hashmap<string boole="" an="">; maHashMap, tu ajoutes true pour chacune des URL que tu rencontres. Tu testes si une URL est présente avec par exemple containsKey, ou encore getOrDefault(., false), ça se fait en temps constant, contrairement à l'ArrayList qui est en temps linéaire.

Edit : bon ce site c'est de la merde pour écrire du code mais tu saisis l'idée.

-
Edité par melepe 30 juillet 2018 à 14:06:59

Bonjour,

Doublon

Les doublons nuisent au bon fonctionnement du forum et sont donc interdits. Si vous vous êtes trompé de section, il suffit de signaler votre sujet au staff pour qu'il le déplace au bon endroit.

Je vous invite à continuer la discussion sur l'autre sujet : https://openclassrooms.com/forum/sujet/optimisation-arraylist-contains?page=1#message-92559089

Je ferme ce sujet. Me contacter par MP si besoin.