Comment compter le nombre d'occurrences de chaque mot?

Voici une autre façon de le faire avec les choses qui sont apparus dans Java 8:

private void countWords(final Path file) throws IOException {
    Arrays.stream(new String(Files.readAllBytes(file), StandardCharsets.UTF_8).split("\\W+"))
        .collect(Collectors.groupingBy(Function.<String>identity(), TreeMap::new, counting())).entrySet()
        .forEach(System.out::println);
}

Alors, quel est-il?

1. Il lit un fichier texte entièrement en mémoire, dans un tableau d'octets pour être plus précis: Files.readAllBytes(file). Cette méthode se place dans Java 7 et permet aux méthodes de chargement de fichiers très rapide, mais pour le prix que le fichier sera entièrement en mémoire, coûter beaucoup de mémoire. Pour la vitesse c'est cependant une bonne appraoch.
2. Le byte[] est converti en une Chaîne: new String(Files.readAllBytes(file), StandardCharsets.UTF_8) tout en supposant que le fichier est encodé en UTF8. Les modifications sur votre propre besoin. Le prix est plein de copie de mémoire de la déjà énorme morceau de données dans la mémoire. Il peut être plus rapide de travailler avec un fichier mappé en mémoire à la place.
3. La chaîne est divisée en non-Mot charcaters: ...split("\\W+") ce qui crée un tableau de chaînes de caractères avec l'ensemble de vos mots.
4. Nous créer un flux à partir de ce tableau: Arrays.stream(...). Cela, en soi, ne pas faire beaucoup de choses, mais nous pouvons faire beaucoup de choses amusantes avec le flux
5. Nous grouper tous les mots: Collectors.groupingBy(Function.<String>identity(), TreeMap::new, counting()). Cela signifie:
   • Nous voulons grouper les mots par la parole eux-mêmes (identity()). On pourrait aussi par exemple des minuscules à la chaîne ici en premier si vous voulez regrouper pour être sensible à la casse. Ce sera à la fin de la clé dans une carte.
   • Comme un résultat de storng groupées des valeurs que nous voulons un TreeMap (TreeMap::new). Les arborescences sont triés en fonction de leur clé, de sorte que nous pouvons facilement de sortie dans l'ordre alphabétique à la fin. Si vous n'avez pas besoin de tri vous pouvez également utiliser une HashMap ici.
   • Comme valeur pour chaque groupe, nous voulons avoir le nombre d'événements de chaque mot (counting()). En arrière-plan qui signifie que pour chaque mot nous ajouter à un groupe, nous augmenter le compteur par un.
6. À partir de l'Étape 5, nous sommes repartis avec une Carte que les cartes de mots à leur compte. Maintenant, nous voulons simplement de les imprimer. Nous avons donc accès à une collection avec toutes les paires clé/valeur dans cette carte (.entrySet()).
7. Enfin l'impression réelle. Nous disons que chaque élément doit être transmis à la méthode println: .forEach(System.out::println). Et maintenant, vous êtes de gauche avec une belle liste.

Alors, quelle est la qualité de cette réponse? L'avantage est qu'il est très court et donc très expressif. Il devient aussi le long avec un seul appel système qui se cache derrière Files.readAllBytes (ou au moins un nombre fixe je ne suis pas sûr si cela fonctionne vraiment avec un seul appel système) et des appels Système peut être un goulot d'étranglement. E. g. si vous êtes à la lecture d'un fichier à partir d'un flux, chaque appel à lire, qui peut déclencher un appel système. C'est considérablement réduite en utilisant un BufferedReader qui comme son nom l'indique tampons. mais stilly readAllBytes devrait être plus rapide. Le prix pour cela est qu'il consomme d'énormes quantités de mémoire. Cependant wikipedia prétend qu'un livre en anglais a De 500 pages, avec 2 000 caractères par page, ce qui signifie à peu près 1 Mégaoctet qui ne devrait pas être un problème en termes de consommation de mémoire même si vous êtes sur un smartphone, un raspberry pi ou un très très vieil ordinateur.

