Špinavý trik (diskuse)

[Michal Kubeček]

Možná mám delší vedení, ale proč by to nešlo stejně řešit i v tom C++?

[ʚĭɞ 🍉]

Šlo, ale ne tak krátce (jo, v Perlu by to bylo úplně košér) a hezky. Prostě v těch interpretovaných jazycích (Python, Ruby, trošku i Scheme) se podobná řešení přímo nabízejí.

[Michal Kubeček]

Mně tedy 'strlen(num)' zase o tolik delší nepřipadá…

[lpd]

Teda to jsou ale dřísty...

[Kyosuke]

Přesně tak, v Lispu bych to taky řešil stejně. A je to.

[Václav HFechs Švirga]

Asi prasím, ale když jsem tohle jednou řešil (C), postupoval jsem obdobně - strlen.

[Lu-Tze]

No to je skutečně elegance sama, pokud teda Python nemá funkci logaritmus.

Nicméně je asi jednodušší násobit než dělit. Co porovnávat s čísly 10^(i*2-1) (i = 1, ..), na prvním větším čísle v téhle posloupnosti se zarazit a rekurzivně aplikovat na "vstup/(předchozí číslo posloupnosti).

[Michal Kubeček]

Logaritmus je první, co člověka napadne, ale to naráží na zaokrouhlovací chyby.

Tu druhou myšlenku bych realizoval spíš tak, že bych šel nejdřív po 10^(2^k) a pak bych půlil interval. Ale když vezmu v úvahu, jaký je maximální počet desítkových číslic pro používané celočíselné typy, vychází mi, že nestojí za to vymýšlet nic přehnaně sofistikovaného.

[Michal Kubeček]

Navíc bychom neměli zapomínat, že spočítat logaritmus je výpočetně výrazně složitější úloha než určit počet číslic celého čísla klasickým postupem. Nesmíme se nechat zmást tím, že to ve zdrojáku vypadá jako "jedna funkce" vs. "ošklivý cyklus".

[Lu-Tze]

Já jsem si nevšiml, že autor načítá řetězec ("vyčistil načtený řetězec"). Měl jsem pocit, že načítá číslo, převádí ho na řetězec a pak vypíše jeho délku. Proto jsem zmínil logaritmus, když už chceme mít takovou "eleganci".

[Michal Kubeček]

Naopak, formulace "vyčistil načtený řetězec" podle mne znamená, že na vstupu dostane řetězec. Pokud píše celý program, ne jen funkci, tak tomu tak vždy je, ať už ho bere z parametrů nebo ze standardního vstupu.

[Lu-Tze]

Však říkám, že jsem si toho původně nevšiml

[Lu-Tze]

Krom toho teda dobře napsaný program by podle mě měl na špatném vstupu zařvat. A taky když očekává na vstupu řetězec a má počítat počet cifer, tak by se měl vypořádat i se vstupy jako " 1" možná i "01" atd.

[ʚĭɞ 🍉]

Ale když vezmu v úvahu, jaký je maximální počet desítkových číslic pro používané celočíselné typy, vychází mi, že nestojí za to vymýšlet nic přehnaně sofistikovaného.

Třeba v Pythonu je omezen velikostí paměti. Na těchto dvou gigabajtech by to mohlo být už krapet zajímavé.

[ajikdpoe]

Length(IntToStr(Abs(cislo)))

[Kyosuke]

Logické řešení spočívá v cyklickém celočíselném dělení dotyčného čísla desítkou a zaznamenávání počtu iterací.

Ne, logické řešení spočívá ve výpočtu logaritmu a vhodném použití jeho celočíselné části, třeba takhle, i když je to hnusné (jen rychlý nástřel): 1+(long)(log(0.5+atol(cislo))/M_LN10). Kdyby na vstupu byl řetězec s číslicemi, tak prosím, ale o tom nebyla řeč.

[Kyosuke]

(Totiž, ten atol() tam nemá co dělat, předpokládám, že už na vstupu je číslo. )

[Josef Kufner]

Hm, napsat to v C je lehký...

void main (int argc, char *argv[]) {
   printf("%d\n", argc > 1 ? strlen(argv[1]) : 0);
}

[frEon]

jak se jmenuje ta knizka? ve skole jsem nasel na nejakym public disku na siti nejspis tu samou, ale uz tam neni a ma kopie se nedochovala :-/ . Myslim ze bych si ji ale mohl sehnad mit nejakou indicii jak ji identifikovat.

[zde]

Na prasárny je lepší perl.

$ perl -e '$_ = 1111; print y///c;'
4

[zde]

Poměrně elegantní řešení..

def pocet_znaku(n):
    r = 1
    while n > 9:
        c = 1
        q = 10
        while q * q < n:
            q = q * q
            c *= 2
        r += c
        n /= q
    return r

[Lu-Tze]

No to je to, co jsem chtěl napsat, akorát se mi tam omylem dostalo násobení místo umocňování.

[Zdeněk Štěpánek]

strlen(inttostr(int)); mi prijde jako zcela legitimni reseni. Ostatne asi proto ze mam radsi jazyky s dynamickym pretypovanim.

Zdenek

[Kvakor]

Ano, obzvlast v interpretovanych jazycich to muze byt i nejrychlejsi a nejefektivnejsi reseni, tedy pokud jazyk nema primo na tohle nejakou hotovou funkci.

Navic, logaritmy pouzit nejdou, protoze u cisel se samymi devitkami to muze hazet divne vysledky (mne osobne se presne tohle stalo), a postupne deleni bude obzlast v intepretovanem jazyce pomalejsi nez optimalizovana knihovni funkce na prevod na retezec.

Ale pokd jde opravu o max. rychlost, tak bych asi pouzil upravenou verzi jiz zmineheho algoritmu s porovnavanim cisel. Stacilo by mit ulozena cisla 0, 1, 10, 100, 1000, 10 000 atd. jako pole, jejich index by byl vlasne pocet cislic (resp. minimalni ceslo s danym poctem cislic, mimo nuly). Pak by stacilo aplikovat klasicke binarni vyhledavani a pokud by se to trefilo mezi dve cisla, vzit to nizsi. Celkova slozitost O(ln(N)), ke N je pocet cislic, zadne logaritmy, zadne nasobeni, pri vhodne udelane tabulce (o velikost 2^n, doplnene cisly vetsimi nez maximum) neni treba ani deleni, staci jen bitove operace.

Ale pokud to nepisete pro osmibitaky a podobne udelatory (obzvlast pro ty, co neumi hardwarove deleni) v assembleru, nema cenu se s necim takovym asi delat