Discussion :

[Ceubex]

Bonjour,

J'ai une liste d'attente ConcurrentLinkedQueue<UrlX> d'URL (plus précisément ce sont des UrlX, un objet que j'ai créé avec une propriété urlString (string)).
J'ai 10 threads qui prennent les urls une à une (ils supprime l'url qu'ils prennent) et de temps en temps ces threads rajoutent des urls

L'ennui est que pour le pas avoir de heap space error j'ai une fonction qui regarde si l'url n'est pas déjà dans la file d'attente avant de l'ajouter :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
    private boolean urlQueueContain(String urlString,int depth) {
    	Iterator<UrlX> it=this.urlQueue.iterator();
    	UrlX url;
    	while(it.hasNext())
    	{
    		url=it.next();
    		if(url.urlString.equals(urlString))
    		{
    			if(url.depth>depth)
    			{
    				this.urlQueue.remove(url);
    				return false;
    			}
    			return true;
    		}
    	}
    	return false;
    }

Et cette fonction prend beaucoup de temps à s'exécuter. Avant j'utilisais un ArrayList qui était beaucoup plus rapide mais à l'époque il n'y avait pas d'accès concurrent
Comment puis je résoudre cela ?

[Pill_S]

Déjà, la boucle à base d'itérateur c'est vraiment old school... "for each" c'est bcp plus joli (mais ça va pas améliorer tes perfs).

Si ton objet UrlX est immuable (son état ne change pas après instanciation) et que equals et hashcode sont correctement implémentés, alors la manière la plus rapide de déterminer si la queue contient un élément, est de passer par un hashset (en plus de ta queue) qui permet (théoriquement) un accès en temps constant (O(1)).

En fonction de ton cas d'utilisation, le surcoût lié au maintien de la cohérence entre les 2 structures de données sera contrebalancé par la rapidité du contains. 'fin bref à tester.

Attention cependant: comme tout ce qui est basé sur hashcode, si le contenu de l'objet peut changer après instantiation, alors tout s'effondre...

PS: j'espère que tu as des "synchronized" quelque part dans le code, parce que sinon les perfs ne seront vraiment pas ton plus gros problème...

[thelvin]

Ben l'idée d'un ConcurrentLinkedQueue c'est de pas avoir besoin de synchronized, sinon on utiliserait juste une LinkedList, logique.

Mais du coup pour tester si l'objet était pas déjà là, s'pas évident. Il y aurait moyen de faire ça en utilisant aussi une ConcurrentHashMap (dont on ne se sert que des clés, on associe chaque objet à lui-même,) l'idée étant d'ajouter l'UrlX à la map mais seulement si elle y est pas déjà, et si l'ajout a marché, l'ajouter aussi dans la queue.
En inverse, quand on enlève une UrlX de la queue, on l'enlève de la Map juste après.

[Ceubex]

Merci, j'utilise le ConcurrentHashMap avec l'url en clé en faisant des urlQueue.containsKey(urlString) dessus
ça marche très bien

[thelvin]

Bah non ça marche pas en concurrentiel -_-°.

Même si tu vérifies qu'à un moment m de ton exécution, l'url n'était pas dans la queue, ça veut pas dire pour autant qu'elle n'y est pas venue au moment m+1. Ça n'a aucun sens d'utiliser une ConcurrentHashMap si c'est juste pour appeler containsKey().

[Ceubex]

ben c pas juste pour ça
je fais aussi des put, des remove et des iterations sur cette liste.
containsKey je l'utilise pour voir si j'ai déjà l'objet UrlX