juillet
2012
Un article de thierryler
Commentaires fermés Quand on a des listes très grosses et qu’on recherche un élément précis, ça peut prend beaucoup de temps. Souvent, ce qui nous intéresse, c’est juste de savoir si l’élément en question est déjà dans la liste.
Prenons un exemple avec une liste de chiens :
1 2 3 4 5 6 7 8 9 10 | int NB_OF_DOGS = 100000; List<Dog> dogs = newArrayList(); Random rand = new Random(); for (int i = 0; i < NB_OF_DOGS; i++) { Dog dog = new Dog(); dog.setName("abc" + rand.nextInt(999)); ... dogs.add(dog); } |
Disons qu’on recherche si Milou est dans la liste :
1 2 3 4 5 | final Dog milou = new Dog(); milou.setName("Milou"); ... boolean isInList = dogs.contains(milou); |
La recherche donne une résultat négatif, en 13 millisecondes environ. C’est super long 
Mais ajoutons donc Milou à la liste pour voir ce que ça donne :
1 2 3 | dogs.add(milou); boolean isInList = dogs.contains(milou); |
Bon, je triche un peu puisque Milou se retrouve à la fin, mais toujours est-il que c’est pile poil la situation la plus courante. Cette fois, la recherche donne un résultat positif mais toujours en autant de temps
Heureusement, Guava propose les Bloom Filter depuis la version 13.0 :
1 2 3 4 5 6 7 8 | Funnel<Dog> dogFunnel = new Funnel<Dog>() { public void funnel(Dogdog, PrimitiveSink sink) { sink.putString(dog.getName()) .putString(dog.getFullName()) .putString(dog.getRace()); }}; BloomFilter<Dog> bloom = BloomFilter.create(dogFunnel, NB_OF_DOGS, 0.01); |
Ici je défini un « bloom » qui possède une probabilité de « 0.01 » de donner un faux positif et une proba de « 1 » (ie. 100%) de donner un vrai négatif. Ça veut dire que le bloom va répondre « true » à tord dans 1% des cas. Par contre, il ne se trompera jamais quand il répondra « false », cf. plus bas.
Evidemment, il faut ajouter les chiens au bloom :
1 2 3 4 | for (int i = 0; i < NB_OF_DOGS; i++) { ... dogs.add(dog); bloom.put(dog); |
Maintenant, on va demander si Milou est bien présent, ou plutôt s’il est probable qu’il soit présent.
1 | boolean isInList = bloom.mightContain(milou); |
Ça dit que Milou n’est pas présent, en 0ms (zéro).
Ajoutons Milou pour voir ce que ça donne :
1 2 3 | bloom.put(milou); boolean isInList = bloom.mightContain(milou); |
Cette fois, le bloom dit que Milou est probablement présent, avec une proba d’erreur de 1%, et en 0ms. C’est donc très rapide.
En changeant le nombre de chiens dans la liste, je monte à 42ms de recherche pour un million de chien avec la méthode classique, et toujours 0ms à l’aide du bloom.
Alors, cette technique n’a d’intérêt que lorsqu’on travaille sur des listes conséquentes. Le tout est de savoir à partir de quand une liste est conséquente.
Commentaires récents
- dans Le Stop watch de Guava
- dans Le Stop watch de Guava
- dans Le Stop watch de Guava