Kirjautuminen

Haku

Tehtävät

Koodit: C++: Käännöksen aikainen Fizz buzz

Kirjoittaja: Jalmari91

Kirjoitettu: 12.05.2016 – 15.05.2016

Tagit: ohjelmointitavat, vinkki

Template Metaprogramming on menetelmä, jolla voidaan käännöksen aikana muodostaa väliaikaista koodia. Tämä väliaikainen koodi voidaan yhdistää muuhun koodiin. Tämä vähentää tarvetta tehdä joitain asioita ohjelman ajon aikana, ja näin optimoidaaa ohjelman toimintaa. Tässä on esimerkkikoodi, jossa käytetään kyseistä menetelmää muodostamaan Fizz buzz -merkkijono halutulle arvoalueelle. Ohjelman suorituksen aikana ajetaan käytännössä vain puts-funktio, joka tulostaa merkkijonon, jonka esimerkkikoodi on muodostanut valmiiksi käännöksen aikana.

Koodi toimii C++:n mallien ja periyttämisen avulla. Mallien avulla luodaan logiikan mukaan automaattisesti erilaisia luokkia, jotka perivät toisia luokkia, joita tehdään aina tarpeen mukaan. Tekstiä ei koota suoraan muuttujiin vaan mallin chars-parametrilistaan, koska tekstimuuttujia ei voi yhdistää malleissa käännöksen aikana. Yksi malli lisää aina oman osuutensa edellisen perään, ja sitten jatketaan seuraavaan malliin. Lopuksi peritään viimeinen luokka string, joka tekee parametrilistasta merkkijonon. Esimerkki:

Luokka1:

template<COUNT, 0, start> struct fizz_buzz_impl

Luokka2, jonka Luokka1 perii:

template<num, start, end> struct fizz_buzz_impl<FIZZ, num, start, end>

Luokka3, jonka Luokka2 perii:

template<num, start+1, end, 'F', 'i', 'z', 'z', '\n'> struct fizz_buzz_impl<BUZZ, num, start+1, end, 'F', 'i', 'z', 'z', '\n'>

Luokka4, jonka Luokka3 perii

template<num, start+2, end, 'F', 'i', 'z', 'z', '\n', 'B', 'u', 'z', 'z', '\n'>
struct fizz_buzz_impl<NUM, num, start+2, end, 'F', 'i', 'z', 'z', '\n', 'B', 'u', 'z', 'z', '\n'>

.
.
.
Viimeinen luokka:

template<'F', 'i', 'z', 'z', '\n', 'B', 'u', 'z', 'z', '\n', ..., '\0'> struct string

Viimeinen luokka kokoaa merkkijonon.

#include <stdio.h>
#include <stdint.h>

enum {
        FIZZ = 0,
        BUZZ = 1,
        FIZZ_BUZZ = 2,
        NUM = 3,
        REV_INT2STR = 4,
        LAST = 5,
        COUNT = 6,
};

/*
  Makro joka toteuttaa seuraavanlaisen logiikan:
  if (start > end)
    return LAST;
  else if (start % 15 == 0)
    return FIZZ_BUZZ;
  else if (start % 3 == 0)
    return FIZZ;
  else if (start % 5 == 0)
    return BUZZ;
  else
    return NUM
 */
#define FIZZ_BUZZ_TYPE(start, end) (((start) > (end)) ? LAST : \
        ((start) % 15 == 0) ? FIZZ_BUZZ :                      \
        ((start) % 3 == 0) ? FIZZ :                            \
        ((start) % 5 == 0) ? BUZZ : NUM)

/* Viimeinen struct joka periydytetään ja muodostetaan varsinainen merkkijono
   chars-parametrilistasta... */
template<char... chars>
struct string {
        static const char value[];
};

/* ... ja sen määrittely */
template<char... chars>
const char string<chars...>::value[] = {
        chars...
};

/* Tällä voidaan kääntää luku toisin päin (esim. 423532 -> 235324). Tätä
   käytetään helpottamaan luvun palastelua, koska palastelussakin luku menee
   väärin päin. Nyt kun käännetään luku jo valmiiksi tällä, niin palastelun
   jälkeen luku on oikein päin. */
template<uint64_t integer, uint64_t reversed>
struct reverse_integer : reverse_integer<integer / 10, reversed * 10 + integer % 10> {

};

/* Luvun kääntäminen tehty loppuun. */
template<uint64_t reversed>
struct reverse_integer<0, reversed> {
        static constexpr uint64_t value = reversed;
};

/* Lähtöpiste josta lähetään periyttämään muita luokkia. Lisäksi tarkistetaan ettei
   start ole suurempi kuin end. */
template<uint16_t type, uint16_t num, uint16_t start, uint16_t end, char... chars>
struct fizz_buzz_impl : fizz_buzz_impl<FIZZ_BUZZ_TYPE(start, end), num, start, end, chars...> {
        static_assert(start <= end, "End cannot be smaller than start!");
};

/* Malli lisää tekstiin yhden sanan ja siirtyy seuraavaan lukuun. Makron parametreillä
   voidaan määrittää mikä sana lisätään tietyn tyyppisellä mallilla. Esimerkiksi jos
   mallin tyyppi on FIZZ, lisätään sana "Fizz\n". */
