Matematické Fórum

No třeba takto:

for(int i = 0; i < strlen(AnalyzovanyText); i++)
{
    switch(AnalyzovanyText[i])
    {
       case 'a':   NumOf_a++; break;
       case 'b':   NumOf_b++; break;
       case 'c':   NumOf_c++; break;

       // atd... pro vsechny mozne znaky
    }
}

Je to samozřejmě hloupý způsob psaní kódu, protože tam budeš muset ručně vypsat všechny písmena co existují.
Elegantněji by to šlo udělat přes "hodnotu znaku":

int CetnostZnaku[256];

for(int i = 0; i < strlen(AnalyzovanyText); i++)
{
    CetnostZnaku[((int)AnalyzovanyText[i])]++;
}

↑ mirekjiranek:
Ahoj, má MATLAB něco jako asociativní pole, tj. možnost indexovat pole řetězcem? Pak to bude ještě snadnější.

↑ mirekjiranek:

Takže nemá asociativní pole.


V jednoduchosti: 8bitová ASCII tabulka má 256 položek, v rozsahu 0-255.

Takže je potřeba jej incializovat na velikost 256 a nastavit do nuly každý index.
Potom každý index přesně odpovída indexu položky v ASCII tabulce

např. array[65], bude představovat písmeno 'A', protože ascii hodnota písmena 'A' je 65.



jak napsat kód máš nahoře. Ale slovy postupuješ tak.

1) pro každý znak v řetezci musíš získat jeho ascii hodnotu, a tuto hodnotu získaš po indexovaní pole

např. 'H' = 72,

2) potom zvýšíš hodnotu na indexu o 1

array[72] = array[72] + 1

3) potom výsledek vypisuješ tak, že přes každou položku v poli, pokud neni nulová, tak výpíšeš hodnotu, ktera se tam vyskytuje a zaroveň převedeš číslo, kterým indexuješ tabulku na znak a ten taky vypíšeš

např.  print(72 --> 'H', " : " , array[72]) //output        H : 1

↑ LukasM: Opravdu existuje mnoho způsobů, jak to udělat, ale procházet ten řetězec opakovaně je prasárna a ne algoritmus. ;-)

No jo, protože "smazání znaku z řetězce" většinou nejde jednoduše provést. Zpravidla to znamená vyrobení nového řetězce překopírováním částí toho původního.

Můžeme si také znak nahradit nějakým předem zvoleným znakem, ale tím si to zase zkomplikujeme, protože řetězec může obsahovat i tenhle znak.

Stýv napsal(a):

↑ LukasM: Opravdu existuje mnoho způsobů, jak to udělat, ale procházet ten řetězec opakovaně je prasárna a ne algoritmus. ;-)

A to je samozřejmě taky pravda, on ten řetězec nemusí mít jen pět či dvacet znaků. Může mít taky 100Gb, takže ho musíme načítat z disku, když to namísto jedenkrát budeme muset udělat 200x, tak to asi moc super nebude. A to ještě máme kliku, že znaků je jen pár desítek.

Pokud to ovšem budeme dělat nad jinou "abecedou" (třeba 32 bitovými instrukcemi), mohlo by to trvat o dost déle...jako třeba i několik let...

Pak také existuje možnost, že ten řetězec nebude uložený nikde, že to bude stream (bude nám to chodit postupně třeba po ethernetové síti) a musíme si s tím nějak poradit.

Nepřeháníte to trochu? Tazatel je naprostý začátečník, který chce "nějaký nápad", tedy nezná ŽÁDNÝ způsob, jak to udělat. Tak jsem vzal to nejjednodušší co mně napadlo a to jsem ještě zjednodušil, aby se to kolegovi programovalo co nejsnadněji. Že je to v nějakém slova smyslu optimální jsem nikde netvrdil, kdyby se tazatel chytil, sám bych na některé ty problémy upozornil. Navíc že místo mazání mohu znak přepsat nějakým vybraným znakem a tím se vyhnout realokacím řetězce, to si snad není zas takový problém domyslet (MichalAld to zvládl, v C++ se nabízí např. znak '\0'). Nicméně, když už jsem byl takto pranýřován, budu také adresněji reagovat.

Stýv napsal(a):

procházet ten řetězec opakovaně je prasárna a ne algoritmus. ;-)

To je sice super, ale stejně tak dobře bych mohl říct, že tvořit si kvůli krátkému řetězci pole součtů o 256 prvcích je prasárna, a ne slušná práce s pamětí. Nemluvě o tom, že v zadání není nic o tom, že jde o 8-bitový řetězec. Znovu, netvrdím, že to nejde udělat lépe. Jde.

edison napsal(a):

nechápu, k čemu je tam potřeba odmazávat započítané znaky.

