streamalism.org

1. Oversikt

Denne raske opplæringen viser hvordan du gjør det finn forskjellen mellom to strenger bruker Java.

For denne opplæringen skal vi bruke to eksisterende Java-biblioteker og sammenligne deres tilnærminger til dette problemet.

2. Problemet

La oss vurdere følgende krav: vi vil finne forskjellen mellom strengene “ABCDELMN ”og“ ABCFGLMN ”.

Avhengig av hvilket format vi trenger at utdataene skal være, og ignorerer muligheten for å skrive vår tilpassede kode for å gjøre det, fant vi to hovedalternativer tilgjengelig.

Den første er et bibliotek skrevet av Google som heter diff-match-patch. Som de hevder, tilbyr biblioteket robuste algoritmer for synkronisering av ren tekst.

Det andre alternativet er StringUtils klasse fra Apache Commons Lang.

La oss utforske forskjellene mellom disse to.

3. diff-match-patch

For formålet med denne artikkelen vil vi bruke en gaffel med det originale Google-biblioteket, ettersom gjenstandene for den originale ikke blir utgitt på Maven Central. Noen klassenavn er også forskjellige fra den opprinnelige kodebasen og er mer overholdende av Java-standardene.

Først må vi inkludere dens avhengighet i vår pom.xml fil:

 org.bitbucket.cowwoc diff-match-patch 1.2 

La oss så vurdere denne koden:

String text1 = "ABCDELMN"; String text2 = "ABCFGLMN"; DiffMatchPatch dmp = ny DiffMatchPatch (); LinkedList diff = dmp.diffMain (text1, text2, false);

Hvis vi kjører ovennevnte kode - som produserer forskjellen mellom tekst1 og tekst2 - utskrift av variabelen forskjell vil produsere denne utgangen:

[Diff (EQUAL, "ABC"), Diff (DELETE, "DE"), Diff (INSERT, "FG"), Diff (EQUAL, "LMN")]

Faktisk vil produksjonen være en liste over Diff gjenstander, hver og en dannet av en operasjonstype (SETT INN, SLETT eller LIK), og den delen av teksten som er knyttet til operasjonen.

Når du kjører diff mellom tekst2 og tekst1, vi får dette resultatet:

[Diff (EQUAL, "ABC"), Diff (DELETE, "FG"), Diff (INSERT, "DE"), Diff (EQUAL, "LMN")]

4. StringUtils

Klassen fra Apache Commons har en mer forenklet tilnærming.

Først vil vi legge til Apache Commons Lang avhengighet til vår pom.xml fil:

 org.apache.commons commons-lang3 3.9 

Så, for å finne forskjellen mellom to tekster med Apache Commons, vil vi ringe StringUtils # Difference:

StringUtils.difference (text1, text2)

Produksjonen produsert vil være en enkel streng:

FGLMN

Mens du kjører forskjellen mellom tekst2 og tekst1 vil returnere:

DELMN

Denne enkle tilnærmingen kan forbedres ved hjelp avStringUtils.indexOfDifference (), hvilken vil returnereindeks der de to strengene begynner å variere (i vårt tilfelle strengens fjerde tegn). Denne indeksen kan brukes til få en delstreng av den originale strengen, å vise hva som er vanlig mellom de to inngangene, i tillegg til det som er annerledes.

5. Ytelse

For våre referanser genererer vi en liste med 10.000 strenger med en fast porsjon på 10 tegn, etterfulgt av 20 tilfeldige alfabetiske tegn.

Vi går deretter gjennom listen og utfører en forskjell mellom n element og n + 1 element av listen:

@Benchmark public int diffMatchPatch () {for (int i = 0; i <inputs.size () - 1; i ++) {diffMatchPatch.diffMain (inputs.get (i), inputs.get (i + 1), false) ; } returner innganger. størrelse (); }

@Benchmark public int stringUtils () {for (int i = 0; i <inputs.size () - 1; i ++) {StringUtils.difference (inputs.get (i), inputs.get (i + 1)); } returner innganger. størrelse (); }

Til slutt, la oss kjøre referansene og sammenligne de to bibliotekene:

Referansemodus Cnt Score Error Units StringDiffBenchmarkUnitTest.diffMatchPatch avgt 50 130.559 ± 1.501 ms / op StringDiffBenchmarkUnitTest.stringUtils avgt 50 0.211 ± 0.003 ms / op

6. Konklusjon

Når det gjelder ren kjøringshastighet, StringUtils er tydeligvis mer performant, selv om den bare returnerer understrengen som de to strengene begynner å skille seg fra.

Samtidig, Diff-Match-Patch gir en grundigere sammenligningsresultat, på bekostning av ytelse.

Implementeringen av disse eksemplene og utdragene er tilgjengelig på GitHub.