Discussion :

[Sharcoux]

Bonjour,

Voilà mon problème :

J'ai dans un fichier txt une liste de 300 000 mots classés par ordre alphabétique à raison d'un mot par ligne (environ 3Mo).

Mon programme va faire régulièrement des recherches dans cette liste (uniquement des requêtes de type "contains(String s)")

Quelle est la meilleure manière d'implémenter cette liste pour garantir une rapidité d'exécution sous Android ?

J'ai pensé à un SortedSet, mais ça a l'air déjà trop lourd. Ou alors il ne faut pas instancier mais rechercher directement dans le fichier brut? Mais ça signifie qu'il va falloir parcourir le fichier un grand nombre de fois, et vu sa taille...

Des idées ?

[Simon MARQUIS]

Il existe une structure de données faite pour ça (et que j'ai déjà pratiqué).
Il s'agit du Patricia Tree ou du Radix Tree

[tchize_]

Si tu peux te permettre de le tenir en mémoire et comme le fichier est déjà trié, un simple String[] dans lequel tu fais une recherche dicothomique pourrait suffire. Ca nécessiterait que 19 comparaisons de Strings pour un contains(), ce qui est raisonnable si tu ne fait pas 500.000 recherches

[Sharcoux]

Merci pour vos idées.
Je ne connaissais pas du tout Radix tree.

En fait, pour la recherche, le SortedSet ça passe bien (très rapide).

Pour la conservation en mémoire, c'est déjà un peu un problème. J'utilise ceci pour un clavier. Est-ce que je peux décemment garder l'instance de mon dictionnaire en mémoire entre deux utilisation du clavier. Si oui, comment ? Est-ce que le String[] offrirait de meilleurs performances dans ce cas?

Enfin, le vrai problème, c'est l'instanciation. De ce point de vue, le radix tree offrira probablement des performances execrables. Est-ce que vous connaissez un code efficace pour lire mes 300 000 lignes et les mettre dans mon sortedSet (ou autre) ? Est-ce que je pourrais envisager de faire un thred séparé pour faire cette opération sans trop perturber l'utilisateur (gros temps de chargement). Je n'ai encore jamais touché au multiThread...

[hotcryx]

300.000 lignes c'est costaud.
Et le tenir en mémoire, c'est énorme (au moins 1 Mb).
Je te conseillerai plus un accès db mais les full table scan ne sont jamais bons pour les processeurs.
Oui, tu devrais utiliser des tâches asynchrones, thread...

[tchize_]

en tout cas, un SortedSet occupera beaucoup plus de mémoire qu'un String[], combien, ça dépendra de l'implémentation, mais si on prend la base d'un TreeSet ça risque d'être très gourmand avec tous les objets servants juste à l'organisation de l'arbre.

[Sharcoux]

Ok. J'ai fait un thread séparé. Le résultat est pas trop mal.

Oui, j'avais utilisé un TreeSet. Tu as raison, je vais utiliser une String[].

Comment je peux faire pour la garder en mémoire même après la fermeture du clavier ?

Merci encore pour votre aide