Diskuze: Funkce v Pythonu. Musí něco vrátit.
DarkCoder:30.8.2023 13:42
Pokud je použito return bez ničeho, sloučí to pro předčasné ukončení funkce bez vrácení hodnoty. Použití return v tomto kontextu není vhodné, neboť jakmile je proveden alespoň jeden prohoz, bude proměnná nastavena na True a tato hodnota bude platná po zbytek provádění funkce. Testy na swapped pak akorát zpomalují algoritmus.
Zde je jiná ukázka použití return bez přidané hodnoty:
def check_and_print_string(input_string):
if input_string == "Hello":
return
else:
print("Zpráva není Hello")
# Volání funkce s různými argumenty
check_and_print_string("Hello") # Funkce skončí pomocí return
check_and_print_string("Hi") # Vypíše "Zpráva není Hello"+20 Zkušeností
+2,50 Kč
Insert. Zkus tu moji stranku, treba to z toho pochopis.
57226 - na zacatku mas nahodne cisla
5 -> [5] vemes dalsi a zaradis ho do out-pole, porovnavas od zacatku out-pole (out-pole mas na zacatku prazdne)
7 -> [5, 7] - pak vemes dalsi a zaradis ho do out-pole, porovnavas od zacatku out-pole, cili 5 a 7
2 -> [2, 5, 7] - porovnavas 2 a 5, 2 je mensi nebo rovno, jde tedy pred 5, uz neporovnavasNo, a abys mohl zaradit cislo jinam nez na konec, tak je nutne cast pole posunout. To se nejjednoduseji dela od konce kopirovanim pole[len+1] = pole[len], pole[len+0] = pole[len-1], pole[len-1] = pole[len-2]...
[5, 7]
[_, _, 7] pozn: _ podtrzitko, jakoze s temi cisly nic nedelam
[_, 5, _] a na prvni pozici ted muzu dat tu dvojku
[2, 5, 7]
A kdyz potrebujes dat neco doprostred, treba pred d
[a, b, c, d, e, f, g]
[a, b, c, | d, e, f, g] - od 'g' po 'd' to posunes o +1 doprava
[a, b, c, d, d, e, f, g] - 'd' a 'd' je tam duplicicne a prvni 'd' nahradis novym cislem, ktere ma byt pred 'd'
[a, b, c, new h, d, e, f, g]To dela ten druhy cyklus v insert sortu.
A zajimavejsi je, zmenit ten prvni algoritmus, hledani kam zaradit na puleni
intervalu. Vis, ze druhe pole je uz serazene. Takze, kdy nove cislo bude vetsi
nez cislo v polovine serazeneho pole, tak proti beznemu insertsortu preskocis
polovinu pole uz v prvni kroku. Takto postupujes dal.
Pokud je pole dlouhe 1.000.000 prvku, tak novy prvek zaradis do 7
porovnani. Coz je super, ne?
Klasicky Insert-top-sort, pokud by musel prvek zaradit na konec potrebuje
1.000.000 porovnani. To je sakra rozdil.
Problematicka cast je vsak stale nutnost posouvat pokazde cele pole 
Cili, ani insert sort bych nedoporucoval. Ale pozor, insert-middle-sort ma uplne
nejmensi pocet operaci porovnani ze vsech. Az na tou pomalou ast je to skvely
algoritmus.
Musis si uvedomit, ze pracujes se serazenym polem a staci narazit na prvni hodnotu, ktera nevyhovuje podmince a nebudou vyhovovat i zadne dalsi. Takze, to je ta pozice, kam musis to nove cislo zaradit.
Prvni cyklus prohazi pole
for i in range(1, len(zadanePole), 1)
klic = zadanePole[i]
01234
ECADB
i = 1, 2, 3, 4
klic = C, A, D, B --- vynechava prvni hodnotu E
... to je asi jasneDruhy cyklus zacina predposledni hodnotou (posledni je v klic) a jde na
zacatek. Ale, musi tam byt podminka pro j >= 0, aby neskoncil na
pozici` j=-1`.
while (j >= 0 and zadanePole[j] > klic ):
zadanePole[j + 1] = zadanePole[j]
j = j - 1abcdefgh C fdhbvuea - serazene pole + C (nova hodnota, klic) + nahodna data
Porovnavas v serazenych datech od konce
a kdyz to nesedi, zadanePole[j] > klic, tak zkopirujes porovnavanou hodnotu na jeji pozici+1, zadanePole[j + 1] = zadanePole[j]
abcdefgh C fdhbvuea, klic = C (C mam zalohovane, muzu tam zapsat, co chci a to take delam)
abcdefgh H fdhbvuea
abcdefgG H fdhbvuea - a postupne prepisuji i vsechny ostatni, dokud plati podminka cyklu
abcdefFG H fdhbvuea
abcdeEFG H fdhbvuea
abcdDEFG H fdhbvuea - a ted prestava platit podminka `C (pole[j]) > C (klic)`
0123
j = 3, j+1 = 4 a tam chces umistit klic
abcdDEFG H fdhbvuea - cili, prepises male 'd' klicem 'C'
abcCDEFG H fdhbvueaSnad to je aspon trochu srozumitelne. Ono se to spatne vysvetluje
A take muze byt matouci, ze porovnavas od konce. Ono je to jedno, od konce, od
zacatku, samozrejme nejlepe od stredu . Zamerne je vybrane od konce, protoze
potrebujes posouvat ty hodnoty. V pripade porovnani od stredu pouzivam dalsi
cyklus jen na to posouvani. Tady delas oboje najednou, zjistujes, kam umistit a
zrovna posunujes take pole.
A ne, pro ten muj insert do stredu plati, ze pomaly neni, pomale je jen to
posouvani pole
Coz ale umi moderni procesor urychlit predvidanim predchozi operace. Dokonce
jsem videl urychleny bubble sort, ktery byl rychlejsi nez quick-sort. A, je
dobre vedet, ze quick-sort neni stabilni. Jde napsat stabilne, ale k tomu
potrebujes dalsi pole. A kdyz mas uz 2 pole, tak je nejrychlejsi a uspornejsi
spojovani serazenych poli delky 1, 2, 4, 8, 16....
Tys to spatne pochopil
i = 1, 2, 3, 4, - cyklus 1 pocita takto
j = 0, 10, 210, 3210 - cyklus 2 pocita pro kazde i od konce
hodnota klic se vyjme z pole z posledni pozice za serazenou casti
mame jine cisla nez ty a jsem nekde uprostred cyklu pro icko
abcdefgh C fdhbvuea - pred C jsou serazene cisla, C + cisla za nim jsou ta, ktera do te predchozi casti chces vlozit.Tu serazenou cast tedy musis prohledat, ze predu nebo ze zadu. Tvuj cyklus ji prohledava ze zadu.
Jestli to potrebujes s cisly, tak treba
abcdefgh C fdhbvuea
13579999 5 0524386 - cisla na zacatku jsou uz serazena, ostatni jsou nahodna
012345678 9 ............. - i
i = 9, pole[i] = 5 = klicNebo, bych mozna pridal princip insert sort pri prohledavani zhora dolu (zleva doprava)
# uživatel zadává čísla: 95, 2, -5, 7, 0
klic = 95, out = []
out[0] = 95
klic = 2, out = [95], j = 0 # serazene pole prohledavas cyklem od min po max,
# kde min = 0 vzdy a max = len(out)
if (klic>out[j]) j = j + 1 else insert_on_pos(j) # 2>95
if (2>95) else insert_on_pos(j)
klic = -5, out = [2, 95], j = 0
if (-5>2) else insert_on_pos(j)
klic = 7, out = [-5, 2, 95], j = 0
if (7>-5) j = j + 1
if (7>2) j = j + 1
if (7>95) else insert_on_pos(j) # j = 2
klic = 7, out = [-5, 2, 95], j = 0
if (0>-5) j = j + 1
if (0>2) else insert_on_pos(j) # j = 1Tohle je asi celkem jasne, ze prohledavas serazene pole, dokud je cislo
mensi. Pak narazis na misto, kde je vetsi a tam to nove cislo (klic) chces
umistit.
A to umisteni provedes tak, ze pravou cast posunes o 1 doprava. Posouvani se
dela od konce.
cyklus start: k = len(out) - 1
cyklus increment: k = k - 1
cyklus end: k==J
posun: out[k+1] = out[k]
za cyklem insert: out[J] = klicVe tvem kodu to delas podobne, ale prohledavas serazene pole od konce, abys
nasel pozici, kam cislo patri. To je asi jedno, zda od zacatku nebo od konce,
ne? A jeste nabizim tu treti moznost, prohledavat pulenim intervalu. Ale ten kod
by byl jeste slozitejsi. Ukazka viz ta ma stranka, asi 30 radku
Py nabizi jeste jinou moznost insertovani. Ta se ti mozna bude libit a zdat jednodussi. Ale vyzaduje vic pameti. Snad to napisi spravne, pac PY moc nepouzivam, uz.
pos = najdi_pozici_pro_vlozeni() # dopln si kod pro hledani pozice
out = out[0:pos-1] + klic + out[pos:len(out)]
# pole[a:b] zkopiruje pole do noveho pole od A po BCili, kdyz vis, na ktere misto to chces umistit, tak si zkopirujes cast pred, cast za a mezi to vlozis klic. Da se tim nahadit tato cast kodu, ale program to zpomali, nepatrne a bude potrebovat dalsi pamet pro kopirovana pole jako celky a ne bunku po bunce.
while (j >= 0 and zadanePole[j] > klic ):
zadanePole[j + 1] = zadanePole[j]
j = j - 1
zadanePole[j + 1] = klic
while (j >= 0 and zadanePole[j] > klic ):
j = j - 1
zadanePole = zadanePole[0:j] + klic + zadanePole[j:len(zadanePole)](ale, mozna tam nekde melo byt j-1 nebo j+1, nechce se mi ted premyslet)
Tak, tak, pokud te programovani zajima, tak dojde i na to, ze cizi kod
pochopis. Pochopit muj popis je horsi
(pozor, nazvy algoritmu jsou pojmenovane, jak jsem chtel ja, nikoliv nejaka
literatura)
Ale, muzu ti ukazat jiny algoritmus, ktery snadneji pochopis. Ale kod ma sileny,
pac to jinak ani nejde.
https://peter.mlich.cz/…/sorting.htm#…
Jestli jsi nekdy soutezil, tak je to klasicky herni pavouk. Dva zapasi proti
sobe, vitez postupuje do dalsiho kola.
A dalsi krok je odstraneni viteze a prepocitani casti pavouka, abys zjistil
druheho nejlepsiho (v pripade sortovani, druhe nejmensi cislo).
A nebo, snadny na pochopeni by mohl byt i tento:
https://peter.mlich.cz/…/sorting.htm#…
Jedna se o spojovani serazenych seznamu.
Mas hromadky, ktere jsou serazene (protoze je tam jeden prvek, v kazde, tak jsou
serazene).
Spojis je na hromadky po dvou tak, ze porovnavas v kazde prvni cisla a to mensi
prelozis na treti hromadku na zacatek. Opakujes, dokud nevycerpas jednu
hromadku. Ze zbyle hromadky proste cisla presunes do te treti.
Treti hromadka je pak opet serazena, jeji velikost je dvojnasobna, spojujes ji s
dalsi takovou. Atd
1) = === ==== ==
2)
=
===
==
====
3)
=
==
===
====Opet, kod neni uplne snadne napsat. Pokud bys chtel pouzit jen jedno pole,
tak musis neustale presouvat jako u insert-sortu.
Pokud pouzijes treti hromadku (cili vice pameti, dve pole), tak je pocet presunu
do 10 mezi polem1 a 2.
Nebo, na to muzes jit jinak, zjistit si, ktera casti jsou uz serazene a ty
spojuj.
https://peter.mlich.cz/…/sorting.htm#…
7
2
3
5
6
0
1
4
serazene casti jsou
7
2
3
5
6
0
1
4A pak spojujes serazene casti, jako v predchozim pripade.
Jestli chces delat testy, neni problem si najit nejakou stranku, kde staci
pridat jen algoritmy a py kod asi taky najdes.
Ja si treba takove testy delal v JS, protoze JS dneska funguje na kazdem pc a
webu.
https://peter.mlich.cz/…g4-pokus.htm
Klikni start u prvniho testu. Dela to, ze ma limit asi 70ms a mezitim se pokusi
seradit co nejdelsi pole. Cili, cim delsi rada cisel na radku, tim je algoritmus
rychlejsi. Vidis, ze js kod Timsortu, ktery jsem nekde vygoogloval, hrave
prekonava vestaveny algoritmus javascriptu (u mne ve Firefox webbrowseru, v117).
Jenze, takove mereni je dost pochybne, firefox ma optimalizace pro opakovani
stejneho kodu pomoci procesoru. Ja tam mam treba serii cisel
4 (pro 1.000) 1 1 2 4 8 10 18 39 (pro 100.000), zacal se 4s, pak naraz skocil na
1s, coz je nesmysl, kdyz je pole 2x vetsi
A takovy Tournament sort (ja ho oznacuji jako SelectPyramid), si take nevedl
spatne.
Cili, spravne by mel byt nejrychlejsi vestaveny sort. Coz by byl, kdyby nebylo
optimalizaci a ja ten kod pro testovani nemusel opakovat.
Zobrazeno 46 zpráv z 46.