Programmering

Iterering over samlinger i Java

Når som helst du har en samling ting, har du brug for en mekanisme til systematisk at gå igennem elementerne i samlingen. Som et dagligdags eksempel, overvej tv-fjernbetjeningen, som lader os gentage gennem forskellige tv-kanaler. På samme måde har vi i programmeringsverdenen brug for en mekanisme til systematisk at gentage gennem en samling af softwareobjekter. Java indeholder forskellige mekanismer til iteration, herunder indeks (til iterering over en matrix), cursoren (til iterering af resultaterne af en databaseforespørgsel), optælling (i tidlige versioner af Java) og iterator (i nyere versioner af Java).

Iterator-mønsteret

En iterator er en mekanisme, der gør det muligt at få adgang til alle elementer i en samling sekventielt, hvor der udføres en vis operation på hvert element. I det væsentlige giver en iterator et middel til "looping" over en indkapslet samling af objekter. Eksempler på brug af iteratorer inkluderer

  • Besøg hver fil i et bibliotek (aka mappe) og få vist navnet.
  • Besøg hver knude i en graf, og fastslå, om den kan nås fra en given knude.
  • Besøg hver kunde i en kø (for eksempel at simulere en linje i en bank) og find ud af, hvor længe han eller hun har ventet.
  • Besøg hver node i en kompilators abstrakte syntaks træ (som er produceret af parseren) og udfør semantisk kontrol eller kodegenerering. (Du kan også bruge besøgende mønster i denne sammenhæng.)

Visse principper gælder for brug af iteratorer: Generelt skal du være i stand til at have flere gennemgange i gang på samme tid; det vil sige, en iterator skal give mulighed for begrebet indlejret looping. En iterator skal også være ikke-destruktiv i den forstand, at iterationshandlingen ikke i sig selv bør ændre samlingen. Naturligvis kan den operation, der udføres på elementerne i en samling muligvis ændre nogle af elementerne. Det kan også være muligt for en iterator at understøtte fjernelse af et element fra en samling eller indsættelse af et nyt element på et bestemt punkt i samlingen, men sådanne ændringer skal være eksplicitte i programmet og ikke et biprodukt af iterationen. I nogle tilfælde skal du også have iteratorer med forskellige tværgående metoder; for eksempel forudbestilling og efterbestilling af et træ eller dybde-første og bredde-første gennemgang af en graf.

Iterering af komplekse datastrukturer

Jeg lærte først at programmere i en tidlig version af FORTRAN, hvor den eneste datastruktureringskapacitet var en matrix. Jeg lærte hurtigt, hvordan man itererer over en matrix ved hjælp af et indeks og en DO-loop. Derfra var det kun et kort mentalt spring til ideen om at bruge et fælles indeks i flere arrays for at simulere en række poster. De fleste programmeringssprog har funktioner, der ligner arrays, og de understøtter ligetil looping over arrays. Men moderne programmeringssprog understøtter også mere komplekse datastrukturer såsom lister, sæt, kort og træer, hvor kapaciteterne gøres tilgængelige via offentlige metoder, men de interne detaljer er skjult i private dele af klassen. Programmører skal være i stand til at krydse elementerne i disse datastrukturer uden at udsætte deres interne struktur, hvilket er formålet med iteratorer.

Iterators and the Gang of Four design mønstre

Ifølge Gang of Four (se nedenfor), er Iterator design mønster er et adfærdsmønster, hvis hovedidee er "at tage ansvaret for adgang og gennemkørsel ud af listen [red. tænk samling] objekt og læg det i et iteratorobjekt. "Denne artikel handler ikke så meget om Iterator-mønsteret, som det handler om, hvordan iteratorer bruges i praksis. For fuldt ud at dække mønsteret ville det være nødvendigt at diskutere, hvordan en iterator ville blive designet, deltagere ( objekter og klasser) i designet, mulige alternative designs og kompromiser med forskellige designalternativer. Jeg vil hellere fokusere på, hvordan iteratorer bruges i praksis, men jeg vil pege på nogle få ressourcer til at undersøge Iterator-mønsteret og designmønstrene generelt:

  • Designmønstre: Elementer af genanvendelig objektorienteret software (Addison-Wesley Professional, 1994) skrevet af Erich Gamma, Richard Helm, Ralph Johnson og John Vlissides (også kendt som Gang of Four eller simpelthen GoF) er den endelige ressource til at lære om designmønstre. Selvom bogen først blev udgivet i 1994, er den stadig en klassiker, hvilket fremgår af det faktum, at der har været mere end 40 udskrifter.
  • Bob Tarr, en lektor ved University of Maryland Baltimore County, har et fremragende sæt dias til sit kursus om designmønstre, herunder hans introduktion til Iterator-mønsteret.
  • David Gearys JavaWorld-serie Java designmønstre introducerer mange af Gang of Four design mønstre, herunder Singleton, Observer og Composite mønstre. Også på JavaWorld indeholder Jeff Friesens nyere tredelte oversigt over designmønstre en guide til GoF-mønstre.

