[JAVA] počet písmen ve Stringu

C++, C#, Visual Basic, Delphi, Perl a ostatní

Moderátor: Moderátoři Živě.cz

Odeslat příspěvekod cebbek 26. 10. 2006 23:00

Zdravím, potřebuji zjistit, kolik písmen obsahuje String, tzn. např. slovo VEVERKA obsahuje 5 písmen. Existuje nějaká sepciální metoda, která by to zjistila? Kdyby ne, tak uměl by to někdo naprogramovat? Já nad tím bádám už dvě hodiny a furt nic. Jsem zoufalý
cebbek
Junior

Odeslat příspěvekod randomizer 26. 10. 2006 23:14

Uz jsem dlouho nic nepsal, tak muj navrh muze byt celkem historii a zbytecne slozity, ale ja bych to resil takto:

- vytvorit pole o 26 prvcich ... pocet pismen v abecede, pro tento priklad tedy anglicka
- pole bude defaultne obsahovat v kazdem prvku nulu
- prochazet retezec znak po znaku a jednotlivym bunkam pole menit index z nuly na jednicku, pokud jiz jednicka je nastavena, tak nechat byt ... takze pro veverku to bude na konci vypadat "10001000001000000100010000"
- az je projety cely retezec, tak jen secist, kolik bunek obsahuje jednicku
randomizer
Kolemjdoucí

Odeslat příspěvekod cebbek 26. 10. 2006 23:41

díky moc, už jsem to tvým způsobem vyřešil :wink:
cebbek
Junior

Odeslat příspěvekod Kyosuke 26. 10. 2006 23:42

Kód: Vybrat vše
int pismen(String s)
    int bitmap = 0;
    int n = 0;
    String velka = s.toUpperCase();
    for(int idx = 0 ; idx < velka.length ; idx ++)
        bitmap |= 1<<(velka.charAt(idx)-65);
    while (bitmap != 0) {
        n = n + 1;
        bitmap = bitmap & (bitmap - 1);
    }
    return n;
}


Netestováno, ale mělo by fungovat.

Mimochodem, v Ruby se to redukuje na
Kód: Vybrat vše
pocet = string.downcase.split(//).uniq.size
:-D
Kyosuke
Junior

Odeslat příspěvekod wojta 27. 10. 2006 08:01

Nevím, jestli jsem přesně pochopil, co je cílem. Na té VEVERCE to moc demonstrované není, ať počítám, jak počítám, tak má 7 písmen.
Chtěl jsi zjistit počet písmen v řetězci, čili počet znaků bez mezer (a jiných bílých znaků)?
Co takhle?
Kód: Vybrat vše
String veverka="Skakala veverka pres cely les";
int pocet=veverka.length()-veverka.split("\\s").length+1;
//pocet je ted 25
Naposledy upravil wojta dne 27. 10. 2006 08:09, celkově upraveno 2
wojta
Pokročilý
Uživatelský avatar

Odeslat příspěvekod Kyosuke 27. 10. 2006 08:04

On chce očividně spočítat, kolik různých písmen to slovo obsahuje.
Kyosuke
Junior

Odeslat příspěvekod wojta 27. 10. 2006 08:06

Aha, tak na to, co jsem napsal zapomeňte. Navíc tam mělo být +1.
wojta
Pokročilý
Uživatelský avatar

Odeslat příspěvekod wessan 27. 10. 2006 17:32

Kyosuke píše:
Kód: Vybrat vše
int pismen(String s)
    int bitmap = 0;
    int n = 0;
    String velka = s.toUpperCase();
    for(int idx = 0 ; idx < velka.length ; idx ++)
        bitmap |= 1<<(velka.charAt(idx)-65);
    while (bitmap != 0) {
        n = n + 1;
        bitmap = bitmap & (bitmap - 1);
    }
    return n;
}


Netestováno, ale mělo by fungovat.

Mimochodem, v Ruby se to redukuje na acode]pocet = string.downcase.split(//).uniq.size[/code] :-D


jaka je asymptoticka slozitost toho kodu v ruby?
wessan
Junior

Odeslat příspěvekod miho 27. 10. 2006 18:14

Nebudu ti psat primo kod ale snad ocenis i nakopnuti spravnym smerem :-) Coz takhle vytorit si pomocny retezec tmp, rozsekat puvodni retezec na pismena a zarazovat do retezce tmp pekne po jednom pokud uz tam neni. Delka pomocneho retezce je vysledkem.

Dalsim zpusobem je zarazovani pismen do hasove tabulky. Tady by slo dosahnout linearni slozitosti.
miho
Hlavní administrátor
Uživatelský avatar

Odeslat příspěvekod Kyosuke 27. 10. 2006 19:52

wessan píše:jaka je asymptoticka slozitost toho kodu v ruby?

