Nejkratší implementace strlen a strcpy (diskuse)

[Dataman]

Nikdy nejde o to napsat co nejméně znaků. Důležitější je spíše optimalizace. Rekurzivní funkce ti zabere spoustu paměti. Schválně, jak ti bude u funkce strlen trvat, než sjede dvacet tisíc znaků a kolik ti zabere paměti. Ta moje ti paměti bude zabírat pořád stejně, ta tvoje ji bude neustále krást.

int strlen(char *a){
  int i=0;
  while(*a)
  {
    ++i;
    ++a;
  }
  return i;
}

[Luk]

Přesně tak. Rekurzivní funkce se hodí prakticky jen jako cvičení, jako ukázka, že to jde. Ale jsou vždycky pomalejší než totéž udělané iterací, navíc spotřebovávají paměť na zásobníku a ten navíc při "větším" počtu vnoření přeteče. Platí známé pravidlo, co jde udělat rekurzí, jde udělat iterací.

[3018736794024648]

ech.. samozřejmě. úloha zněla ale "nejméně znaků", nikoli nejvýkonnější. Prostě toto není otázka z reálného světa, a nemá smysl se ptát jestli úloha "najděte nejkratší řešení" má smysl, stejně jako nemá smysl mnoho lidské činnosti.

já vím že rekurze je v tomto případě úplná blbost. Nicméně musíš uznat, že pomocí rekurze je to řešení kratší než jiná, běžnější řešení.

[Martin Čížek]

char *strcpy(char *d, const char *s) 
{
  char *ret = d;
  while ((*d++ = *c++))
    ;
  return ret;
}

P. S. K ,,sestřesení'' kódu do jedné řádky se uchylovat nebudu .

P. P. S. Obě funkce se obvykle implementují v asembleru, ,,výkonný kód'' je na i386 tvořen pomocí jedné prefixované instrukce (+ nějaký ten vstup do funkce, cld a leave).

[unchallenger]

Ad P.P.S. Obvykle už ne. Obvykle je slušný kompilátor (gcc) implementuje přímo a dokáže optimalizovat in-line.

[Martin Čížek]

Obecně souhlasím -- je pravda, že mikrooptimalizace se stále více nechávají na kompilátoru, ale existující implementace těchto základních knihovních funkcí na to obvykle nespoléhají. V glibc jsou tyto jednoduché funkce napsané v asembleru pro všechny možné architektury, plus je tam jedna generic implementace v čistém C.

Jak tak na to koukám, v glibc jsou i ,,jemnější'' verze pro i486, i586 atd., které jsou implemetované v asembleru bez prefixových instrukcí (což je asi na procesorech s RISCovými rysy rychlejší).

[Martin Čížek]

Špatně jsem si to přečetl tvůj příspěvek, máš samozřejmě pravdu. Ale to není v rozporu s tvrzením o implementaci knihovních funkcí strlen() a strcpy(), i když je pak třeba optimalizovaný kód nepoužívá .

[3018736794024648]

ježda. samozřejmě. jenže tohle řešení má 35 platných znaků.. moje má 33 ;) proto jsem ho dával do blogu, protože je kratší než tahle klasika

[Jan Turoň]

tahle je taky zajímavá

int strlen(char *str) {
  int i=0;
  for(;*(str+i);i++);
  return i;
}