Aktive iteratorer vs passive iteratorer

Der er to generelle tilgange til implementering af en iterator, afhængigt af hvem der styrer iterationen. Til en aktiv iterator (også kendt som eksplicit iterator eller ekstern iterator), klienten styrer iterationen i den forstand, at klienten opretter iteratoren, fortæller den, hvornår den skal gå videre til det næste element, tester for at se, om hvert element er blevet besøgt osv. Denne tilgang er almindelig på sprog som C ++, og det er den tilgang, der får mest opmærksomhed i GoF-bogen. Selvom iteratorer i Java har taget forskellige former, var brugen af ​​en aktiv iterator i det væsentlige den eneste levedygtige mulighed forud for Java 8.

For en passiv iterator (også kendt som en implicit iterator, intern iterator, eller tilbagekald iterator), kontrollerer iteratoren selv iterationen. Klienten siger i det væsentlige til iteratoren: "Udfør denne handling på elementerne i samlingen." Denne tilgang er almindelig på sprog som LISP, der giver anonyme funktioner eller lukninger. Med udgivelsen af ​​Java 8 er denne tilgang til iteration nu et rimeligt alternativ for Java-programmører.

Java 8 navneskemaer

Selvom det ikke er lige så dårligt som Windows (NT, 2000, XP, VISTA, 7, 8, ...), indeholder Java's versionshistorik flere navngivningsskemaer. For at starte, skal vi henvise til Java-standardudgaven som "JDK", "J2SE" eller "Java SE"? Java's versionsnumre startede ret ligetil - 1.0, 1.1 osv. - men alt ændrede sig med version 1.5, som var mærket Java (eller JDK) 5. Når jeg henviser til tidlige versioner af Java, bruger jeg sætninger som "Java 1.0" eller "Java 1.1, "men efter den femte version af Java bruger jeg sætninger som" Java 5 "eller" Java 8. "

For at illustrere de forskellige tilgange til iteration i Java har jeg brug for et eksempel på en samling og noget, der skal gøres med dens elementer. I den indledende del af denne artikel bruger jeg en samling strenge, der repræsenterer tingene. For hvert navn i samlingen vil jeg blot udskrive dens værdi til standardoutput. Disse grundlæggende ideer udvides let til samlinger af mere komplicerede objekter (såsom medarbejdere), og hvor behandlingen for hvert objekt er lidt mere involveret (som at give hver højt vurderet medarbejder en forhøjelse på 4,5 procent).

Andre former for iteration i Java 8

Jeg fokuserer på iterering over samlinger, men der er andre, mere specialiserede former for iteration i Java. For eksempel kan du bruge en JDBC ResultSet at gentage de rækker, der er returneret fra en SELECT-forespørgsel til en relationsdatabase, eller brug en Scanner for at gentage over en inputkilde.

Iteration med klassen Enumeration

I Java 1.0 og 1.1 var de to primære samlingsklasser Vektor og Hashtable, og Iterator-designmønsteret blev implementeret i en klasse kaldet Optælling. Set i bakspejlet var dette et dårligt navn for klassen. Forveksl ikke klassen Optælling med begrebet enumtyper, der ikke blev vist før Java 5. I dag begge Vektor og Hashtable er generiske klasser, men dengang var generik ikke en del af Java-sproget. Koden til at behandle en vektor af strenge ved hjælp af Optælling ville se ud som Listing 1.

Fortegnelse 1. Brug optælling til at gentage over en vektor af strenge

 Vektornavne = ny vektor (); // ... tilføj nogle navne til samlingen Enumeration e = names.elements (); mens (e.hasMoreElements ()) {String name = (String) e.nextElement (); System.out.println (navn); } 

Iteration med Iterator-klassen

Java 1.2 introducerede de samlingsklasser, som vi alle kender og elsker, og Iterator-designmønsteret blev implementeret i en klasse med passende navn Iterator. Fordi vi endnu ikke havde generiske gener i Java 1.2, kastede vi et objekt returneret fra et Iterator var stadig nødvendigt. For Java-versioner 1.2 til 1.4 kan iterering over en liste over strenge muligvis ligne Listing 2.

Fortegnelse 2. Brug en Iterator til at gentage en liste over strenge

 Liste navne = ny LinkedList (); // ... tilføj nogle navne til samlingen Iterator i = names.iterator (); mens (i.hasNext ()) {String name = (String) i.next (); System.out.println (navn); } 

Iteration med generiske lægemidler og den forbedrede for-loop

