Abstraktit tietorakeneet Jono ja Pino Pythonilla&Javalla - Kommentteja kaipaan

[Jere Sumell]

Ohjelmoin tänään aikani kuluksi Pythonissa ja Javassa abstraktit tietorakenteet Jono ja Pino. Kaipaisin jotain kommenttia, jos joku voisi katsoa koodit läpi, ja tehdä jonkin huomautuksen, jos löytyy jotain silmiin pistävää virhettä.

Suora linkki Github Data Structures -repooni, jonka loin noita varten

https://github.com/jjsume/DataStructures

Tuossahan on nyt demonstraatio-ohjelmassa pinossa ja jonossa Integer-tietotyypin olioita muistipaikkoihin viittauksia, mitä lisäillään ja poistellaan noista rakenteista, ja pystyy seuraamaan listan kehitystä lisäys ja poistovaiheissa askel kerrallaan, opetusohjelma -näkökulmasta, mutta voihan ne olla käytännössä mitä olioita tahansa pienellä muokkauksella.

Miten muuten, kun nyt minulla on sisältöä jonossa ja pinossa, pitäisi lajitella seuraavaksi, jonka jälkeen pitäisi varmaankin leveyshaku ohjelmoida. Javassahan on Java 8:n API:sta katsoin, niin java.util -paketin tarjoama Arrays-tietotyypin toimintometodi .sort -joka tuon APIn informatiivisen kuvauksen mukaan perustuu timPetersin Tim Petersin kehittämään TimSort -lajittelualgoritmiin, joka perustuu tekniikkaan vuodelta 1993 esitettyyn jossain konferenssissa epäilisin.

Joku kommentoi Ohjelmointiputkassa, kun kysyin lomittelulajittelusta (merge sort), kun se ratkeaa logaritmisessa ajassa, mitä tulee algoritmin aikakompleksisuuteen, niin tuo TimSort olisi jokin sovellus tuosta mergesortista, ja joissain tilanteissa suoriutuisi jopa nopeammin. Javalla lienee järkevintä käyttää sitä, että ei lähde lajittelualgoritmiä itse kehittelemään? Lomituslajittelun itse ohjelmointi vaikuttaa tuon dokumentaation luettuani pyörän keksimiseltä uudestaan?

No ehkä lajittelun saan noissa tietorakenteissani kuntoon lomituslajittelun menetelmin, mutta entäs sitten tietyn muistipaikkaviittaus-päässä olevan olion löytäminen mahdollisimman nopeasti? Äärellinen hakuavaruus, ja leveyshaku lienee järkevin tapa toteuttaa se, jollei sitten käytä jotain sääntöjä, miten lajittelee järjestykseen nuo kokonaisluku-olio-muistipaikkaviittaukset. Javassa taitaa olla valmiina jo tähänkin ratkaisut?

Onko jollakulla sanoa varmana, kun en ole Pythonin dokumentaatiota lukenut listojen osalta, että mitä lajittelualgoritmiä ja hakualgoritmiä Python 3 käyttää Array -ilmentymien osalta?

https://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html#sort-T:A-int-int-java.util.Comparator-

[Lepotila zZ]

Pythonissa ei ole varsinaisia taulukoita. Pythonin listat vastaavat pikemminkin Javan ArrayList-tietorakennetta. Jos haluaa käyttää oikeita taulukoita Python ohjelmassa, Numpy-kirjasto on varmaankin yleisin ratkaisu. Siinä voi valita useamman järjestämisalgoritmin väliltä, mutta oletuksena siinä käytetään pikajärjestämistä.

Listojen järjestäminen on hoidettu Pythonissa Timsortilla. Tim Peters toteutti sen Pythoniin. Sen jälkeen sitä on kopioitu muualle kuten Javaan. Ilmeisesti se on erittäin hyvä vakaa järjestämisalgoritmi.

[Jere Sumell]

Kiitos vastauksesta, lepotilazZ,

Tuosta selvisikin tuosta Java 8 -API -dokumentaatiosta, että Peters kehittänyt Pythonilla sen, joten lienee selvä, että se on otettu käyttöön Pythonissa kehitysversioiden kehittymisen myötä viimeistään, kun se on todettu vakaaksi ja nopeaksi lajittelualgoritmiksi.

