Keskustelu: Ohjelmointikysymykset: C, C++: Millaisia kikkoja tiedätte?

Ajattelin luoda tällaisen keskustelun, jossa voitaisiin keskustella sellaisista koodin tyyliä (myös esim. lyhyyttä) ja nopeutta (tai siis voi olla pelkkä toinenkin tarkoitan siis TAI(ei XOR)) parantavista asioista ja sitten sellaisista muuten vaan kivoista.

Annan tästä hieman esimerkkejä, niin ehkä tajuatte paremmin jos ette vielä tajunneet (eka aina hidas/ruma ja sitten kaunis/nopea):

a%2        a&1
a%2==0     ~a&1
a*2+1      a<<1|1 // paitsi tässä en oo sitä mieltä, että toi jälkimmäinen olisi parempi kun siinä on yksi merkki enemmän niin vähän ikävää toisaalta käyttää sitä. Tästä syystä käytänkin a*2+1

Sitten tää olis esimerkki sellaisesta muuten vaan kivasta jutusta:

!!a

On aika turha luulo, että tuollaiset purkkaviritelmät enää nykykääntäjillä olisivat hyödyksi – alkaa olla aivan päinvastoin. Kannattaa myös panostaa koodin selvyyteen, ja sitä ei paranna mikään ideoistasi.

Opettele otsikoimaan aiheet jotenkin järkevästi (esim. ytimekkäästi ja ei kokonaan versaaleilla). Vaihdoin otsikon.

Tässä pari kikkaa koodin tyylin/luettavuuden parantamiseksi:

a&1    -> a%2
~a&1   -> a%2==0
a<<1|1 -> a*2+1

Nuo minun esimerkkini eivät ohjelman suoritusaikaa kyllä kai vähennä. T_T Ehkä joku kuitenkin tietää ohjelman suoritusnopeuteen oikeastikin vaikuttavia asioita?

En selvyydestä sitten tiedä, mutta nuo kuitenkin mielestäni lisäävät ohjelman kauneutta.

Onko myös !!a sinun mielestäsi purkkaviritelmä? Itse olen havainnut sen erittäin hyödylliseksi ja kauniiksi.

Lisäys: Yritän tulevaisuudessa tehdä otsikoista parempia. Arvostan palautettasi!

Vaihtoehtoinen toteutus binäärihaulle. Tämä on lyhyempi ja mielestäni helpompi toteutus kuin perinteinen toteutus.

int x[] = {3, 5, 7, 8, 10, 16}; // taulukko
int n = 6; // taulukon koko
int q = 10; // etsittävä luku

// binäärihaku
int k = 0;
for (int b = n; b >= 1; b /= 2) {
    while (k+b < n && x[k+b] <= q) k += b;
}
if (x[k] == q) cout << "löytyi kohdasta " << k;
else cout << "ei löytynyt";

Lähes yhtä helposti saa version, joka löytää etsittävän luvun ensimmäisen ja viimeisen esiintymän taulukossa:

int x[] = {3, 8, 10, 10, 10, 16}; // taulukko
int n = 6; // taulukon koko
int q = 10; // etsittävä luku

// binäärihaku
int i = -1, j = 0;
for (int b = n; b >= 1; b /= 2) {
    while (i+b < n && x[i+b] < q) i += b;
    while (j+b < n && x[j+b] <= q) j += b;
}
if (x[j] == q) cout << "löytyi " << j-i << " kertaa";
else cout << "ei löytynyt";

http://graphics.stanford.edu/~seander/bithacks.html

Olen käyttänyt seuraavaa temppua 32-bittisten kokonaislukujen perässä olevien nollabittien laskemiseen (trailing zeros):

int ctz32(uint32_t x)
{
    static const int table[32] = {
        0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
        31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
    };
    return table[((x & -x) * 0x077CB531) >> 27];
}

Miten toi toimii?

x & -x nollaa x:n kaikki muut bitit paitsi vähiten merkitsevän bitin (LSB). Jäljellä jää siis luku 2ⁿ, missä n on luvun perässä olevien nollabittien lukumäärä.

Taikavakio 0x077CB531 ei ole mikä tahansa luku. Sen bitit muodostavat 2-haaraisen de Bruijn -jonon alijonon pituudella 5. Käytännössä tämä tarkoittaa, että luvun 0x077CB531 bittiesitys sisältää jokaisen 5-bittisen luvun alijonona, ja täsmälleen kerran:

00000111011111001011010100110001 0000

Mitä sitten tapahtuu, kun tämä luku kerrotaan 2ⁿ:llä? Kaikkihan tietää, että luvulla 2ⁿ kertominen vastaa bittisiirtoa vasemmalle n:llä bitillä. Tästä seuraa, että kertolaskun tulon korkeimmat 5-bittiä ovat uniikit jokaiselle n = 0, 1, ..., 31. Taulukon avulla saadaan selville n, eli haluttu tulos.

kllp kirjoitti:

Onko myös !!a sinun mielestäsi purkkaviritelmä? Itse olen havainnut sen erittäin hyödylliseksi ja kauniiksi.

Minusta on, koska siitä ei käy ilmi miksi niin tehdään. Siis loogisestihan tuo näyttäisi siltä että tuloksena on a ja !! voisi heittää pois.

Jos tarkoitus on "castata" bool:iksi niin (bool)a olisi mielestäni parempi. Jos tarkoitus on verrata onko luku muu kuin nolla, olisi mielestäni a != 0 parempi.

Toisaalta voi olla että C# on rikkonut minut ja olen vaan vähän pervo kun tykkään siitä että kääntäjä ilmoittaa tuollaisesta esimerkiksi kokonaislukumuuttujan tapauksessa "Error: Operator '!' cannot be applied to operand of type 'int'"

Itse jostain syystä tykkään siitä, että koodista näkyy enemmänkin mitä halutaan tapahtuvan kuin että koodi olisi mahdollisimman lyhyttä.

Joskus lyhyt ja ruma on hyvä

void foo( void * ptr){
  ptr||return;

  jutut();
}
//verrattuna
void foo( void * ptr){
  if(ptr == NULL){
    return;
  }

  jutut();
}

Varsinkin silloin kun nullin tarkistus ei ole se juttu vaan jutut() voisi olla jotain todella rumaa bitin nypläystä. Muuten en arvosta && ja || käyttämistä if-lauseen sijaisena. Enkä kyllä ?:, mutta sillekin on paikkansa, jossa selkeyttää koodia.

Ja yleensä käsittämätön koodi on sellaista missä asiat on nimetty huonosti, ei bittkikkailu. Bittikikkailusta kun saa selvää, mutta format_hdd_and_burn_cpu(meat_balls) ei koskaan ole hyvä funktion kutsu.

vuokkosetae kirjoitti:

void foo( void * ptr){
  ptr||return;

Mitähän kieltä tämä mahtaa olla? Ei ainakaan C:tä. Perlissä ja joissain muissa vastaava pelleily on sallittua ja sitä näkeekin silloin tällöin, mutta pidän sitä itse rumana. En alkuunkaan ymmärtänyt pointtiasi.

JavaScriptissä !!x on yleinen tapa muuttaa null/undefined/tms. falsy arvo selkeäksi booleaniksi, enkä nää siinä mitään vikaa. Jokaisen JavaScript-koodarin pitäisi tajuta miettimättä, mitä se tekee, kun taas oman funktion käyttö hidastaisi lukemista. (Jos vain tietyt arvot halutaan käsitellä, niin suora vertailu kuten x !== null on totta kai parempi.)

Tässä hauska kikka: !~[1,2,3].indexOf(x).

Maailmanhistorian lyhin bigint-toteutus:

Seuraava koodi laskee 150. Fibonaccin luvun sekä luvun 30 kertoman. Tai laskisi, jos lukujen tarkkuus riittäisi.

void fibo(int n) {
    long long a = 0;
    long long b = 1;
    for (int i = 0; i < n; i++) {
        long long c = a+b;
        a = b; b = c;
    }
    printf("%lli\n", a);
}

void kertoma(int n) {
    long long k = 1;
    for (int i = 2; i <= n; i++) {
        k *= i;
    }
    printf("%lli\n", k);
}

int main() {
    fibo(150);
    kertoma(30);
}

Koodi antaa vääriä tuloksia:

6792540214324356296
-8764578968847253504

Idea: lasketaan tarkkuuden lisäämiseksi kaikki laskut sekä tyypillä long long että double. Nyt long long antaa luvusta tarkan loppuosan ja double antaa alkuosan. Lopullisen luvun tulostamiseen riittää parin rivin koodi.

void tulosta(long long x, double y) {
    y /= pow(10, 18);
    if (y < 1) {printf("%lli\n", x); return;}
    long long z = y;
    printf("%lli", z);
    for (int i = 0; i < 18; i++) z *= 10;
    printf("%018lli\n", x-z);
}

void fibo(int n) {
    long long a1 = 0;
    double a2 = 0;
    long long b1 = 1;
    double b2 = 1;
    for (int i = 0; i < n; i++) {
        long long c1 = a1+b1;
        a1 = b1; b1 = c1;
        double c2 = a2+b2;
        a2 = b2; b2 = c2;
    }
    tulosta(a1, a2);
}

void kertoma(int n) {
    long long k1 = 1;
    double k2 = 1;
    for (int i = 2; i <= n; i++) {
        k1 *= i;
        k2 *= i;
    }
    tulosta(k1, k2);
}

int main() {
    fibo(150);
    kertoma(30);
}

Nyt koodi antaa oikeat tulokset:

9969216677189303386214405760200
265252859812191058636308480000000

Lähde: http://petr-mitrichev.blogspot.fi/2008/11/long-time-no-see.html

Antti Laaksonen kirjoitti:

Maailmanhistorian lyhin bigint-toteutus:

pllk pls

6,7c6
<     for (int i = 0; i < 18; i++) z *= 10;
<     printf("%018lli\n", x-z);
---
>     printf("%018lli\n", x-z*(long long)1e18);

jlaire pls

void tulosta(long long x, double y) {
	long long w = 1e18, z = y / w;
	if (z) printf("%lli%018lli\n", z, x - z * w); else printf("%lli\n", x);
}

Tuo on kyllä hieno kikka. Vielä pari numeroa saa käyttämällä doublen sijaan long double -tyyppiä. Joissain tilanteissa kannattaa muistaa myös GCC:n __int128.

Haluan määritellä makron, jota käytetään näin:

PUTKASILMUKKA(...) {
    ...
}

Parametreillä ja silmukan logiikalla ei ole merkitystä. Ongelma on, että tarvitsen toteutuksessa useita apumuuttujia, jotka ovat erityyppisiä:

#define PUTKASILMUKKA(...) \
    for (bool b1, b2, double d, int i; ...; ...)

Kielen syntaksi ei salli tätä. Voisin määritellä muuttujat silmukan ulkopuolella, mutta se vaatisi makron käyttäjiä lisäämään ylimääräisen aaltosulun:

#define PUTKASILMUKKA(...) \
    { \
        bool b1, b2; \
        double d; \
        int i; \
        for (...; ...; ...)

PUTKASILMUKKA(...) {
   ...;
} }

Ei kelpaa.

Kikka:

#define PUTKASILMUKKA(...) \
    if (bool b1 = false); else \
    if (bool b2 = false); else \
    if (double d = 0.0); else \
    if (int i = 0); else \
    for (...; ...; ...)

Koska if-lauseen ehdossa määritellyt muuttujat näkyvät myös else-haarassa, niitä voi käyttää for-silmukan ehto- ja toisto-osiossa logiikan toteuttamiseen.

Miten edes määritellään se, mikä on kikka? Jos näen jonkun asian ensi kertaa, se voi näyttää kikalta. Jos käytän sitä sen jälkeen useasti, se on pikemminkin tekniikka.

En usko, että ketjun kannalta on oleellista kikan määritelmä. Ihan mikä tahansa juttu kelpaa, jos vain itse koet sen kivaksi. Tai no tuskin sitäkään vaaditaan 8D

teKnIiKKA

 o -.
 O /
| |

vuokkosetae kirjoitti:

ptr||return;

Voisihan jotain tuon tapaista käyttää.

/* palauttaa 0 jos virhe */
int f(int);
...
/* yritä toisella arvolla jos ensimmäinen antaa virheen */
int x = f(y) || f(z);
if (!x) { ... }

Virheen tulostus ja ohjelman pysäytys:

int virhe(char* viesti) {
    /* kirjaa lokiin viesti */
    ...
    exit(1);
}
...
int x = f(y) || virhe(" VIRHE!!!!!! ");

Tuossa on sellainen ongelma, että C:ssä || palauttaa aina joko 0 tai 1.

$ gcc -std=c99 -x c - <<< 'int main() { printf("%d\n", 0 || 42); }' && ./a.out
1

Törmäsin tähän joskus, kun yritin käyttää tuota tyyliä (C++:ssa). Jouduinkin kirjoittamaan x?x:y.