Ohjelmointi

Lankojen käyttäminen kokoelmien kanssa, osa 1

Viestiketjut ovat olennainen osa Java-kieltä. Lankoja käyttämällä moniin algoritmeihin, kuten jononhallintajärjestelmiin, on helpompi päästä kuin he käyttävät kysely- ja silmukointitekniikoita. Viime aikoina kirjoittaessani Java-luokkaa huomasin, että minun tarvitsi käyttää ketjuja luetteloita luetellessani, ja tämä paljasti joitain mielenkiintoisia aiheita, jotka liittyivät ketjutietoisiin kokoelmiin.

Tämä Java syvyydessä -sarakkeessa kuvataan ongelmat, jotka paljastin yrittäessäni kehittää langattomia kokoelmia. Kokoelmaa kutsutaan "langattomaksi", kun useat asiakkaat (ketjut) voivat käyttää sitä turvallisesti samanaikaisesti. "Joten mikä on ongelma?" kysyt. Ongelmana on, että tavallisessa käytössä ohjelma muuttaa molemmat kokoelmaa (kutsutaan mutaatio) ja lukee sen (kutsutaan luetellaan).

Jotkut ihmiset eivät yksinkertaisesti rekisteröi lausetta "Java-alusta on monisäikeinen". Toki he kuulevat sen ja nyökkäävät päätään. Mutta he eivät ymmärrä, että toisin kuin C tai C ++, joissa kierteitys ruuvattiin sivulta käyttöjärjestelmän kautta, Java-ketjut ovat peruskielirakenteita. Tämä väärinkäsitys tai huono käsitys Java-luonteen kierteellisestä luonteesta johtaa väistämättä kahteen yleiseen virheeseen ohjelmoijien Java-koodissa: Joko he eivät ilmoita menetelmää synkronoituna, koska sen pitäisi olla (koska esine on epäjohdonmukaisessa tilassa menetelmän suorittaminen) tai he julistavat menetelmän synkronoituksi sen suojaamiseksi, mikä saa muun järjestelmän toimimaan tehottomasti.

Törmäsin tähän ongelmaan, kun halusin kokoelman, jota useat ketjut voisivat käyttää estämättä tarpeettomasti muiden ketjujen suorittamista. Mikään JDK: n 1.1-version kokoelmaluokista ei ole langankestävä. Yksikään kokoeluluokista ei salli sinun luetella yhtä säiettä samalla kun mutatoituu toisen kanssa.

Langattomia kokoelmia

Perusongelmani oli seuraava: Olettaen, että sinulla on järjestetty objektikokoelma, suunnittele Java-luokka siten, että säie voi luetella koko kokoelman tai osan siitä huolimatta siitä, että luettelo ei kelpaa muiden kokoelmaa muuttavien säikeiden vuoksi. Harkitse esimerkkinä ongelmaa Java Vektori luokassa. Tämä luokka ei ole langattomasti turvallinen ja aiheuttaa monia ongelmia uusille Java-ohjelmoijille, kun he yhdistävät sen monisäikeiseen ohjelmaan.

Vektori luokka tarjoaa erittäin hyödyllisen mahdollisuuden Java-ohjelmoijille: nimittäin dynaamisesti kokoinen joukko esineitä. Käytännössä voit käyttää tätä toimintoa tulosten tallentamiseen, kun käsittelemiesi objektien lopullinen määrä ei ole tiedossa, ennen kuin olet valmis niiden kanssa. Rakensin seuraavan esimerkin tämän käsitteen havainnollistamiseksi.