Tuntuu siltä, vaikka aineopinnoissa olen maisterilinjalla tekniikan laitoksella, että jotta voisi ottaa kantaa esimerkiksi tämän Tim Petersin lajittelualgoritmiin, pitäisi opiskella lisää, mahdollisesti olla computer sciences tai tietojenkäsittelytieteen tohtorin tutkinnon ensin suorittaa matematiikka pitkänä sivuaineena ja algoritmiteoriaan perehtyä niin paljon, että voisi jotain kantaa ottaa sillä tavalla siihen esimerkiksi, että sillä olisi jotain laajempaa yleisöä, kuuluvuutta, vaikka sitten olisikin 50-vuotiaana valmistuisi ja ei koskaan elinaikanaan saisi tietokonetieteiden tai tietojenkäsittelytieteiden professorin oppituolia oppilaitoksestaan? Tuntuu myös siltä, että näistä norsunluutornin tutkijat tietojenkäsittelytieteissä vääntävät kättä päivätöikseen?

Nyt maisterin tutkinto loppuun tietojenkäsittelytieteissä, tekniikassa, tai luonnontieteissä, mikä se virallinen oppiarvo on , mutta vielä ei ole tullut kommentteja tuohon alkuperäiseen kysymykseeni, että onko noissa jono ja pino -tietotyypeissäni jotain silmiin pistävää kommentoitavaa?

Akateemisessa tietojenkäsittelymaailmassa maisterin tutkinto käsittääkseni antaisi loppuun suoritettuna ihan kohtalaisen näköala-paikan oman oppialan seuraamiselle ja kehityksen seuraamiselle, kun gradussakaan tarvitse vielä mitään uutta löytää omasta aiheesta, kuten ei kanditutkielmassakaan, vaikka siinä mitataan opiskellun tiedon soveltamista itse tehtyihin johtopäätöksiin omasta aiheesta jotakuinkin syvälle mennen johonkin aiheeseen perehtymisen jälkeen.

[Lepotila zZ]

Pienenä tarkennuksena: Vakaalla en tarkoittanut varmatoimista. Englanninkielessä käytetään termiä "stable". Wikipediaa lainaten: "Vakaa (stabiili) lajittelualgoritmi ei vaihda keskenään samansuuruisten alkioiden suhteellista järjestystä, kun taas epävakaa saattaa niin tehdä." Tällä on joskus merkitystä, kun järjestettävillä elementeillä on muitakin ominaisuuksia kuin se, jota käytetään järjestämisen perusteena. Luulisin, että Timsortia käytetään Javassa olioiden järjestämiseen nimenomamaan tämän ominaisuuden vuoksi. Alkeistyyppejä sisältävien taulukoiden (array) järjestämiseen käytetään sen sijaan pikajärjestämistä, joka ei ole vakaa. Alkeistyyppien järjestämisessä vakaudella ei ole merkitystä, ja pikajärjestäminen on jonkin verran tehokkaampaa.

En ole ohjelmoija enkä tunne lainkaan Pythonin tai Javan tyylisuosituksia. En halua siis kommentoida niitä. Toiminnallisuuden suhteen: jos koodi tekee sen, mitä sinä sen haluat tekevän, kaikki on hyvin.

Sinänsä turha huomio, koska suorituskyvyllä ei ole sovelluksessasi merkitystä: Pythonin lista on tehoton tietorakenne jonon perustaksi, koska elementtien poistaminen sen alkupäästä on hyvin tehotonta. Pythonissa on sitä varten tehokkaampi deque-luokka, jossa poistot kummasta tahansa päästä sujuvat vakioajassa (kuten myös lisäykset kumpaan päähän tahansa). En tunne Javaa siinä määrin, mutta luultavasti myös sen ArrayList-olioilla on yhtälailla tehotonta poistaa listan alusta. Voi tietenkin harkita jonon toteuttamista Pythonin listaa tai Javan ArayListia käyttäen, mutta siten, että poistot suoritettaisiin vakioajassa. Se olisi tietenkin monimutkaisempi kuin nykyinen toteutuksesi.

[Jere Sumell]

Hienoa, että sulla on tietoa tuosta "epävarma", ja "varma" -vastakohtana -termeistä tässä tietojenkäsittelykonteksista ja Pythonista nimeomaan, itsekään ole vielä edes maisteri, joten on jotain kosketuspintaa ainoastaan.