#define FIZZ_BUZZ_IMPL(type, type_str...)                                           \
        template<uint16_t num, uint16_t start, uint16_t end, char... chars>         \
        struct fizz_buzz_impl<type, num, start, end, chars...> :                    \
                        fizz_buzz_impl<FIZZ_BUZZ_TYPE(start + 1, end), num,         \
                                       start + 1, end, chars..., type_str, '\n'> {  \
                                                                                    \
	}

/* Luodaan makron avulla malli, joka peritään jos luku on jaollinen 3:lla mutta ei 5:llä.
   Malli lisää sanan "Fizz\n" chars-parametrilistaan. */
FIZZ_BUZZ_IMPL(FIZZ, 'F', 'i', 'z', 'z');
/* Luodaan makron avulla malli, joka peritään jos luku on jaollinen 5:llä mutta ei 3:lla.
   Malli lisää sanan "Buzz\n" chars-parametrilistaan. */
FIZZ_BUZZ_IMPL(BUZZ, 'B', 'u', 'z', 'z');
/* Luodaan makron avulla malli, joka peritään jos luku on jaollinen sekä 3:lla että 5:llä.
   Malli lisää sanan "FizzBuzz\n" chars-parametrilistaan. */
FIZZ_BUZZ_IMPL(FIZZ_BUZZ, 'F', 'i', 'z', 'z', 'B', 'u', 'z', 'z');

/* Malli, joka peritään jos luku ei ole jaollinen 3:lla eikä 5:llä. Malli kääntää ensin luvun
   väärin päin, jonka jälkeen luku lisätään yksi numero kerrallaan chars-parametrilistaan. */
template<uint16_t num, uint16_t start, uint16_t end, char... chars>
struct fizz_buzz_impl<NUM, num, start, end, chars...> :
                fizz_buzz_impl<REV_INT2STR, reverse_integer<start, 0>::value, start, end,
                               chars...> {

};

/* Lisätään yksi numero chars-parametrilistaan ja siirrytään luvun seuraavaan numeroon. */
template<uint16_t num, uint16_t start, uint16_t end, char... chars>
struct fizz_buzz_impl<REV_INT2STR, num, start, end, chars...> :
                fizz_buzz_impl<REV_INT2STR, num / 10, start, end, chars..., '0' + num % 10> {

};

/* Koko luku käsitelty ja siirrytään logiikan mukaan seuraavaan malliin. */
template<uint16_t start, uint16_t end, char... chars>
struct fizz_buzz_impl<REV_INT2STR, 0, start, end, chars...> :
                fizz_buzz_impl<FIZZ_BUZZ_TYPE(start+1, end), 0, start + 1, end, chars..., '\n'> {

};

/* Muutetaan chars-parametrilista varsinaiseksi merkkijonoksi string luokan avulla. */
template<uint16_t num, uint16_t start, uint16_t end, char... chars>
struct fizz_buzz_impl<LAST, num, start, end, chars...> : string<chars..., '\0'> {

};

/* Wrapperi fizz_buzz_impl:lle. */
template<uint16_t start, uint16_t end>
struct fizz_buzz : fizz_buzz_impl<COUNT, 0, start, end> {

};

int main()
{
        static const char *r = fizz_buzz<1, 100>::value;
        puts(r);
}

Kommentit

Metabolix [15.05.2016 13:12:31]

#

Hauska vinkki!

Funktioilla toteutus olisi aika helposti jokin tällainen:

#include <iostream>
#include <string>

std::string sana(int a) {
	return a % 15 ? a % 3 ? a % 5 ? std::to_string(a) : "Buzz" : "Fizz" : "FizzBuzz";
}
std::string fizzbuzz(int a, int b) {
	return (a <= b) ? sana(a) + "\n" + fizzbuzz(a+1, b) : "";
}

int main() {
	std::cout << fizzbuzz(0, 30) << std::endl;
}

C++:n malleilla ei ole mahdollista tehdä (merkkijonojen kanssa) tällaisia sivukutsuja, vaan koko nykyistä merkkijonoa täytyy kuljettaa mukana chars-parametrissa järjestyksessä kaikkien välivaiheiden läpi, kuten vinkissä näkyy.

Esimerkiksi Fibonaccin lukuja olisi malleilla mahdollista tuottaa enemmän funktiotyylisesti rekursiivisesti:

/** Yksi fibonaccin lukujonon termi lasketaan edellisten summana. */
template <unsigned i> struct fibonacci {
	static constexpr unsigned long n = fibonacci<i-1>::n + fibonacci<i-2>::n;
};

/** fibonacci(0) = 0. */
template <> struct fibonacci<0u> {
	static constexpr unsigned long n = 0;
};

/** fibonacci(1) = 1. */
template <> struct fibonacci<1u> {
	static constexpr unsigned long n = 1;
};

#include <stdio.h>
int main() {
	printf("%lu\n", fibonacci<7>::n); // 13
	printf("%lu\n", fibonacci<8>::n); // 21
	printf("%lu\n", fibonacci<9>::n); // 34
}

Ylipäänsä tällaisen malliohjelmoinnin rajoitus on, että parametrina ei voi käyttää muuttujia, eli kaikki parametrit pitää tietää käännösvaiheessa.

Kirjoita kommentti

Muista lukea kirjoitusohjeet.
Tietoa sivustosta