01 tuo java.util.Vector; 02 tuonti java.util.Laskenta; 03 julkisen luokan esittely {04 public static void main (String args []) {05 Vektorin numerot = uusi vektori (); 06 int tulos = 0; 07 08 if (args.pituus == 0) {09 System.out.println ("Käyttö on java-demo 12345"); 10 System.exit (1); 11} 12 13 (int i = 0; i = '0') && (c <= '9')) 16 numeroa. AddElement (uusi kokonaisluku (c - '0')); 17 muuta 18 taukoa; 19} 20 System.out.println ("On" + numeroa. Koko () + "numeroa."); 21 for (Luku e = numerot.elements (); e.hasMoreElements ();) {22 tulos = tulos * 10 + ((Kokonaisluku) e.nextElement ()). IntValue (); 23} 24 System.out.println (argumentit [0] + "=" + tulos); 25 System.exit (0); 26} 27} 

Yllä olevassa yksinkertaisessa luokassa käytetään a Vektori objekti kerätä numeromerkkejä merkkijonosta. Kokoelma lasketaan sitten merkkijonon kokonaisluvun laskemiseksi. Tässä luokassa ei ole mitään vikaa paitsi, että se ei ole langankestävä. Jos toisessa säikeessä sattui viittaus numeroa vektori ja että säie lisäsi uuden merkin vektoriin, silmukan tulokset yllä olevilla viivoilla 21 - 23 olisivat arvaamattomia. Jos lisäys tapahtui ennen kuin luettelo-objekti oli ohittanut lisäyskohdan, ketju laskee tulos käsittelisi uuden merkin. Jos lisäys tapahtui sen jälkeen, kun luettelo oli ohittanut lisäyskohdan, silmukka ei käsittele merkkiä. Pahimmassa tapauksessa skenaario saattaa heittää a NoSuchElementException jos sisäinen luettelo olisi vaarantunut.

Tämä esimerkki on juuri se - keksitty esimerkki. Se osoittaa ongelman, mutta kuinka suuri on mahdollisuus, että toinen säike toimii lyhyen viiden tai kuusinumeroisen luettelon aikana? Tässä esimerkissä riski on pieni. Aika, joka kuluu, kun yksi säie aloittaa vaarassa olevan operaation, joka tässä esimerkissä on luettelo, ja suorittaa tehtävän loppuun, kutsutaan ketjun haavoittuvuusikkunatai ikkuna. Tämä ikkuna tunnetaan nimellä rodun kunto koska yksi ketju on "kilpaillut" tehtävänsä loppuun saattamiseksi ennen kuin toinen ketju käyttää kriittistä resurssia (luettelo numeroista). Kuitenkin, kun aloitat kokoelmien käytön edustamaan useita tuhansia elementtejä sisältävää ryhmää, kuten tietokannan kanssa, haavoittuvuusikkuna kasvaa, koska säikeiden luettelointi viettää paljon enemmän aikaa luettelointisilmukassaan, mikä antaa mahdollisuuden uudelle ketjulle paljon korkeampi. Et todellakaan halua jonkun muun säikeen muuttavan alla olevaa luetteloa! Haluat vakuutuksen siitä, että Luettelointi esine, jota pidät, on kelvollinen.

Yksi tapa tarkastella tätä ongelmaa on huomata, että Luettelointi objekti on erillään Vektori esine. Koska he ovat erillisiä, he eivät pysty säilyttämään hallintaa toistensa suhteen, kun ne on luotu. Tämä löysä sidonta ehdotti minulle, että ehkä hyödyllinen polku tutkittavaksi oli luettelo, joka oli tiukemmin sidottu sitä tuottaneeseen kokoelmaan.

Kokoelmien luominen

Tarvitsin ensin kokoelman, jotta voisin luoda langankestävän kokoelmani. Minun tapauksessani tarvittiin lajiteltu kokoelma, mutta en vaivautunut kulkemaan koko binääripuun reittiä. Sen sijaan loin kokoelman, jota kutsuin nimellä Synkronointiluettelo. Tässä kuussa tarkastelen SynchroList-kokoelman ydinelementtejä ja kuvaan kuinka sitä käytetään. Ensi kuussa osassa 2 otan kokoelman yksinkertaisesta, helposti ymmärrettävästä Java-luokasta monimutkaiseen monisäikeiseen Java-luokkaan. Tavoitteenani on pitää kokoelman suunnittelu ja toteutus selkeänä ja ymmärrettävänä suhteessa tekniikoihin, joita käytetään sen tekemiseen lankatietoisuuteen.