Java 5 gav os generiske grænseflader Iterabelog den forbedrede for-loop. Den forbedrede for-loop er en af ​​mine favorit små tilføjelser til Java hele tiden. Oprettelsen af ​​iteratoren og opfordrer til dens hasNext () og Næste() metoder udtrykkes ikke eksplicit i koden, men de finder stadig sted bag kulisserne. Så selvom koden er mere kompakt, bruger vi stadig en aktiv iterator. Ved hjælp af Java 5 ville vores eksempel se ud som det, du ser i Listing 3.

Listing 3. Brug af generics og den forbedrede for-loop til at gentage en liste over strenge

 Liste navne = ny LinkedList (); // ... tilføj nogle navne til samlingen for (String name: names) System.out.println (name); 

Java 7 gav os diamantoperatøren, hvilket reducerer generikernes bredde. Borte var dagene med at skulle gentage den type, der blev brugt til at starte den generiske klasse efter at have påberåbt sig ny operatør! I Java 7 kunne vi forenkle den første linje i liste 3 ovenfor til følgende:

 Liste navne = ny LinkedList (); 

En mild rant mod generiske lægemidler

Udformningen af ​​et programmeringssprog involverer afvejninger mellem fordelene ved sprogfunktioner versus den kompleksitet, de pålægger sprogets syntaks og semantik. For generiske stoffer er jeg ikke overbevist om, at fordelene opvejer kompleksiteten. Generics løste et problem, som jeg ikke havde med Java. Jeg er generelt enig med Ken Arnolds holdning, når han siger: "Generics er en fejltagelse. Dette er ikke et problem baseret på tekniske uenigheder. Det er et grundlæggende sprogdesignproblem [...] Java's kompleksitet er blevet turboladet til det, der synes mig relativt lille fordel. "

Heldigvis, mens design og implementering af generiske klasser undertiden kan være alt for kompliceret, har jeg fundet ud af, at brugen af ​​generiske klasser i praksis normalt er ligetil.

Iteration med metoden forEach ()

Lad os reflektere over, hvad der er galt med koden, der er vist i de forrige oversigter - hvilket er, ja, ikke rigtig noget, før vi går ind i Java 8 iterationsfunktioner. Der er millioner af linjer med Java-kode i aktuelt anvendte applikationer, der bruger aktive iteratorer svarende til dem, der er vist i mine lister. Java 8 giver simpelthen yderligere funktioner og nye måder at udføre iteration på. For nogle scenarier kan de nye måder være bedre.

De vigtigste nye funktioner i Java 8 er centreret om lambda-udtryk sammen med relaterede funktioner såsom streams, metodereferencer og funktionelle grænseflader. Disse nye funktioner i Java 8 giver os mulighed for seriøst at overveje at bruge passive iteratorer i stedet for de mere konventionelle aktive iteratorer. Især den Iterabel interface giver en passiv iterator i form af en standardmetode kaldet for hver().

EN standardmetode, en anden ny funktion i Java 8, er en metode i en grænseflade med en standardimplementering. I dette tilfælde er for hver() Metoden implementeres faktisk ved hjælp af en aktiv iterator på en måde svarende til det, du så i Listing 3.

Samlingsklasser, der implementeres Iterabel (for eksempel alle liste- og sætklasser) har nu en for hver() metode. Denne metode tager en enkelt parameter, der er en funktionel grænseflade. Derfor sendes den aktuelle parameter til for hver() metoden er en kandidat til et lambda-udtryk. Ved hjælp af funktionerne i Java 8 ville vores løbeeksempel udvikle sig til den form, der er vist i Listing 4.

Fortegnelse 4. Iteration i Java 8 ved hjælp af metoden forEach ()

 Liste navne = ny LinkedList (); // ... tilføj nogle navne til samlingens navne. forEach (navn -> System.out.println (navn)); 

Bemærk forskellen mellem den passive iterator i Listing 4 og den aktive iterator i de foregående tre lister. I de første tre lister styrer sløjfestrukturen iteration, og under hver passage gennem sløjfen hentes et objekt fra listen og udskrives derefter. I liste 4 er der ingen eksplicit sløjfe. Vi fortæller simpelthen for hver() metode, hvad man skal gøre med objekterne på listen - i dette tilfælde udskriver vi simpelthen objektet. Kontrol af iteration ligger inden for for hver() metode.

Iteration med Java-streams

Lad os nu overveje at gøre noget lidt mere involveret end blot at udskrive navnene på vores liste. Antag for eksempel, at vi vil tælle antallet af navne, der begynder med brevet EN. Vi kunne implementere den mere komplicerede logik som en del af lambda-udtrykket, eller vi kunne bruge Java 8s nye Stream API. Lad os tage den sidstnævnte tilgang.