streamalism.org

1. Pregled

Ovaj brzi vodič pokazat će kako pronaći razliku između dva niza koristeći Javu.

Za ovaj ćemo vodič koristiti dvije postojeće Java knjižnice i usporediti njihove pristupe ovom problemu.

2. Problem

Razmotrimo sljedeći zahtjev: želimo pronaći razliku između žica “ABCDELMN “i„ ABCFGLMN “.

Ovisno o tome u kojem formatu trebamo biti izlazni, i zanemarujući mogućnost pisanja vlastitog koda za to, pronašli smo dvije glavne opcije na raspolaganju.

Prva je knjižnica koju je napisao Google diff-match-patch. Kako tvrde, knjižnica nudi robusni algoritmi za sinkronizaciju običnog teksta.

Druga opcija je StringUtils razreda iz Apache Commons Lang.

Istražimo razlike između ove dvije.

3. diff-match-patch

U svrhu ovog članka koristit ćemo vilicu izvorne Googleove knjižnice, jer artefakti izvorne biblioteke nisu objavljeni na Maven Central. Također, neka imena klasa razlikuju se od izvorne baze kodova i više se pridržavaju Java standarda.

Prvo, morat ćemo uključiti njegovu ovisnost u našu pom.xml datoteka:

 org.bitbucket.cowwoc diff-match-patch 1.2 

Zatim, razmotrimo ovaj kod:

Tekst niza1 = "ABCDELMN"; Tekst niza2 = "ABCFGLMN"; DiffMatchPatch dmp = novi DiffMatchPatch (); LinkedList diff = dmp.diffMain (text1, text2, false);

Ako pokrenemo gornji kod - koji stvara razliku između tekst1 i tekst2 - ispis varijable razl će proizvesti ovaj izlaz:

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

U stvari, izlaz će biti a popis Diff predmeta, svako biće nastala operacijskim tipom (UMETNUTI, IZBRISATI ili JEDNAK) i dio teksta povezan s operacijom.

Pri pokretanju razlike između tekst2 i tekst1, dobit ćemo ovaj rezultat:

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

4. StringUtils

Razred iz Apache Commons ima pojednostavljeniji pristup.

Prvo ćemo našoj ovisnosti dodati Apache Commons Lang ovisnost pom.xml datoteka:

 org.apache.commons commons-lang3 3.9 

Zatim bismo nazvali kako bismo pronašli razliku između dva teksta s Apache Commons StringUtils # Razlika:

StringUtils.difference (text1, text2)

Rezultat proizvodnje bit će jednostavan niz:

FGLMN

Dok pokretanje razlike između tekst2 i tekst1 će se vratiti:

DELMN

Ovaj jednostavan pristup može se poboljšati pomoćuStringUtils.indexOfDifference (), koji vratit ćeindeks pri kojem se dva niza počinju razlikovati (u našem slučaju četvrti znak niza). Ovaj indeks se može koristiti za dobiti podniz izvornog niza, pokazati ono što je zajedničko između dva ulaza, uz ono što je drugačije.

5. Izvedba

Za naša mjerila generiramo popis od 10.000 nizova s fiksni dio od 10 znakova, nakon čega slijedi 20 slučajnih abecednih znakova.

Zatim prolazimo kroz popis i izvodimo razliku između n-ti element i n + 1 element popisa:

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

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

Na kraju, pokrenimo mjerila i usporedimo dvije knjižnice:

Benchmark Mode Cnt Score Greške Jedinice StringDiffBenchmarkUnitTest.diffMatchPatch avgt 50 130.559 ± 1.501 ms / op StringDiffBenchmarkUnitTest.stringUtils avgt 50 0.211 ± 0.003 ms / op

6. Zaključak

Što se tiče čiste brzine izvršavanja, StringUtils je očito učinkovitiji, iako vraća samo podniz od kojeg se dva niza počinju razlikovati.

U isto vrijeme, Diff-Match-Patch pruža a temeljitiji rezultat usporedbe, na štetu izvedbe.

Implementacija ovih primjera i isječaka dostupna je na GitHubu.