Nimesin luokkani Synkronointiluettelo. Nimi "SynchroList" tulee tietysti "synkronoinnin" ja "luettelon" ketjutuksesta. Kokoelma on yksinkertaisesti kaksinkertaisesti linkitetty luettelo, kuten saatat löytää mistä tahansa korkeakouluopetuksen ohjelmoinnista, vaikka käyttämällä sisäistä luokkaa nimeltä Linkki, voidaan saavuttaa tietty eleganssi. Sisempi luokka Linkki määritellään seuraavasti:

 luokka Linkki {yksityisten objektien tiedot; yksityinen linkki nxt, prv; Linkki (objekti o, linkki p, linkki n) {nxt = n; prv = p; data = o; jos (n! = null) n.prv = tämä; jos (p! = null) p.nxt = tämä; } Object getData () {palautustiedot; } Linkki seuraava () {return nxt; } Linkki seuraava (Linkitä uusiSeuraava) {Linkki r = nxt; nxt = uusiSeuraava; return r;} Linkki edellinen () {return prv; } Linkin edellinen (Link newPrev) {Linkki r = prv; prv = uusiPrev; return r;} public String toString () {return "Linkki (" + data + ")"; }} 

Kuten yllä olevasta koodista näet, a Linkki object kiteyttää linkityskäyttäytymisen, jota luettelo käyttää objektien järjestämiseen. Kaksinkertaisesti linkitetyn luettelokäyttäytymisen toteuttamiseksi objekti sisältää viitteet sen dataobjektiin, viittauksen ketjun seuraavaan linkkiin ja viittauksen ketjun edelliseen linkkiin. Lisäksi menetelmät Seuraava ja edellinen ovat ylikuormitettuja tarjoamaan keinon päivittää objektin osoitin. Tämä on tarpeen, koska vanhempaluokan on lisättävä ja poistettava linkkejä luetteloon. Linkkirakentaja on suunniteltu luomaan ja lisäämään linkki samanaikaisesti. Tämä tallentaa menetelmän kutsun luettelon toteutukseen.

Luettelossa käytetään toista sisäluokkaa - tässä tapauksessa nimettyä luetteloluokkaa ListEnumerator. Tämä luokka toteuttaa java.util.Laskenta käyttöliittymä: vakiomekanismi, jota Java käyttää toistamaan objektikokoelman. Kun laskijamme toteuttaa tämän käyttöliittymän, kokoelmamme on yhteensopiva kaikkien muiden Java-luokkien kanssa, jotka käyttävät tätä rajapintaa kokoelman sisällön luettelointiin. Tämän luokan toteutus näkyy alla olevassa koodissa.

 class LinkEnumerator toteuttaa Enumeration {private Link current, previous; LinkEnumerator () {current = pää; } public boolean hasMoreElements () {return (current! = null); } public Object nextElement () {Objektin tulos = null; Linkki tmp; if (nykyinen! = null) {tulos = nykyinen.getData (); virta = virta.seuraava (); } palautustulos; }} 

Nykyisessä inkarnaatiossaan LinkEnumerator luokka on melko suoraviivainen; se muuttuu monimutkaisemmaksi, kun muokkaamme sitä. Tässä inkarnaatiossa se yksinkertaisesti kävelee kutsuvan objektin luettelon läpi, kunnes se tulee sisäisen linkitetyn luettelon viimeiseen linkkiin. Kaksi menetelmää, joita tarvitaan java.util.Laskenta käyttöliittymä ovat hasMoreElements ja seuraavaElement.

