y2017

Vapaa kuvaus

Aloituksia

0

Kommenttia

11

  1. Luuppaamatta tästä harjoituksesta ei selviä. Idea lieneekin, että luuppaaminen minimoidaan ja että luuppien pituus on määrämittainen, siis ennustettava.

    Aputaulukon käyttö edellä kuvatulla tavalla toimii, kun lukualue on pieni. Kaksi ei-sisäkkäistä luuppia sisältyy tähänkin ratkaisuun. Huomaa, että mm. shuffle-funktio sisältää luupin.

    Jos lukualue on liian suuri taulukoitavaksi, tulee nopeasti mieleen seuraava ratkaisu.

    Luvut tulostaulukossa pidetään suuruusjärjestyksessä esimerkiksi puurakennetta käyttäen. Luupataan: Arvotaan luku lukualueelta. Käydään tulostaulukko läpi pienimmästä luvusta alkaen ja milloin luku tulostaulukossa on pienempi tai yhtäsuuri kuin arvottu luku, arvottua lukua kasvatetaan yhdellä. Tulostaulukon läpikäynti päättyy viimeistään kun luku tulostaulukossa on suurempi kuin arvottu luku. Arvottu luku sijoitetaan tulostaulukkoon. Lukualuetta pienennetään yhdellä ja luuppaaminen jatkuu.

    Ratkaisussa on kaksi sisäkkäistä luuppia. Lisäksi puurakenteen käsittely tarkoittaa eräänlaista luuppaamista. Jos arvottavia lukuja on vain vähän, tulostaulukon pitäminen järjestyksessä onnistuu yksinkertaisesti sisentämällä (joka vaatii oman luuppinsa).
  2. Hyvin olet perehtynyt AVR-ohjelmointiin. Pidä kuitenkin mielessä, että prosessori on vain kasibittinen, et voi odottaa siltä x86:n ominaisuuksia. Arkkitehtuureissakin on merkittäviä eroja. AVR on RISC-arkkitehtuuri, jossa moni asia tehdään vähän vaikeamman kautta, esimerkiksi mainitsemasi automaattimuuttujien tilanvaraus.

    Toisin kuin PIC-prosessorit alunperin, AVR suunniteltiin C-ohjelmointia silmälläpitäen ja rajoitteista huolimatta Atmel onnistui tavoitteessa hyvin. Pienellekin AVR-kontrollerille on mielekästä kirjoittaa koodia C-kielellä.

    Funktion kutsuparametrien välitys ja automaattimuuttujat ovat hankalia asioita silloin, kun RISC-prosessorin rekisterit eivät riitä. Kannattaakin aina tarkkaan harkita millaisia funktioita kirjoittaa. Kasibittinen kontrolleri ei pysty samaan, mikä x86-ympäristössä on jopa helppoa.

    Kuten arvelit, jotkut kääntäjät (mm. IARCC) käyttävät kahta pinoa eli parametreille ja automaattimuuttujille on oma pino. Se tehostaa toimintaa, mutta ei ilmaiseksi. Rajallinen RAM-resurssi on lohkottava kahdelle pinolle ja yksi rekisteripari on uhrattava pino-osoittimeksi.

    Olit huolissasi keskeytyslatenssista. Mikä sovellus voi olla niin reaaliaikainen, että keskeytysten kielto viiden käskyn on ongelma? AVR kun on vieläpä suht' nopea prosessori lajissaan. Esimerkkikoodisi:

    cli
    in R16, SPL
    in R17, SPH
    sbiw R16, n
    out SPL, R16
    out SPH, R17
    sei

    lienee turvallista optimoida muotoon:

    in R16, SPL
    in R17, SPH
    sbiw R16, n
    cli
    out SPL, R16
    out SPH, R17
    sei

    Minusta keskeytysten kielto ja salliminen funktion alussa ja lopussa on sittenkin pikkujuttu, en kiinnittäisi moiseen liikaa huomiota. Parempi keskittää huomio funktioiden suunnitteluun siten, että tarvitsee turvautua mahdollisimman harvoin pinomuistin käyttöön tällä tavoin, 32 rekisteriä riittävät melko pitkälle.
  3. Vastakysymys: Osaatko heittää stetsonista mikä on autossa vastine peräsimelle?

    Vaikka C onkin hyvin laiteläheinen ohjelmointikieli, se on eri asia kuin assembler. C-kääntäjän tehtävä on kääntää lähdekoodista mahdollisimman tehokasta ja/tai tiivistä konekoodia. Yhtenä tällaisena optimointina se, kun kääntäjä havaitsee lähdekoodissa jotakin, jolla ei ole toiminnallista vaikutusta lopputulokseen, kääntäjällä on lupa ohittaa tällainen osa koodista. Olisikin merkillistä, jos lopputuloksessa olisi NOP-käskyjä. Siksi niitä ei ole C-kielessäkään.

    Olet kuitenkin oikeassa NOP-käskyn suhteen: "Ajoitushommissa joutuu välillä sitäkin turhaketta käyttämään". Siksi kääntäjiin on tehty erilaisia lisäyksiä, joilla C-koodiin on mahdollista sijoittaa assemblerin käskyjä. Lisäykset ja assembler ovat konekohtaisia, joten niiden käyttäminen tarkoittaa C-koodin siirrettävyyden menetystä. Niiden käytöllä saattaa olla vaikutusta myös kääntäjän optimointeihin ainakin ko. funktion sisällä.

    Käytännössä jokainen kääntäjä tuntee jonkin __asm { ... } -lisäyksen, jolla käännettyyn kooodiin saa lisättyä mm. NOP-käskyn. Vaihtoehtona esimerkiksi Microsoft on koonnut intrin.h headeriin suuren joukon muitakin käskyjä, joiden käyttäminen on siirrettävyyden kannalta hieman turvallisempaa. Tässä tapauksessa C-kielen vastine assemblerin NOP-käskylle on siis __nop().

    https://learn.microsoft.com/en-us/cpp/intrinsics/nop?view=msvc-170

    Osaatko heittää stetsonista mikä on NOP, koska ainakaan x86-prosessorit eivät tunnista sellaista käskyä?

    Anonyymi kirjoitti edellä: "Assembler on tietokoneohjelma, jolla käännetään symbolisella konekielellä eli assembly-kielellä kirjoitettuja ohjelmia. Sen taitamisesta ei haittaa ole, mutta ne taidot on tarpeettomia nykyään."

    Tarpeettomia vain amatööreille ja hällä väliä -koodareille. Pro osaa ainakin lukea assembly-koodia, jotta selviää debuggerin kanssa ja pystyy varmistamaan kääntäjän ja optimoijan tekemiset ainakin ohjelman kriittisissä osissa.

    Niin, kuten jokainen pro hyvin tietää, NOP on synonyymi x86-prosessorin käskylle XCHG (E)AX, (E)AX.
  4. Hauska+tehtävä.+Päivitän+sitä+sen+verran,+että+otan+numeron+40+mukaan,+kuten+lotossa+tehtiin+kierroksella+48/2016.+Erilaisia+rivejä+on+siis+18643560+kappaletta,+kuten+Veikkauksen+sivuilla+(peliohjeet+/+todennäköisyys)+kerrotaan.Pienin+määrä+lottorivejä,+à+7+numeroa,+että+ainakin+4+oikein+-tulos+(jäljempänä+"voitto")+osuisi+niihin+on+teoriassa+93.+Käytännössä+tällaista+rivikokoelmaa+ei+pysty+valitsemaan,+koska+osa+mahdollisesti+arvottavista+riveistä+tuottaisi+väistämättä+useamman+voiton.+Tämä+päällekkäisyys+tarkoittaa+ylimääräisiä+rivejä+teoreettisen+minimin+lisäksi.Optimaalisen+rivikokoelman+löytäminen+ei+ole+suoraviivainen+tehtävä+enkä+usko,+että+löytyy+oikotietä+onneen,+mutta+kokoelmassa+täytyy+olla+yli+200+lottoriviä.+Alla+hieman+alustusta+aiheeseen.+Arvottavan+lisänumeron+merkitystä+en+ole+huomioinut.Mikä+tahansa+yksittäinen+lottorivi+tuottaa+voiton+202280+tapauksessa+18643560:sta.+Jos+kokoelman+seuraavalla+rivillä+ei+ole+yhteisiä+numeroita+ensimmäisen+kanssa,+sekin+tuottaa+voiton+202280+tapauksessa.+Ilman+yhteisiä+numeroita+voidaan+laatia+vain+5+riviä.+Kuudenteen+riviin+on+poimittava+mukaan+kertaalleen+jo+käytettyjä+numeroita+ja+jos+kahdella+rivillä+on+vain+yksi+yhteinen+numero,+riveihin+osuu+kaksi+voittoa+400+tapauksessa.+Jos+kahdella+rivillä+on+kaksi+yhteistä+numeroa,+riveihin+osuu+kaksi+voittoa+3200+tapauksessa+jne.Tehtävänä+on+siis+tuon+päällekkäisyyden+minimointi+siten,+että+jokaisella+mahdollisesti+arvottavalla+rivillä+18643560:sta+voittaisi+yhden,+mutta+mahdollisimman+pienen+määrän+voittoja.Tehtävään+kannattaa+valita+tehokas+ohjelmointikieli+koska+kuten+kirjoitit,+tarkistaminen+on+hidasta.+Jos+unohdamme+assemblerin,+C-kieli+lienee+paras+vaihtoehto.+Esimerkiksi+näin:char+rivi[7]+=+{1,2,3,4,5,6,7};...for+(;;){//+Tarkista+voittaako+rivi[]...//+nextrow++++for+(int+i=7;+rivi[i-1]+==+40-7+i;)++++++++if+(--i==0)++++++++++++exit(0);+//+Valmis,+kaikki+rivit+läpikäyty++++for+(rivi[i-1]++;+++i+<=+7;+rivi[i-1]+=+rivi[i-2]+1);}Uloin+for-luuppi+funktion+sisään+ja+"Tarkista+voittaako+rivi[]"+-kohtaan+silmukka,+jossa+tarkistataan+kokoelman+rivit.+Jos+rivi[]+ei+tuota+voittoa+yhdenkään+kokoelmassa+olevan+rivin+kanssa,+kokoelmaan+on+lisättävä+numeroita+tai+kokonainen+rivi+siten,+että+rivi[]+tuottaa+voiton.Kokoelman+rivien+tarkistaminen+kannattaa+tehdä+taitavasti,+koska+siitä+saattaa+tulla+ohjelman+ylivoimaisesti+eniten+aikaavievä+osuus.+Tarvittaessa+kerron+lisää.+Onnea+tehtävään!
  5. FreeRTOS+on+resurssisyöppö+p***a,+mutta+toimiihan+se+ja+vieläpä+ilmaiseksi.+Raudan+tulee+olla+juuri+niin+"tehokas"+kuin+konenäkösovellus+ja+muut+mahdolliset+taskit+vaativat.+Pieni+RT-käyttis+ei+ole+mitenkään+oleellinen+tekijä+raudan+"tehokkuutta"+mitoitettaessa.+Esimerkiksi+FreeRTOS+toimii+aivan+hyvin+kontrollerissa,+jossa+on+kymmenen+kiloa+RAMia+ja+muutama+kymmenen+kiloa+koodimuistia.+Konenäkösovellus+vaatinee+paljon+enemmän+ja+MIPSejäkin+tarvitaan,+jotta+kuvat+ehditään+prosessoida.
  6. Mielenkiintoinen+kysymys!+Kirjoitit+oikeaan+paikkaan,+tältä+palstalta+löytyy+tunnetusti+Suomen+parasta+asiantuntemusta+tietotekniikan+alalta+mitä+sotiin+tulee.Minäkin+kirjoitan+tässä+mutua,+joka+lienee+suomenkielen+vastine+sanalle+proof.Esittämiesi+kahden+notaation+välillä+on+bijektio,+kuten+arvelit.+Ensimmäinen+notaatio+on+sama+kuin+postfix,+toinen+on+tietenkin+infix.+Muunnoksiin+notaatioiden+välillä+on+hyvin+tunnetut+algoritmit,+jotka+käyttävät+pinoa.Tekemäsi+literaalimuunnos+on+erikoinen.+Jos+se+toimii+kaikilla+n+arvoilla,+tilanteeseen+sopinee+lainata+Saulin+amerikkalaisen+kollegan+kaiman+sanoja:+"The+resulting+formula+is+properly+parenthesized,+believe+it+or+not."Literaalimuunnos+toiseen+suuntaan+ei+käy+yhtä+vaivattomasti,+kuten+varsinkin+näistä+esimerkeistä+ilmenee:(())()++-->++(a(bc))d(()())++-->++a((bc)d)
  7. Kiitän+tarkkaavaisuudesta+ja+palautteesta,+olet+tietenkin+oikeassa.+Esimerkkini+ansiot+lienevätkin+ensisijassa+sen+osoittamisessa,+että+lyhyeenkin+koodiin+saattaa+jäädä+pari+virhettä,+jos+laiminlyö+testaamisen.Esimerkkini+olisi+toki+pitänyt+"nähdä"+virheelliseksi+jo+helpolla+ajatusleikillä:+Otetaan+kuvakortit+J,+Q+ja+K+ja+sekoitetaan+ne+esimerkkini+mukaisella+koodilla.+Silmukan+ensimmäinen+kierros+tuottaa+yhden+kolmesta+mahdollisesta+lopputuloksesta,+toinen+kierros+9:stä+(sisältäen+samoja+yhdistelmiä)+ja+kolmas+27:stä,+mikä+luku+ei+ole+tasan+jaollinen+kuudella+ts.+kolmen+kortin+yhdistelmien+määrällä.+Lopputuloksen+on+siis+oltava+painotettu.Oikeampi+toteutus+on+esittämäsi+mukainen.+Silmukan+pituutta+leikkaisin+yhdellä,+koska+52.+kortti+jäisi+vaihdettavaksi+vain+itsensä+kanssa.for+(i=0;+i<51;+i++)vaihda_kortit(&pakka[i],+&pakka[i+++(unsigned)+(rand()+%+(52U-i))]);Satunnaisuus+ei+ole+harhaton+vieläkään,+sillä+rand()+modulo+tuottaa+painotettuja+satunnaislukuja+aina+milloin+luku+RAND_MAX+1+ei+ole+tasan+jaollinen+jakajalla.+Kuitenkin,+koska+RAND_MAX+on+huomattavan+paljon+suurempi+kuin+50,+vähäinen+painottuminen+voitanee+hyväksyä+tässä+yhteydessä.
  8. Taivaallisen+kömpelö+esitys+(web.nchu.edu.tw).+Enkä+kirjoittaisi+tällaiseen+dynaamisia+listojakaan,+koska+korttien+määrä+on+kiinteä.+Osoitintaulukko+voisi+tulla+kyseeseen,+mutta+yksinkertainen+ratkaisu+on+yleensä+paras.+Esimerkiksi+näin:void+sekoita_pakka(void)+{++++unsigned+i;++++for+(i=0;+i<52;+i++)++++++++vaihda_kortit(&pakka[i],+&pakka[(unsigned)+rand()+%+52U]);}vaihda_kortit()+on+funktio+tai+makro,+joka+vaihtaa+parametrina+annetut+kaksi+korttia+keskenään.
  9. Jaa+että+vielä+hyviä?Palauttaminen+C+++lle+(tai+muulle+natiivi-konekoodille+kääntävälle+kielelle)+ei+käytännössä+onnistu,+koska+nykyiset+kääntäjät+optimoivat+erittäin+hyvin.+Yhteys+suoritettavasta+ohjelmasta+lähdekoodiin+ts.+toteutustapaan+katoaa+varsin+tehokkaasti.Eri+asia+tietenkin,+jos+ohjelma+on+käännetty+ilman+optimointeja+ja+vielä+debug-tiedot+säilyttäen,+mutta+ainakaan+kaupallisista+ohjelmista+tällaista+mokaa+tuskin+löytyy.Ainakin+teoriassa+mikä+tahansa+suoritettava+(kryptaamaton)+ohjelma+on+käännettävissä+lähdekoodiksi.+Tuossa+edellä+jo+mainittiinkin+disassembler,+joka+oli+käyttökelpoinen+työkalu+silloin,+kun+ohjelmat+olivat+pieniä.+Nykyisistä+PC-sovelluksista+tms.+disassembler+todennäköisesti+generoisi+niin+runsaasti+koodia,+ettei+siitä+olisi+mitään+käytännön+hyötyä.Muita+(disassembleria+parempia)+työkaluja+löytyy,+mutta+em.+optimointisyyn+vuoksi+ei+ole+mitään+takeita+siitä,+että+lopputulos+on+lähelläkään+alkuperäistä+lähdekoodia.+Ainakin+näitä+kannattaa+tutkia+tarkemmin:https://en.wikipedia.org/wiki/FermaT_Transformation_Systemhttps://www.grammatech.com/products/binary-analysis
  10. 50+merkkiä:main(int+c,char**v){for(;--c;printf("%s+",*++v));}59+merkkiä:main(int+c,char**v){for(;--c;printf("%s+",*++v));puts("");}Sitten,+kuten+varmaan+tiedättekin,+tässä+kisassahan+ei+ole+mitään+järkeä.Kuten+Anonyymi+edellä+kirjoitti+(3.5.2019+19:33),+koodista+kannattaa+tehdä+mielumminkin+helposti+luettavaa+kuin+hyvin+kompaktia.+C-kääntäjä+ei+tee+tiukasta+onelinerista+tippaakaan+tehokkaampaa,+tiiviimpää+tai+nopeampaa+lopputulosta+eli+suoritettavaa+koodia+kuin+jos+lähdekoodi+on+kirjoitettu+nättiin,+väljään+ja+helposti+ymmärrettävään+muotoon.Kisassa+olisi+paljonkin+järkeä,+jos+paremmuutta+ratkotaan+lopputuloksen+tiukkuudella.+Esimerkiksi+montako+tavua+tai+assembler-käskyä+käännettyyn+objektiin+sisältyy.+(Tehtävän+toki+pitäisi+olla+hieman+vaativampi.)+Mm.+tätä+tarkoitusta+varten+C-kääntäjästä+saa+ulos+listauksen,+josta+objektin+voi+vaivatta+lukea+assembler-käskyinä.C-kielellä+työskennellessä+assembler-listausta+kannattaa+vilkaista+silloin+tällöin+monestakin+syystä.+C-kieltä+on+hyvin+helppoa+käyttää+"väärin"+eli+siten,+että+kääntäjän+tuotos+jää+tehottomaksi,+vaikka+ohjelma+toimisikin.+Osoittimien+käyttö+vs.+taulukon+indeksointi+on+yksi+esimerkki.+PC-ympäristössä+asialla+tuskin+on+suurta+merkitystä+nykyään,+mutta+varsinkin+sulautettujen+ohjelmoinnissa+jokaisella+tavulla+ja+mikrosekunnilla+saattaa+olla+suuri+merkitys.
  11. Joskus+ratkaisua+kannattaa+hetken+miettiä+aivan+oppimistarkoituksessakin.+C-kieli+on+siitä+jännä+juttu,+että+yksinkertaisuudestaan+huolimatta+siinä+riittää+oppimista+jopa+vuosikymmeniksi.+Ylläolevan+makron+pitäisi+toimia+ja+vieläpä+kaikilla+integer-tyypeillä....vaikken+olekaan+testannut+sitä.
    12. 1 / 1
TietosuojaselosteKäyttöehdotEvästeasetuksetSäännöt