Viděl bych to předběžně na O(N.log(N)), což mi nepřijde jako tragédie (zkusím ověřit), ale hlavně mi tahle poznámka *****í rýpalstvím a Předčasnou Optimalizací (TM). :-D Zlinearizovat to v případě potřeby není problém, ale tohle jsem napsal rychle, jednoduše a vím, že to nemusím ladit. ;-) Pravda, trošku jiné design assumptions než v té javovské verzi, ale rozhodně dse vyznám mnohem víc ve smalltalkovských a rubínových kolekcích než v javovských, něčím inteligentnějším v případě javovské verze bych si jen přidělal prohledávání javadocu do hloubky. :-D Krom toho stejně pochybuju, že bych to udělal tak krátké.
Kyosuke
Junior

Odeslat příspěvekod wessan 27. 10. 2006 22:06

Kyosuke píše:
wessan píše:Zlinearizovat to v případě potřeby není problémo/quote]


bojim se ze to bude problem, puvodne jsem to videl jeste na vetsi slozitost (ale nevim jak je iplementovana uniq) ... protoze metoda "uniq" podle me z pole vyradi duplicitni prvky a tohle si nejsem jisty ze v linearnim case pujde

jinak udelat postup tak, ze se stringu udelam pole, vyradim z nej duplicity a zjistim jeho delku mi prijde dost silene ... co kdyz to nebude jen slovo veverka ale 10MB dokument?

pokud jsem ten zapis v ruby pochopil dobre, tak je to skutecny prasacke a pouziva uplne jiny a daleko mene efektivni algoritmus ... jestli jsem to pochopil spatne tak se omlouvam
wessan
Junior

Odeslat příspěvekod Kyosuke 27. 10. 2006 22:41

wessan píše:bojim se ze to bude problem, puvodne jsem to videl jeste na vetsi slozitost


1. průchod polem je lineární operace.
2. inkrementování prvku v hashi, případně jeho vytvoření, pokud zatím neexistuje, je amortizovaně lineární operace.

Nástin implementace:
code]c = Hash.new(0)
aString.each_byte {|b| c[b]+=1}[/code]

Kde je ten problém, kterého se bojíš?

Kyosuke
Junior

Odeslat příspěvekod wessan 27. 10. 2006 22:54

nevim ale prijde mi to takove silene reseni ... veverku jsem bral jen jako trapnou ukazku aby bylo videt co je cilem algoritmu a predpokladal jsem ze ten program nema fungovat co nejvice neefektivne

az budou kompilatory umet vestit co kterym zapisem vlastne programator myslel, tak to bude ok ... jinak mam zkusenosti prave s programatory, kteri delaji ve scriptovacich jazycich, ze to resi podobnymi zverstvy i ve vetsim meritku

napsat neco kratce je sice bezva, ale vede to k tomu, ze z algoritmu ktery vypada jednoduse diky zapisu se na pozadi stava priserna obluda a kdyz se takove "jednoduche reseni" pouzije na vsechno ... tak stoho bude jedno reseni, ktere se pro hw stane nocni murou

v podstate ukazka v jave je dlouze popsany jednoduchy algoritmus a ukazka v ruby jednoduse zapsany slozity algoritmus

samozrejme programujte jak chcete, dokud nepotkam vas kod tak je mi to prakticky jedno
wessan
Junior

Odeslat příspěvekod Kyosuke 27. 10. 2006 23:20

Stále ještě jsi nedefinoval „zvěrstvo“. Upozorňuju, že „programátoři ve skriptovacích jazycích“ (+ lispeři a smalltalkeři), které znám, jsou výborní programátoři – právě proto vědí, že čas ušetřený jazyky, jako je Ruby, Lisp a Smalltalk mohou věnovat algoritmické optimalizaci v těch místech, kde to má smysl, a vytvořit tak nejlepší řešení v nejkratší době. Prasata samozřejmě najdeš všude, před těmi tě Java nezachrání, ba spíše naopak, jakožto jazyk pro masy (= protiklad jazyka pro inteligentní lidi, viz Graham).

Předhodil jsem svému kódu megabajt shakespearových tragédií, běželo to jednu sekundu na 1GHz P3. Pořád Ti to přijde pomalé a prasácké? Navrhni tedy něco rychlejšího než cyklus s vkládáním do množiny, což jsou dvě ze tří řešení, která jsem tu uvedl (jedno přes hash, jedno specializované přes bitový vektor).
Kyosuke
Junior

Odeslat příspěvekod Benjamin 27. 10. 2006 23:37

Kyosuke píše:Ten zápis v Ruby je naprosto adekvátní slovu VEVERKA. :-D -/quote]


Naprosto neadekvatni bylo tahat nejake Ruby do threadu, kde se nekdo pta jak vyresit neco v Jave. :P :P :P
Umělá inteligence není soupeř pro přirozenou hloupost.
Benjamin
Junior
Uživatelský avatar

Další stránka

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 0 návštevníků