Katsoin Googlen hakutermillä tuota "Tim Peters" -ensimmäistä kerta etenkin eilisen ohjelmointipäivärutiinini jäljiltä, ja siellähän yksi hakuehdotus viittaa mieheen itseensä, eli "Tim Peter Python". Katsoin sitä siis, mutta selvisi, että mies työskentelee ohjelmistokehittäjänä Amerikan Yhdysvalloissa.

Mitä itsestäni piti tulla humaanilta pohjiltiani runoilija, niin siellähän Python viittaa brittikasvatukseen kielen osalta Monty Pythonin huumoriin lopulta, mitä olet Monty Pythonia ehkä varttuneemmallakin iällä katsonut, epäilen että olet, niin seurannut. Sitcom-vicahteita viitaten muiden foorumeiden postauksiini, mutta kyllä Monty Python on ykkönen ja toimi ykkösenä myös ehkä nykyaikaisen Putous - sketsiviihteen mitä niitä oli Peteliuksen firman Pulttibois ja sen jälkeen kun ensin pultit oli vedetty pois niin ManiBois, ja Tabuhan edelsi jo sitä ja moni muu ennen  niitä...

Tim Peter's Googlesta ja hakuehdotuksista "Tim Peter's Python", mikä tuli viimeisenä, tulenhan itsekkin niissä jo, jos pistää pari ekaa kirjainta, Peters teki jotain uraa uurtavaa, nyt tuntuu siltä.

[nm]

Ohjelmoin tänään aikani kuluksi Pythonissa ja Javassa abstraktit tietorakenteet Jono ja Pino. Kaipaisin jotain kommenttia, jos joku voisi katsoa koodit läpi, ja tehdä jonkin huomautuksen, jos löytyy jotain silmiin pistävää virhettä.

Javassa on yleiset interfacet Deque ja Queue, joita kannattaisi noudattaa myös omissa toteutuksissa. Yleiskäyttöisyyden vuoksi on syytä käyttää myös geneeristä tyypitystä (generics) aina kuin suinkin mahdollista.

Toisaalta Javassa on jo useita valmiita virallisia toteutuksia perustuen listoihin ja dynaamisiin taulukoihin, joten näitäkään pyöriä ei kannata keksiä uudelleen muuten kuin opiskelumielessä. Deque ja Queue -rajapintojen dokumentaatiossa on linkit näihin toteutuksiin. Esimerkiksi LinkedList ja PriorityQueue toteuttavat Queue-rajapinnan.

No ehkä lajittelun saan noissa tietorakenteissani kuntoon lomituslajittelun menetelmin, mutta entäs sitten tietyn muistipaikkaviittaus-päässä olevan olion löytäminen mahdollisimman nopeasti? Äärellinen hakuavaruus, ja leveyshaku lienee järkevin tapa toteuttaa se, jollei sitten käytä jotain sääntöjä, miten lajittelee järjestykseen nuo kokonaisluku-olio-muistipaikkaviittaukset. Javassa taitaa olla valmiina jo tähänkin ratkaisut?

En ehkä ihan ymmärtänyt, mitä tässä haet. Käytännön esimerkki voisi avata ongelmaa.

Yksi tyypillinen hakuongelma on sellainen, että halutaan tarjota joukolle olioita (tai vaikka kokonaislukuja) nopea keino tarkistaa, onko joukossa tietty olio. Esimerkiksi Pythonin dict() ja set() ovat tällaisia, ja ne perustuvat hajautustauluun. Dictissä on tallennettuna avain - arvo -pareja, ja sieltä haetaan arvo avaimen perusteella keskimäärin vakioajassa O(1), eli keskimääräinen hakuaika ei riipu dictiin säilöttyjen alkioiden määrästä. Tosin amortisoitu huonoin tapaus on O(n), eli datasta riippuen tietyn haun kesto voi olla lineaarinen suhteessa alkioiden määrään. Tällaiset heikkoudet ovat yleisiä hajautustauluissa ja muissa dynaamisissa tietorakenteissa. Joskus esimerkiksi tietoturvasyistä on käytettävä tietorakennetta, joka toimii keskimäärin hieman hitaammin, mutta pahin tapaus ei ole yhtä patologinen.

Pythonin tietorakenteiden aikavaativuuksia: https://wiki.python.org/moin/TimeComplexity
Wikipedian yleisartikkeli aiheesta: https://en.wikipedia.org/wiki/Time_complexity

