- 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). - 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. - 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. - 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! - 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.
- 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) - 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.
- 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:
- 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_System
https://www.grammatech.com/products/binary-analysis - 50+merkkiä:
- 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ä.