Diskuze: Jednoduchá rekurzivní metoda

V předchozím kvízu, Online test znalostí Java, jsme si ověřili nabyté zkušenosti z kurzu.

Aktivity

Adam Bucher

Člen

Adam Bucher:9.2.2017 20:16

Ahoj Javisti,
mám na vás menší dotaz. Občas dělám příklady z této stránky: CodingBat. Dnes jsem dělal příklad „countHi2“. Jde o to napsat rekurzivní metodu zadanou takto: Je daný string. Rekurzivně spočítejte počet výskytů "hi" v daném stringu, nicméně nepočítejte "hi", je-li před tím písmeno "x" ("hi" i "x" <-- lowercase). Na dané stránce je zadání i s příklady výstupu.
Důvod, proč sem píšu, je, že si nejsem jistý logikou svého řešení. I když metoda funguje správně, jestli mi neuchází něco, co by to řešení mohlo zjednodušit.
Kromě jednoduššího řešení, budu rád za každé „Já bych to řešil jinak, takto: ...“

Moje řešení:

public int countHi2(String str) {
  if (str.length() == 2 && str.equals("hi")) return 1; //případ, kdy jsou "hi" jediné dva znaky stringu str
  if (str.length() < 3) return 0; //0-2 znaky ve stringu, ale pokud 2, "hi" už to není (podmínka výš)
  if (str.substring(0,2).equals("hi"))
    return 1 + countHi2(str.substring(2));
  if (str.substring(1,3).equals("hi")) {
    int p = 0;
    if (str.charAt(0) != 'x') p = 1;
    return p + countHi2(str.substring(3));
  }
  return countHi2(str.substring(1));
}

Předem díky za každou reakci :-) .

Odpovědět

9.2.2017 20:16

Petr

Člen

Petr:10.2.2017 15:51

Ja bych to treba zapsal takhle:

public int countHi2(String str) {
  if(str.startsWith("hi")) {
    return 1 + countHi2(str.substring(2)); //pricte jedna k vysledku a zavola funkci na zbytek retezce
  } else if (str.startsWith("xhi")) { //ignoruje xhi a zavola funkci na zbytek retezce
    return countHi2(str.substring(3));
  } else {
    return (str.length() > 2)? countHi2(str.substring(1)) : 0; // zjisti jestli retezec obsahuje aspon 3 znaky tj. jestli ma cenu pokracovat dal, pokud ano zavola funkci na celem retezci bez prvniho znaku, jinak vrati 0
  }
}

Ten tvuj kod tam ma myslim podminky navic. Abych pravdu rekl tak tohle nema s javou moc spolecne, tohle spis zavani funkcionalnim programovanim a navic je to extremne neefektivni protoze tam vznika spousta objektu, ktere se na konci vypoctu zahodi => zbytecna zatez pro garbage collector.

Nahoru Odpovědět

10.2.2017 15:51

Adam Bucher

Člen

Adam Bucher:10.2.2017 17:15

Velice pěkné řešení.

Mimochodem ten podmínkový zápis return jsem doteď neznal, ale koukám, že ušetří programátorovi pár vteřin .

Mám dotaz na to, co jsi psal:

je to extremne neefektivni protoze tam vznika spousta objektu

Rekurzivní metody při každém znovuzavolání vytváří nový pomocný objekt? Nebo jsem to špatně pochopil?

Jinak díky za reakci. Porovnávat pomocí startsWith je v tomto případě nejen přehlednější, ale hlavně nemusíš pojistit, abys, jako já, nemohl používat substring s indexy, které neexistují. To jsem si neuvědomil a akorát jsem si to ztížil.

Nahoru Odpovědět

10.2.2017 17:15

Petr

Člen

Petr:10.2.2017 17:57

Ten "podminkovy zapis" nesouvisi primo s return, rika se tomu tercialni operator a je nutne to pouzivat s mirou, na takovyto kratky vyraz se to hodi ale kdyby to bylo neco delsi tak doporucuji rozepsat do klasickeho if / else.

Rekurze sama o sobe neni efektivni pokud neni jazyk kolem ni postaveny (funkcionalni jazyky), v jave pokazde kdyz zavolas funkci / metodu tak si program zapamatuje aktualni stav aby se, az metoda nebo funkce ukonci, mohl program vratit tam, kde byl pred volanim funkce (napr. hodnoty lokalnich promennych pred volanim funkce atd.). Takze existuje tzv. zasobnik volani (call stack), do ktereho se to vsechno uklada a ten ma jistou sice velkou ale rozhodne ne neomezenou kapacitu. No a to ukladani stavu a prace se zasobnikem volani je samozrejme rezije navic.
Ale to jsem nemel na mysli, ja mel na mysli volani metody substring z tridy String, ktere pokazde vytvori novou instanci tridy String:

public String substring(int beginIndex, int endIndex) {
        if (beginIndex < 0) {
            throw new StringIndexOutOfBoundsException(beginIndex);
        }
        if (endIndex > value.length) {
            throw new StringIndexOutOfBoundsException(endIndex);
        }
        int subLen = endIndex - beginIndex;
        if (subLen < 0) {
            throw new StringIndexOutOfBoundsException(subLen);
        }
        return ((beginIndex == 0) && (endIndex == value.length)) ? this
                : new String(value, beginIndex, subLen);
    }

Tohle je vytazene z JDK8, jak vidis pokazde vola konstruktor a vytvori novy objekt. Rekneme ze mas String o delce par desitek tisic znaku, kdyz to budes prochazet rekurzi po znacich tak ti vznikne v nejhorsim pripade zhruba tolik objektu String kolik mas znaku ve Stringu a vsechny se nakonec zahodi.
Tohle samo o sobe ti javu nepolozi, ale pokud to budes volat casto a budes provadet jine podobne ne prilis efektivni operace tak se to nasklada a aplikace stravi vetsinu casu tim ze se snazi uklidit pamet, no proste cesta do pekel.

Pokud tuto ulohu budes chtit resit efektivne pak bys k tomu musel pristoupit jako k poli znaku a prochazet to po znacich v cyklu a nebo by to jeste melo jit pres regularni vyraz.

Abych nevytvoril mylny dojem, ze odsuzuji rekurzi - to v zadnem pripade, rekurze v urcitych pripadech zjednodusi a zprehledni kod, ale musi se nad tim trochu premyslet a necpat ji vsude.

Nahoru Odpovědět

10.2.2017 17:57

Adam Bucher

Člen

Adam Bucher:10.2.2017 20:23

Aha, fajn.
Moc děkuju, s Javou a zároveň celkově s programováním zatím nejsem nijak daleko, ale pomalu se učím víc a víc a tvůj komentář mi rozšíril obzory.

Nahoru Odpovědět

10.2.2017 20:23

Naučíme tě pracovat na home-office.

Zjistit více...

Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 5 zpráv z 5.

Nejčastěji vyhledáváné

Diskuze: Jednoduchá rekurzivní metoda