Jos tämä aihepiiri kiinnostaa, kannattaa käydä yliopiston algoritmikursseja, joissa aikavaativuus on yleensä keskeinen teema.

[Jere Sumell]

Juu, Turun Yliopistossa ainakin aineopinnoissa on algoritmiteoriaa, ja sen yhteydessä olen tutustunut tuohon aikakompleksisuuteenkin vähän.

Tosiaan tuossa demonstraatiossa, jossa on noita kokonaislukuja pieni syotemäärä, niin sama mitä lajittelualgoritmiä käyttää, mutta jos syotekoko kasvaa, niin ei ole ollenkaan sama, minkälaisia algoritmejä käyttää, vaikka ongelmaa ratkaistaisiin Suomen valtion kvanttitietokoneella, tai nykyisillä supertietokoneilla.

Googlesta kun katsoo Time Complexity algorithms cheat sheet, niin tuolta bigoheatsheetistä pystyy tarkistamaan näppärästi, minkälaisia aikavaatimuksia eri algoritmeillä on. Suora linkki on

https://www.bigocheatsheet.com/

Kysyin luennoitsijalta, että onko kaikkiin algoritmisesti ratkeaviin ongelmiin mahdollista loytää logaritmisessa ajassa suoriutuva ratkaisu, mutta tämä ei osannut vastata siihen.

Algoritmiteoria kyllä mielenkiintoista, ja se on ajaton aihe. Mitä idea algoritmista on tuhansia vuosia vanha, niin vain hyvin pieni osa ihmisen reaalimaailman ongelmista lopulta on sellaisia, joihin kyetään loytämään tietokoneen avulla ratkaisu.

Heitän nyt haasteen, jos joku tykkää bisnestä tehdä, niin kehitetään tuollainen aikataulutus-algoritmi, ja lisenssoidaan yksinoikeudella hyvään hintaan se vaikka jollekin televisiokanava-yritykselle myyntipuheessa kanavan suuntaan painottaen, että toimii kilpailuvalttina kilpailevien kanavien suhteen, kun ei tule päällekkäisyyksiä saman formaatin ohjelmissa niin paljon ja mainoskatkoissa omien hittiohjelmien kanssa. Vaikka kyllä aika hyvin, mitä olen myos innokas sohvaperuna television katselun osalta, niin ainakin mainoskatkot yleensä ajoittuu samoihin kellonaikoihin vähän joka kanavalla.

Bill Gateshan ohjelmoi joskus kouluaikoinaan lukujärjestysohjelman koulun tietokoneella, olen jostain lukenut. Likimääräisyys-algoritmejähän ne soveltaa, kun jos on paljon soviteltavaa, niin joitain yhteentormäyksiä välttämättä sattuu, siinä on juuri se haaste, että onko mahdollista aikatauluttaa siten, että ei tule päällekkäisyyksiä, tuollainen televisiokanavayhtion järjestelmään integroituna, mikä laatii sen ohjelmataulukon, ja alkaa toistamaan ohjelmia missäkin järjestyksessä ja mihin aikaan on yksi käytännnon reaalimaailman sovellus.

[AimoE]

Sinulla tuntuu edelleen olevan se käsitys että algoritmi yksinään voisi olla rahastuksen peruste. Algoritmia ei voi patentoida, joten algoritmin perusteella ei voi määrätä lisenssimaksuja. Ohjelmistojen lisenssimaksut eivät perustu algoritmien rahastukseen, vaan kyse on palvelumaksuista, eli asiakas maksaa siitä että ohjelmistoa ylläpidetään, bugeja korjataan, kysymyksiin vastataan, jne. Jos olet valmis antamaan tällaista tukea, voit hinnoitella oman työsi tuen parissa ja kerätä siitä lisenssimaksuja. Mutta pelkän algoritmin perusteella et pysty rahastamaan, ainakaan Euroopan alueella.

