Portál AbcLinuxu, 3. května 2025 00:13
16.11.2016 19:02
| Přečteno: 3045×
| C
|
int seq[10] = { 11, -8, 92, 22, 7, -25, -95, 63, 3, 43 };
K seřazení můžeme použít například knihovní funkci qsort.
qsort(seq, 10, sizeof(int), compar);Řadicí algoritmy vyžadují ke své činnosti funkci, která porovná dva prvky z řady. Pro vzestupné řazení funkcí
qsort musí tato funkce vracet celé číslo (a) menší než, (b) rovno nebo (c) větší než nula, když je první prvek z této dvojice (a) menší než, (b) roven nebo (c) větší než prvek druhý. Pro náš případ to bude rozdíl těchto dvou prvků.
int compar(const void *p1, const void *p2)
{
return *(const int *)p2 - *(const int *)p1;
}
A jako výsledek dostaneme správně seřazenou řadu.
92 63 43 22 11 7 3 -8 -25 -95A teď kdo uhádne, co je na příkladu výše špatně? Nebudu vás napínat. Implementace selže na číslech, jejichž rozdíl se nevleze do datového typu
int. Uvažme například následující řadu.
int seq[10] = { -1951288147, 51, -2022032484, 79, -1227112550, 1760804629, 75, -2038298820, 1264956463, 22 };
Po volání qsort bude řada vypadat takto:
79 51 -1227112550 -1951288147 -2022032484 -2038298820 1760804629 1264956463 75 22Podobný problém nastane také u porovnání datových typů širších než typ
int. Řešení může být v našem případě porovnání:
int compar(const void *p1, const void *p2)
{
return (*(const int *)p2 > *(const int *)p1) - (*(const int *)p2 < *(const int *)p1);
}
A výsledek (tentokrát správně):
1760804629 1264956463 79 75 51 22 -1227112550 -1951288147 -2022032484 -2038298820Ještě dodám, že problém se týká i příbuzných funkcí jako například
bsearch.
Tiskni
Sdílej:
16.11.2016 20:54
int i;
for (i = 1; i > 0; i++);
muze prekladac optimalizovat na nekonecny cyklus. Na nekterych platformach pri preteceni dostanete SIGFPE.
Měl byste se naučit rozlišovat mezi empiricky odpozorovaným chováním jednoho konkrétního překladače na jedné konkrétní platformě a tím, co garantuje norma jazyka.
Např. gcc 4.8.1 na x86_64 přeloží s -O3 funkci
int main() {
int i;
for (i = 1; i > 0; i++)
;
printf("%d\n", i);
return 0;
}
na
0000000000400410 <main>: 400410: eb fe jmp 400410 <main> 400412: 66 90 xchg %ax,%ax
Tj. nejen že z toho udělá nekonečný cyklus, ale rovnou vyhodí i volání printf() a návrat z funkce za ním.
17.11.2016 03:33
Jendа | skóre: 78
| blog: Jenda
| JO70FB
Těžko říct. Ale třeba v jádře je běžné, že v závislosti na konfiguračních volbách (což jsou vlastně makra) může někde z preprocesoru vypadnout kus kódu, který je zbytečný, a počítá se s tím, že si s tím optimalizátor poradí.
Na druhou stranu se ale taky občas stane, že nějaká vynalézavá optimalizace novějšího gcc (třeba "není potřeba testovat pointer na null, když už jsme ho dereferencovali") naopak věci rozbila.
Jinak, jestli te to zajima, tak se podivej do "Dragon book", kapitola o "Symbolic analysis"
Je to optimalizace ktera umozni urcit jak se promenne v cyklu chovaji v zavislosti na poctu iteraci. Tim je mozne odstranit treba nasobeni, indexaci, podminky, ...
Napr. to umozni prepsat tenhle cyklus:
for (m = 10; m < 20; m++) {
x = m*3;
A[x] = 0;
}
na:
for (ptr = A+30; ptr <= A+57; ptr += 3) {
*ptr = 0;
}
$ gcc --version gcc (Debian 6.2.0-10) 6.2.0 20161027 [...] $ gcc -o test test.c test.c: In function ‘main’: test.c:7:9: warning: implicit declaration of function ‘printf’ [-Wimplicit-function-declaration] printf("%d\n", i); ^~~~~~ test.c:7:9: warning: incompatible implicit declaration of built-in function ‘printf’ test.c:7:9: note: include ‘stdio.h’ or provide a declaration of ‘printf’ $ ./test -2147483648
17.11.2016 22:24
Jendа | skóre: 78
| blog: Jenda
| JO70FB
Tady si sam protirecite, nebot pouzivate chovani jednoho konkretniho prekladace na jedne konkretni platforme jako dukaz.
Vůbec ne. Vy jste tvrdil, že to překladač udělat nemůže. To je obecné tvrzení, takže příklad nestačí. Já jsem vám ukázal, že vaše tvrzení obecně neplatí a na to samozřejmě jeden protipříklad stačí.
Já jsem nijak nerozporoval, že existuje nějaký překladač, který s konrétními volbami u optimalizaci neprovede. Ale rozhodně to neplatí pro všechny - a i kdyby náhodoou ano, stejně byste na to nemohl spoléhat, protože norma to chování nezaručuje, takže by se vám to mohlo rozbít hned s následující verzí.
Ještě pro pořádek:
C99 specifikuje int jako znamenkovy typ, takze pokud pretece, podminka se pretoci do < 0
A kde konkrétně se to o "přetočení do < 0" v té normě píše?
Napr. GCC 6.x to kompiluje korektne, takze to co pozorujete je spis bug v gcc optimizeru.
gcc6 se chová úplně stejně jako gcc 4.8.1, zkuste si to přeložit s -O3. S -O0 tu optimalizaci neprovede ani gcc 4.8.1, což je celkem logické, když mu řeknete, že optimalizovat nemá.
17.11.2016 02:29
Jendа | skóre: 78
| blog: Jenda
| JO70FB
16.11.2016 21:06
wamba | skóre: 38
| blog: wamba
sort. :) Já měl zafixováno, že by to mělo nabývat jen hodnot -1, 0, 1.
Krásné je v Perlu 6 chování sort, které řadí podle cmp.
Chování cmp:
perl6 -e 'say 2 cmp 12, 12 cmp "12a", "12a" cmp 2' LessLessLessPole, kde následující prvek vznikne seřazením předchozího
perl6 -e 'say ((12, 2, "12a"), *.sort ... * ).head(5)' ((12 2 12a) (12a 2 12) (12 12a 2) (2 12 12a) (12a 2 12))
ISSN 1214-1267, (c) 1999-2007 Stickfish s.r.o.
20.11.2016 10:55