No.. nejspíš abych je při dalších průchodech nepotkal znovu. Pouze první znak by mohl zůstávat - když smažu i ten, můžu jít vždy od začátku, čímž kolegovi odpadne jeden index. Pokud má k dispozici nějaký dynamický kontejner (což v MATLABu nepochybně má), mazání kód zjednoduší.

edison napsal(a):

to bude fyzicky obnášet opakované kopírování řetězce

Ano, to bude. Viz text výše.

edison napsal(a):

S takovým přístupem se pak nelze divit, že nový Open Office nezvládne na 4jádrovém procesoru s několika GHz a několika GB RAM v rozumném čase zobrazit graf z tabulky 1000x10, zatímco před mnoha lety to dokázal v pohodě i z řádově větší tabulky na jednojádru se čtvrt GB RAM.

Ano, mirekjiranek hned po dokončení tohoto úkolu otevře repozitář OpenOffice a začne ho ničit neefektivním kódem. Ze stejného důvodu v sekci Fyzika nikdy nepoužíváme rovnici ideálního plynu, nezanedbáváme odpor vzduchu a nic nepočítáme v homogenním tíhovém poli. Jinak by totiž začala po světě padat letadla, a to jenom kvůli nám. (Tím nijak netvrdím, že kód, na kterém záleží, nemá být napsaný chytře.)

edison napsal(a):

Rozumné je prostě inkrementovat index.

Mají se počítat znaky, každému je jasné, že se něco bude inkrementovat. Otázka je co a jak to najít.


MichaloviAld děkuji za podnětné vyprávění o řetězci, co se nevejde do paměti a procesoru s jinou instrukční sadou. Jsou to palčivé problémy, které by mirekjiranek měl urychleně řešit. V podobné souvislosti si dovoluji poznamenat, že znaky nemusejí být 8-bitové (a na rozdíl od Tebou uváděných případů to může možná i v tomto případě nastat). A když se podívám pro změnu na Tvůj kód, v takovém případě je třeba alokovat na to pomocné pole skutečně značné množství paměti. To je už správně? Navíc když už jsem byl donucen to zkoumat, pokud dobře vidím, ve Tvém kódu je neinicializované pole, což je v jazyce C nedefinované chování - tedy mnohem větší problém, díky kterému to nemusí správně zpracovat ani ten řetězec ze zadání.

MichalAld napsal(a):

lze vymyslet ještě i zajímavější algoritmy. Jako třeba si ten řetězec nejprve setřídit...

Nepochybně lze. Ovšem diskuze o tom, jakým způsobem to pole setřídit, aby to fungovalo se streamovaným stringem, který se nevejde do paměti, a přitom se žádný krok neprovedl zbytečně bude nejspíš dlouhá. A já se jí účastnit nebudu:-)



"Správné" řešení je patrně to asociativní pole, kde nějaký efektivní algoritmus rychle najde správné počítadlo, aby se mohlo inkrementovat (a když ho nenajde, vytvoří ho). Pokud mirekjiranek neví, co to je, asi ho nemůže použít. A protože je evidentně začátečník, asi si ho také nenapíše hned sám (byť pokusy o optimalizaci budou k něčemu takovému nejspíš směřovat). Takže to asi bude muset udělat nějak jinak. Rád se přiučím, jak to udělat neprasácky a jednoduše současně.

Nikdo se k tomu nemá, já zas neumím Matlab... Tak to zkusím obecně:

Budeme potřebovat pole 256 čísel (na začátku všechny 0), které nazveme dejme tomu seznam a jednu číselnou proměnnou jménem index.

Pak bude potřeba nějaký převod ze znaku na číslo (v c to nemí potřeba, protože řetězec je pole bajtů, dost jazyků na to má nějaké funkce, které se jmenují třeba asc, ascii, nebo code).

Pak musíme nějak získávat jednotlivé znaky (v c je to zas jaksi "samo", jinde na to bývají funkce, často trochu univerzálnější, např. mid ve VB vytáhne z jednoho většího řetězce menší kousek a pro náš účel pak budeme požadovat délku 1).

Pak to chce nějakou funkci na délku řetězce (len, strlen a pod.), nebo nějak poznat jeho konec (např. v c je za koncem prvek s hodnotou 0).

Dále to chce nějaký cyklus, třeba for, ten je skoro ve všech jazycích.

Takže uděláme cyklus, ve kterém se vezme znak z pozice index, jeho kód se použije jako adresa do pole seznam a v něm se hodnota daného prvku zvýší o 1. Pak se index zvýší o 1 a pokud nejsme na konci řetězce, cyklus se opakuje. Po ukončení cyklu máme v seznamu počty znaků s patřičnými kódy.

Při vypisování seznamu pak budeme potřebovat rozhodování (téměř všude if) a převod z čísla na znak (chr, char a pod).

Zase cyklus. Projede seznam a vypíše znaky, které mají nenulový počet s jejich počty.