Tietenkin yksi syy siihen, miksi emme käytä java.util. vektori luokka johtuu siitä, että minun piti lajitella kokoelman arvot. Meillä oli valinta: rakentaa tämä kokoelma erityiseksi tietyntyyppiselle objektille, käyttämällä objektityypin läheistä tietoa lajittelemiseksi tai luomaan yleisempi rajapintoihin perustuva ratkaisu. Valitsin jälkimmäisen menetelmän ja määrittelin käyttöliittymän nimeltä Vertailija kapseloida tarvittavat menetelmät kohteiden lajittelemiseksi. Tämä käyttöliittymä on esitetty alla.

 julkinen käyttöliittymä Vertailija {public boolean lessThan (Object a, Object b); julkinen totuusarvo suurempi kuin (Object a, Object b); julkinen totuusarvo equTo (Object a, Object b); void typeCheck (Object a); } 

Kuten yllä olevasta koodista näet, Vertailija käyttöliittymä on melko yksinkertainen. Rajapinta vaatii yhden menetelmän kullekin kolmesta vertailutoiminnosta. Tämän käyttöliittymän avulla luettelo voi verrata lisättäviä tai poistettavia objekteja jo luettelossa oleviin objekteihin. Lopullinen menetelmä, typeCheck, käytetään kokoelman tyypin turvallisuuden varmistamiseen. Kun Vertailija objektia käytetään, Vertailija voidaan käyttää varmistamaan, että kokoelman objektit ovat kaikki samantyyppisiä. Tämän tyyppisen tarkistuksen arvo on, että se säästää sinua näkemästä objektien suoratoistoa koskevia poikkeuksia, jos luettelossa oleva objekti ei ollut odotettua tyyppiä. Minulla on myöhemmin esimerkki, joka käyttää a Vertailija, mutta ennen kuin pääsemme esimerkkiin, katsotaanpa Synkronointiluettelo luokan suoraan.

 public class SynchroList {class Link {... tämä näytettiin yllä ...} class LinkEnumerator toteuttaa luettelon {... the enumerator class ...} / * Objekti elementtien vertailemiseksi * / Comparator cmp; Linkki pää, häntä; public SynchroList () {} public SynchroList (vertailija c) {cmp = c; } private void before (Object o, Link p) {new Link (o, p.prev (), p); } private void jälkeen (Object o, Link p) {new Link (o, p, p.sext ()); } private void remove (Linkki p) {if (p.prev () == null) {head = p.sext (); (p. seuraava ()). prev (nolla); } else if (p.sext () == null) {tail = p.prev (); (p.prev ()). seuraava (nolla); } else {p.prev (). seuraava (p.sext ()); p.sext (). prev (p.prev ()); }} public void add (Object o) {// jos cmp on tyhjä, lisää aina luettelon hännään. if (cmp == null) {if (head == null) {head = uusi Linkki (o, null, null); pyrstö = pää; } else {tail = uusi linkki (o, tail, null); } paluu; } cmp.typeCheck (o); if (head == null) {head = uusi linkki (o, null, null); häntä = pää; } else if (cmp.lessThan (o, head.getData ())) {head = uusi linkki (o, null, head); } muu {Linkki l; for (l = pää; l.seuraava ()! = null; l = l.seuraava ()) {if (cmp.lessThan (o, l.getData ())) {ennen (o, l); palata; }} tail = uusi linkki (o, tail, null); } paluu; } public boolean delete (Object o) {if (cmp == null) return false; cmp.typeCheck (o); for (Linkki l = pää; l! = null; l = l.seuraava ()) {if (cmp.equalTo (o, l.getData ())) {poista (l); palaa tosi; } if (cmp.lessThan (o, l.getData ())) rikkoutuu; } return false; } julkiset synkronoidut luetteloelementit () {return new LinkEnumerator (); } julkinen int-koko () {int tulos = 0; (Linkki l = pää; l! = null; l = l.seuraava ()) tulos ++; paluutulos; }}