Täydennys:
Edellä olevassa hyppäsin yli tekijänoikeuksiin perustuvista lisenssimaksuista. Tekijänoikeusmaksukaan ei perustu algoritmiin, vaan sen esitystapaan, eli miten se on muotoiltu ohjelmakoodiksi. Tekijänoikeusmaksulla katetaan tämän esitysmuodon tuottamiseen käytetty työ. Ohjelmistoja kuitenkin harvoin myydään sellaisenaan, niin että niitä ei jälkeenpäin korjata ja täydennetä. Alkuperäisen julkaisun jälkeen tehty ylläpito jakautuu viankorjauksiin ja uusien ominaisuuksien julkaisuun. Ylläpitomaksu siis sisältää sekä uusien esitysmuotojen luomiseen että vikojen korjaukseen tehdyn työn. Näitä on vaikea jakaa erilleen, joten jako on käytännössä mahdollista tehdä vain sen mukaan, mitä maksetaan siitä että ohjelmisto ylipäätään on julkaistu ja mitä maksetaan ensimmäisen julkaisun jälkeen tehtävästä ylläpitotyöstä ja muusta tuesta. Näitä molempia voidaan nimittää lisenssimaksuiksi.

Toistan vielä kerran, mikään näistä maksuista ei voi eurooppalaisen lainsäädännön mukaan perustua algoritmiin, vaan maksut perustuvat aina siihen että algoritmin esitystapa ensin ja sitten ohjelmiston tuki teettää työtä. Työstä voi kerätä maksuja, algoritmin keksimisestä ei. Algoritmi ei sovi patentoitavan keksinnön määritelmään, joka perustuu siihen, että patentin avulla suojataan teollisuuden (materiaalisia) investointeja, kuten tehtaiden ja tuotelinjojen rakentamista, materiaalien hankintaa tuotantoa varten, jne.

[_Pete_]

Ite koodissa ei tällä kertaa ole havaittavissa suuria kännioivalluksia

Pari huomiota mitä kannattaa Javan kanssa touhutessa:

1) Käytä IDE:ä, Intellij on paras, sen kanssa saata koodit automaattisesti oikein muotoilluksi joka helpottaa lukemista

2) Java 8 päivitysten tuki on loppumassa/loppunut, käytä uusinta JDK versiota

3) Käytä projektissa maven buildi työkalua

4) Jaa koodi erikseen toteutus luokkiin ja testiluokkiin jolla toiminnallisuus testataan. Vältytään sekavilta main() virityksiltä. Tämä jako tapahtuu automaattisesti kun käyttää maven projektirakennetta.

[Jere Sumell]

Kiitos pete kommenteistasi.

Juu, on kännikoodailusta kokemusta vähän, niin eihän kännissä voi ohjelmoida täysiverisesti. Toisin kun mitään lisäarvoa tuottamatonta opinnäytetyota voi kirjoittaa humalassa, johon lopulliseen kanditutkielmaan päätyy enemmän humalassa kirjoitettua tekstiä, mitä selvin päin, vaikka yleisesti en harrasta mitään kännissä automaattikirjoitusta.

Olen katsonut tuota IntelliJ IDEä, niin sehän on tolkuttoman kallis lisenssi siinä, paitsi tuo community-versio on maksuton tosin.

Kiitos maven-vinkistä, pitänee tutustua.

[_Pete_]

Olen katsonut tuota IntelliJ IDEä, niin sehän on tolkuttoman kallis lisenssi siinä, paitsi tuo community-versio on maksuton tosin.

Kiitos maven-vinkistä, pitänee tutustua.

Community versio on ihan riittävän hyvä aloittelijoille. IntelliJ:llä saat helposti myös luotua maven projektin suoraan sen kautta.

[Jere Sumell]

Joo, kiitos paljon vinkistä!

Mun kurssikollega kanssa puhui tuosta IntelliJ:stä, että oli kokeillut sitä. Itse suosin Eclipse IDEä, kun se on avoimesti saatavilla Cross-Platform kehitystyökalu, ja liitännäistarjonta hyvin laaja, jos päätyy vaikka päätyisi R:ällä tekemään jotain jos vaikka gradun tekisi tiedonlouhinnasta sosiaalisessa mediassa, keskittyisi siinä tekstidatan louhintaan, kun se lienee kuva ja -videolouhintaa helpompaa, ja datan määrä kasvaa ja tekstidatan erityisesti sosiaalisen median esiintulon myötä koko ajan niin valtavalla volyymillä. Tiedon louhinta kyllä kiinnostaa. Kyllähän siitä nyt saisi varmaan yhden opinnäytetyötutkielman tehtyä, jos menisi oikein syvälle aiheeseen.

Eclipisessäkin on projekteissa tuo Maven, mutta en ole siihen perehtynyt, nyt voisi ottaa asiaksi, kun ehdotit sitä.