Efficiënte woordfrequentiecalculator in Java

1. Overzicht

In deze tutorial laten we verschillende manieren zien om een ​​woordteller in Java te implementeren.

2. Counter-implementaties

Laten we beginnen met het simpelweg berekenen van het aantal woorden in deze array:

statische tekenreeks [] COUNTRY_NAMES = {"China", "Australië", "India", "VS", "USSR", "VK", "China", "Frankrijk", "Polen", "Oostenrijk", "India" , "VS", "Egypte", "China"}; 

Als we enorme bestanden willen verwerken, moeten we andere opties gebruiken die hier worden beschreven.

2.1. Kaart Met Gehele getallen

Een van de eenvoudigste oplossingen zou zijn om een Kaart, sla woorden op als sleutels en het aantal keren dat ze voorkomen als waarden:

Map counterMap = nieuwe HashMap (); for (String country: COUNTRY_NAMES) {counterMap.compute (country, (k, v) -> v == null? 1: v + 1); } assertEquals (3, counterMap.get ("China"). intValue ()); assertEquals (2, counterMap.get ("India"). intValue ());

We gebruikten gewoon Kaart‘Is handig berekenen methode die de teller verhoogt of initialiseert met 1 als de sleutel niet aanwezig is.

Echter, deze methode om een ​​teller te maken is niet zo efficiënt als Geheel getal is onveranderlijk, dus elke keer dat we de teller verhogen, creëren we een nieuwe Geheel getal voorwerp.

2.2. Stream API

Laten we nu de Java 8 Stream API parallel gebruiken Streams, en de groupingBy() verzamelaar:

@Test openbare leegte whenMapWithLambdaAndWrapperCounter_runsSuccessfully () {Map counterMap = nieuwe HashMap (); Stream.of (COUNTRY_NAMES) .collect (Collectors.groupingBy (k -> k, () -> counterMap, Collectors.counting ()); assertEquals (3, counterMap.get ("China"). IntValue ()); assertEquals (2, counterMap.get ("India"). IntValue ());} 

Evenzo kunnen we een parallelStream:

@Test openbare leegte whenMapWithLambdaAndWrapperCounter_runsSuccessfully () {Map counterMap = nieuwe HashMap (); Stream.of (COUNTRY_NAMES) .parallel () .collect (Collectors.groupingBy (k -> k, () -> counterMap, Collectors.counting ()); assertEquals (3, counterMap.get ("China"). IntValue ( )); assertEquals (2, counterMap.get ("India"). intValue ());} 

2.3. Kaart Met een Geheel getal Array

Laten we vervolgens een Kaart dat een teller wikkelt binnen een Geheel getal array gebruikt als een waarde:

@Test openbare leegte whenMapWithPrimitiveArrayCounter_runsSuccessfully () {Map counterMap = nieuwe HashMap (); counterWithPrimitiveArray (counterMap); assertEquals (3, counterMap.get ("China") [0]); assertEquals (2, counterMap.get ("India") [0]); } private void counterWithPrimitiveArray (Map counterMap) {for (String country: COUNTRY_NAMES) {counterMap.compute (country, (k, v) -> v == null? new int [] {0}: v) [0] ++ ; }} 

Merk op hoe we een simple hebben gemaakt Hash kaart met int arrays als waarden.

In de counterWithPrimitiveArray methode, terwijl we elke waarde van de array herhalen, we:

  • een krijgen op de counterMap door de naam van het land als sleutel door te geven
  • controleer of er al een sleutel aanwezig was of niet. Als de invoer al aanwezig is, maken we een nieuwe instantie van een primitieve integer-array met een enkele "1". Als de invoer afwezig is, verhogen we de tellerwaarde die aanwezig is in de array

Deze methode is beter dan de implementatie van de wrapper - omdat het minder objecten creëert.

2.4. Kaart Met een MutableInteger

Laten we vervolgens een wrapper-object maken dat een primitieve integer-teller insluit, zoals hieronder:

privé statische klasse MutableInteger {int count = 1; public void increment () {this.count ++; } // getter en setter} 

Laten we eens kijken hoe we bovenstaande klasse als teller kunnen gebruiken:

@Test openbare leegte whenMapWithMutableIntegerCounter_runsSuccessfully () {Map counterMap = nieuwe HashMap (); mapWithMutableInteger (counterMap); assertEquals (3, counterMap.get ("China"). getCount ()); assertEquals (2, counterMap.get ("India"). getCount ()); } private void counterWithMutableInteger (Map counterMap) {for (String country: COUNTRY_NAMES) {counterMap.compute (country, (k, v) -> v == null? new MutableInteger (0): v) .increment (); }}

In de mapWithMutableInteger methode, terwijl ze zich herhalen over elk land in de COUNTRY_NAMES array, wij:

  • een beroep doen op de counterMap door de naam van het land als sleutel door te geven
  • controleer of de sleutel al aanwezig is of niet. Als een item ontbreekt, maken we een instantie van MutableInteger waarmee de tellerwaarde wordt ingesteld op 1. We verhogen de tellerwaarde die aanwezig is in de MutableInteger als het land aanwezig is op de kaart

Deze methode om een ​​teller te maken is beter dan de vorige - aangezien we hetzelfde hergebruiken MutableInteger en daardoor minder objecten creëren.

Dit is hoe Apache Collections HashMultiSet werkt waar het een Hash kaart met waarde als MutableInteger intern.

3. Prestatieanalyse

Hier is de grafiek die de prestaties van elke hierboven genoemde methode vergelijkt.

De bovenstaande grafiek is gemaakt met behulp van JMH en hier is de code die de bovenstaande statistieken heeft gemaakt:

Map counterMap = nieuwe HashMap (); Map counterMutableIntMap = nieuwe HashMap (); Map counterWithIntArrayMap = nieuwe HashMap (); Map counterWithLongWrapperMap = nieuwe HashMap (); @Benchmark openbare ongeldige wrapperAsCounter () {counterWithWrapperObject (counterMap); } @Benchmark openbare leegte lambdaExpressionWithWrapper () {counterWithLambdaAndWrapper (counterWithLongWrapperMap); } @Benchmark openbare leegte parallelStreamWithWrapper () {counterWithParallelStreamAndWrapper (counterWithLongWrapperStreamMap); } @Benchmark public void mutableIntegerAsCounter () {counterWithMutableInteger (counterMutableIntMap); } @Benchmark openbare leegte mapWithPrimitiveArray () {counterWithPrimitiveArray (counterWithIntArrayMap); } 

4. Conclusie

In dit korte artikel hebben we verschillende manieren geïllustreerd om woordtellers te maken met Java.

De implementatie van deze voorbeelden is te vinden in het GitHub-project - dit is een op Maven gebaseerd project, dus het zou gemakkelijk moeten kunnen worden geïmporteerd en uitgevoerd zoals het is.