BGAFC Vendégkönyv

Σ: 1 post

TCH (statz)

#1, Főfasz (10443)

4387 | #274a | ^ | Idézet | Sat, 24 Aug 2013 03:34:13 +02

84.3.*.*

*.catv.pool.telekom.hu

@kemi:
Ilyenkor mi a teendő?

Megkérdezni, hogy miért nem jó, mi nem jó, járuljanak már kissé hozzá a szakmai fejlődésedhez.

@kemi:
Itt a kód amit beadtam.

Nem jó a kód kemi: azt kérték, hogy ha azonos elemeket tartalmaz, akkor adjon vissza None értéket, de te ezt hibásan vizsgáltad le, csak azt nézted, hogy az aktuálisan vizsgált elem nagyobb-e, mint a letárolt legnagyobb, na de mi van, ha kisebb? Ezt nem vizsgáltad le és ennek megfelelően, ha a tömb legelső eleme a legnagyobb, akkor a belső if soha nem fog lefutni és a van változó hamis marad.
Röviden, ha a tömb első eleme a legnagyobb, akkor a kódod None-t fog visszaadni, akkor is, ha különböznek az elemek.
De van benne egy másik hiba is: a második legnagyobb elem vizsgálata is ugyanez a hiba miatt nem jó, ugyanis ha a legelső elem a legnagyobb, akkor a végére a lastmax nem a második, hanem az első legnagyobb értéket fogja tartalmazni, hiszen az elején azt raktad bele és mint az előbb tisztáztuk az if nem fog lefutni, tehát az is marad benne.

Ahhoz, hogy ne None-t adjon vissza és a második legnagyobb értéket is helyesen találja meg, ahhoz több dolog is kell:
• Egyfelől, hogy a lastmax kiindulási értéke ne egyezzen meg mx-ével, hanem attól kisebb legyen. Viszont elkerülendő, hogy ne okozzon fennakadást, ha a kiindulási értéke nem létezik a tömbben, így a lehető legkisebb értéknek kell lennie - ami a Python lebegőpontos változóiban a mínusz végtelen, azaz a -inf - mert ennél kisebbet a tömbben nem találhat, csak egyenlőt vagy nagyobbat, tehát vagy létezik, vagy szükségszerűen cserélődik egy létezőre.
• Másfelől az kell még, hogy a ciklus ne 0-ról, hanem 1-ről induljon és a legelső if ágban összehasonlítsa a tömb jelenlegi elemét az előzővel, ha nem egyformák, akkor lesz a van igaz.
• Harmadfelől szükséges még a lastmax és az aktuális elem összehasonlítása a ciklus végén, ha az aktuális elem nagyobb, viszont a maximumnál meg kisebb, akkor cserélni kell!

Azonkívül for ciklus felső határának felesleges körönkénti újraszámítása miatt is bele lehet kötni, ugyanis a len(a) minden körben le fog futni, az pedig felesleges idő és erőforráspazarlás - hacsak menet közben nem manipulálod a tömböt, de itt ilyen nincs. Ez ugyan nem működési hiba - a kód ettől még menne - ez csak tervezési hiba, de annak elég vaskos.

Meg lehet még kötözködni azon is, hogy mivel a ciklusban a tömb aktuális elemére sokszor hivatkozol, ezért azt kiteheted egy normál változóba, hogy ne kelljen annyiszor indexelnie, ugyanis a scriptnyelvek a typejuggling miatt a tömböket elég nehézkesen kezelik, de ez már inkább szépséghiba. Nem nagy, de nem is kicsi. (Amúgy az előző elem indexelését is meg lehet spórolni, csak egyszer kell a ciklus előtt megcsinálni, de ez már tényleg marginális optimalizáció.)

Meg, ha nagyon szarrágó az ember, akkor a végén abba is bele tud kötni, hogy van benne egy felesleges negálás, egyszerűen megcseréled a két ágat és megspóroltál egy felesleges műveletet, de ez már csak apró szépséghiba.

Ez az algoritmus helyesen így nézne ki:

def max2nd(a):
    l = len(a)
    if l <= 1:
	return None
    mx = a[0]
    lastmax = -inf
    van = False
    f = a[0]
    for i in range(1, l):
	e = a[i]
	van = van or (e != f) # ez gyorsabb, mint, ha azt irnam, hogy if e != f: van = true
	f = e
	if e > mx:
	    lastmax = mx
	    mx = e
	if e > lastmax and e < mx:
	    lastmax = e
    if (van):
	return lastmax
    return None

Nem teszteltem le, de elméletileg így kéne, hogy legyen.

De lehet, hogy ők az N-edik elem keresésére gondoltak, de ha a második legnagyobb elem kell, akkor amint a mellékelt forrásból is látszik, nincs szükség több ciklusra, vagy rekurzióra.
Olyat is lehetett volna csinálni, hogy max()-al kirántjuk a legnagyobb elemet a tömbből, aztán a mi ciklusunk megkeresi a legnagyobb, ennél kisebb elemet, de hiába natív a max(), egy jókora tömbön már lassabban fog végigmenni a max() meg az egy if-es for, mint a max() nélküli két if-es for.

Ballmer is wistavonul, hehe.