Ces solutions impliquent certaines optimisations qui n'étaient pas possibles avant Java 8. Par exemple, l'idiome map.put(word, map.get(word) + 1) exige la "parole" à être regardé, twicte dans la carte, ce qui est un gaspillage inutile.

Mais aussi une simple boucle pourrait être plus facile à optimiser pour le compilateur et d'en sauver un certain nombre d'appels de méthode. Donc je voulais savoir et de mettre cela à l'épreuve. J'ai généré un fichier à l'aide de:

[ -f /tmp/random.txt ] && rm /tmp/random.txt; for i in {1..15}; do head -n 10000 /usr/share/dict/american-english >> /tmp/random.txt; done; perl -MList::Util -e 'print List::Util::shuffle <>' /tmp/random.txt > /tmp/random.tmp; mv /tmp/random.tmp /tmp/random.txt

Ce qui me donne un fichier d'environ 1,3 MO, donc pas que atypique pour un livre avec plus de mots d'être répété 15 fois, mais dans un ordre aléatoire pour contourner cette fin jusqu'à être une branche de prédiction de test. Ensuite, j'ai couru les tests suivants:

public class WordCountTest {
@Test(dataProvider = "provide_description_testMethod")
public void test(String description, TestMethod testMethod) throws Exception {
long start = System.currentTimeMillis();
for (int i = 0; i < 100_000; i++) {
testMethod.run();
}
System.out.println(description + " took " + (System.currentTimeMillis() - start) / 1000d + "s");
}
@DataProvider
public Object[][] provide_description_testMethod() {
Path path = Paths.get("/tmp/random.txt");
return new Object[][]{
{"classic", (TestMethod)() -> countWordsClassic(path)},
{"mixed", (TestMethod)() -> countWordsMixed(path)},
{"mixed2", (TestMethod)() -> countWordsMixed2(path)},
{"stream", (TestMethod)() -> countWordsStream(path)},
{"stream2", (TestMethod)() -> countWordsStream2(path)},
};
}
private void countWordsClassic(final Path path) throws IOException {
final Map<String, Integer> wordCounts = new HashMap<>();
for (String word : new String(readAllBytes(path), StandardCharsets.UTF_8).split("\\W+")) {
Integer oldCount = wordCounts.get(word);
if (oldCount == null) {
wordCounts.put(word, 1);
} else {
wordCounts.put(word, oldCount + 1);
}
}
}
private void countWordsMixed(final Path path) throws IOException {
final Map<String, Integer> wordCounts = new HashMap<>();
for (String word : new String(readAllBytes(path), StandardCharsets.UTF_8).split("\\W+")) {
wordCounts.merge(word, 1, (key, oldCount) -> oldCount + 1);
}
}
private void countWordsMixed2(final Path path) throws IOException {
final Map<String, Integer> wordCounts = new HashMap<>();
Pattern.compile("\\W+")
.splitAsStream(new String(readAllBytes(path), StandardCharsets.UTF_8))
.forEach(word -> wordCounts.merge(word, 1, (key, oldCount) -> oldCount + 1));
}
private void countWordsStream2(final Path tmpFile) throws IOException {
Pattern.compile("\\W+").splitAsStream(new String(readAllBytes(tmpFile), StandardCharsets.UTF_8))
.collect(Collectors.groupingBy(Function.<String>identity(), HashMap::new, counting()));
}
private void countWordsStream(final Path tmpFile) throws IOException {
Arrays.stream(new String(readAllBytes(tmpFile), StandardCharsets.UTF_8).split("\\W+"))
.collect(Collectors.groupingBy(Function.<String>identity(), HashMap::new, counting()));
}
interface TestMethod {
void run() throws Exception;
}
}

Le résultat était:

type    length  diff
classic 4665s    +9%
mixed   4273s    +0%
mixed2  4833s    +13%
stream  4868s    +14%
stream2 5070s    +19%

Remarque que j'ai déjà testé aussi avec les Arborescences, mais a constaté que la HashMaps étaient beaucoup plus rapidement, même si j'ai trié la sortie par la suite. Aussi j'ai changé les tests ci-dessus après Tagir Valeev dit moi dans les commentaires ci-dessous sur la Pattern.splitAsStream() méthode. Depuis que je suis variant fortement les résultats que j'ai quitté l'exécution des tests pendant un certain temps comme vous pouvez le voir par la durée en secondes ci-dessus pour obtenir des résultats significatifs.

Comment je juge les résultats:

1. Le "mixte", approche qui n'utilise pas les flux, mais utilise la fonction "fusionner" avec rappel introduit dans Java 8 permet d'améliorer les performances. C'est quelque chose que je m'attendais parce que le classique get/put appraoch nécessite que la clé pour être regardé à deux fois dans la table de hachage et ce n'est plus requis avec la "fusion".

2. À ma grande surprise, le Pattern.splitAsStream() appraoch est en fait plus lentement par rapport à Arrays.asStream(....split()). Je n'ai regarder le code source des deux implémentations et j'ai remarqué que le split() appel enregistre les résultats dans une liste de tableaux qui commence avec une taille de zéro et est élargie en tant que de besoin. Cela nécessite de nombreuses opérations de copie et à la fin d'une autre opération de copie pour copier la liste de tableaux dans un tableau. Mais "splitAsStream" crée un itérateur qui j'ai pensé que peut être interrogé en tant que de besoin à la prévention de ces opérations de copie complètement. Je n'ai pas bien regarder à travers toutes les sources qui convertit l'itérateur à un objet de flux de données, mais il semble être lent et je ne sais pas pourquoi. En fin de compte, il pourrait théoriquement avoir à faire avec la mémoire de l'unité centrale caches: Si exactement le même code est exécuté de plus et une fois de plus le code est plus susceptible d'être dans le cache alors effectivement en cours d'exécution sur une grande chaîne, mais c'est un très sauvage de la spéculation de ma part. Il peut aussi être quelque chose de complètement différent. Cependant splitAsStream POURRAIT ont une meilleure mémoire, peut-être qu'il ne le fait pas, je n'ai pas le profil.

3. Le flux approche en général est assez lent. Ce n'est pas totalement inattendu, car un certain nombre d'invocations de méthode prendre place, y compris, par exemple quelque chose d'aussi inutile que Function.identity. Cependant, je ne m'attendais pas la différence lors de cette ampleur.

Comme une note de côté intéressante je trouve l'approche mixte qui a été le plus rapide assez bien à lire et à comprendre. L'appel à la "fusion" n'est pas le plus ovbious effet sur moi, mais si vous savez ce que cette méthode est en train de faire, il semble plus lisible pour moi, alors que dans le même temps, la groupingBy de commande est plus difficile à comprendre pour moi. Je pense qu'on pourrait être tenté de dire que cette groupingBy est si spécial et hautement optimisé qu'il est logique de l'utiliser pour la performance, mais comme démontré ici, ce n'est pas le cas.

OriginalL'auteur yankee

Si j'étais vous, je voudrais utiliser l'une des implémentations de map<String, int>, comme une table de hachage. Alors que vous parcourez chaque mot s'il existe déjà juste incrémenter le type int par un, sinon l'ajouter dans la carte. À la fin, vous pouvez sortir tous les mots, ou de la requête sur la base d'un mot spécifique pour obtenir le nombre.

Si l'ordre est important pour vous, vous pouvez essayer un SortedMap<String, int> pour être en mesure de pring dans l'ordre alphabétique.

Espère que ça aide!

OriginalL'auteur Jared Wadsworth