1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
|
<!DOCTYPE html>
<html lang="sl">
<head>
<meta charset="utf-8" />
<title></title>
<link rel="stylesheet" type="text/css" href="/css/codeq.css" />
<link rel="stylesheet" type="text/css" href="../../style.css" />
<!-- KaTeX -->
<link rel="stylesheet" href="/css/katex-0.6.0.min.css">
<style> .katex { font-size: 1.1em !important; } </style>
<script src="/js/katex/katex-0.6.0.min.js"></script>
<script src="/js/katex/auto-render-0.6.0.min.js"></script>
</head>
<body>
<p>Matematiki si lahko privoščijo opisati množico dvakratnikov vseh naravnih
števil, katerih kvadrat je manjši od 120, takole:
\(S=\{\,2\cdot x\mid x \in \mathbb{N},\ x^2<120\,\}\). Mi tudi.</p>
<h2>Seznami</h2>
<p>Vendar pojdimo lepo počasi. Začnimo s tistim, kar najbolj poznamo: s seznami.
Doslej smo jih zapisali tako, da smo v oglatih oklepajih naštevali njihove
elemente,</p>
<pre>k = [9, 16, 81, 25, 196]</pre>
<p>Oglate oklepaje bomo uporabljali tudi poslej, le da znotraj njih ne bomo
našteli elementov, temveč napisali izraz, ki jih sestavi. Recimo, da bi
hotel seznam korenov števil iz gornjega seznama (po nekem čednem naključju
gornji seznam vsebuje ravno same kvadrate). Naredil bi tako:</p>
<pre>>>> [sqrt(x) for x in k]
[3.0, 4.0, 9.0, 5.0, 14.0]</pre>
<p>Torej: napisal sem oglate oklepaje, kot vedno, kadar definiram seznam, a
namesto, da bi naštel elemente, sem povedal, kakšni naj bodo. Rekel sem,
naj bodo elementi mojega novega seznama <em>koren iz x</em>, pri čemer so
<code>x</code> elementi seznama <code>k</code>. Kaj pa, če bi hotel
namesto tega imeti kvadrate števil? Isti šmorn:</p>
<pre>>>> [x**2 for x in k]
[81, 256, 6561, 625, 38416]</pre>
<p>Oblika tega, kar pišemo, je vedno
<code>[<em>izraz</em> for <em>spremenljivka</em> in <em>nekaj</em>]</code>,
kjer je <em>spremenljivka</em> ime neke spremenljivke (npr. <code>x</code>,
<em>izraz</em> nek izraz, ki (običajno, ne pa čisto nujno) vsebuje to
spremenljivko (npr. <code>sqrt(x)</code> ali <code>2*x</code>, <em>nekaj</em>
pa je nekaj, čez kar je možno spustiti zanko for, torej seznam, slovar,
množica, datoteka ali kaj, česar še ne poznamo, vendar bomo spoznali še danes.
</p>
<p>Imam seznam imen, recimo,</p>
<pre>l = ["Ana", "Berta", "Cilka", "Dani", "Ema"]</pre>
<p>Kako bi izračunal povprečno dolžino imena? Imam funkcijo <code>sum</code>,
ki zna sešteti števila v seznamu. Potrebujem torej le še seznam dolžin
(namesto seznama imen). Tega pač preprosto dobim: izračunati želim dolžino
niza <code>ime</code> za vsako <code>ime</code> v seznamu
<code>imena</code>.</p>
<pre>>>> [len(ime) for ime in imena]
[3, 5, 5, 4, 3]</pre>
<p>Zdaj pa tole le še seštejem in delim z dolžino seznama.</p>
<pre>>>> sum([len(ime) for ime in imena]) / len(imena)
4.0</pre>
<p>Poprečna dolžina imena ni nič posebej zanimivega. Računajmo raje povprečno
težo in, da nam ne bo dolgčas, jo bomo računali iz teh podatkov:</p>
<pre>podatki = [
(74, "Anže", False),
(82, "Benjamin", False),
(58, "Cilka", True),
(66, "Dani", False),
(61, "Eva", True),
(84, "Franc", False),
]</pre>
<p>Takole nam je storiti: z zanko se zapeljemo čez podatke, izračunamo vsoto
prvih elementov in jo delimo z dolžino seznama.</p>
<p>Lepo prosim, ne tako:</p>
<pre>vsota = 0
for i in range(len(podatki)):
vsota += podatki[i][0]
print(vsota / len(podatki))</pre>
<p>Tole je že boljše:</p>
<pre>vsota = 0
for podatek in podatki:
vsota += podatek[0]
print(vsota / len(podatki))</pre>
<p>In še malo bolje:</p>
<pre>vsota = 0
for teza, ime, zenska in podatki:
vsota += teza
print(vsota / len(podatki))</pre>
<p>Zdaj pa naredimo tako, kot smo se naučili danes. Naredimo lahko
<pre>vsota = sum([podatek[0] for podatek in podatki])</pre>
<p>ali, po zadnji različici</p>
<pre>vsota = sum([teza for teza, ime, zenska in podatki])</pre>
<p>Pri izpeljevanju seznamov lahko dodamo še pogoj, s katerim izbiramo
elemente, ki naj se dodajo.</p>
<p>Kako bi sestavili seznam kvadratov vseh lihih
števil do 100? Seznam kvadratov vseh števil do 100 je trivialen, napisati
nam je treba le:</p>
<pre>s = [x**2 for x in range(100)]</pre>
<p>Če želimo pobrati samo liha števila, lahko v izpeljavo seznama dodamo še
pogoj.</p>
<pre>s = [x**2 for x in range(100) if x % 2 == 1]</pre>
<p>Tole pravzaprav ni čisto potrebno, lahko bi rekli preprosto</p>
<pre>s = [x**2 for x in range(1, 100, 2)]</pre>
<p>Kaj pa, če bi hoteli seznam kvadratov vseh števil do 100, ki niso deljiva s
7 in ne vsebujejo števke 7?</p>
<pre>[x**2 for x in range(100) if (x % 7 != 0) and ("7" not in str(x))]</pre>
<p>V pogoju smo zaradi preglednosti uporabili oklepaje, čeprav sicer niso
potrebni). Prvi del poskrbi, da število ni deljivo s 7 (ostanek po deljenju s
7 mora biti različni od 0). Drugi del poskrbi, da število ne vsebuje števke 7:
število preprosto pretvorimo v niz in preverimo, da ne vsebuje sedemke.</p>
<p>Kako bi izračunali vsoto tež moških v gornjem seznamu? Za zanko dodamo
pogoj. Za začetek sestavimo le seznam imen vseh moških.</p>
<pre>[ime for teza, ime, zenska in podatki if not zenska]</pre>
<p>V definicijo našega seznama lepo na konec, za <code>for</code>, dodamo še
<code>if</code> in pogoj, ki mu mora zadoščati element, da nas zanima.</p>
<p>Z vsoto je podobno.</p>
<pre>vsota = sum([teza for teza, ime, zenska in podatki if not zenska])</pre>
<p>Zdaj veste, zakaj sem tako utrujal, da ne uporabljajte
<code>for i in range(len(s))</code>: zato, ker z njim namesto lepega, kratkega
preglednega <code>[ime for teza, ime, zenska in podatki if not zenska]</code>
dobimo
<code>[podatki[i][1] for i in range(len(podatki)) if not podatki[i][2]]</code>.
Seveda lahko delate tudi na ta, drugi način. Svobodni ljudje ste in noben zakon
ne prepoveduje mazohizma.</p>
<p>Sestavimo seznam vseh deliteljev danega števila <code>n</code>. Vzemimo,
recimo <code>n = 60</code>. Seznam deliteljev je tedaj seznam vseh
<code>x</code>, pri čemer <code>x</code> prihaja z intervala
1 ≤ x ≤ n, za katere velja, da je ostanek po deljenju
<code>n</code> z <code>x</code> enak 0 (torej <code>x</code> deli
<code>n</code>).</p>
<pre>def delitelji(n):
return [x for x in range(1, n+1) if n % x == 0]</pre>
<p>Zdaj lahko hitro ugotovimo, ali je dano število popolno: popolna
števila so (se še spomnimo?) števila, ki so enaka vsoti svojih
deliteljev (brez sebe samega).
<pre>def popolno(n):
return n == sum(delitelji(n))</pre>
</p>
<p>Še bolj imenitna števila so praštevila, števila brez deliteljev. Se pravi
tista, pri katerih je seznam deliteljev med 2 in tem številom prazen.</p>
<pre>def prastevilo(n):
return not delitelji(n)</pre>
<p>Če funkcije <code>delitelji</code> še ne bi imeli - nič hudega. Ali je
število praštevilo, bi še vedno dognali v eni sami vrstici.</p>
<pre>def prastevilo(n):
return not [x for x in range(2, n) if n % x == 0])</pre>
<p>S to funkcijo hitro sestavimo seznam vseh praštevil med 2 in 100:</p>
<pre>>>> [n for n in range(2, 101) if prastevilo(n)]
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]</pre>
<p>Znamo pa, jasno, tudi brez funkcije; tisto, kar dela funkcija, pač kar
prepišemo v pogoj.</p>
<pre>>>> [n for n in range(2, 101) if not [x for x in range(2, n) if n % x == 0])]
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]</pre>
<p>Takšnih reči sicer raje ne pišemo, saj hitro postanejo nepregledne.</p>
<p>Kdor je gledal stare naloge, je opazil nalogo z vislicami. V eni od nalog
je bilo potrebno napisati funkcijo <code>pokazi_crke(beseda, crka)</code>,
ki kot argument dobi besedo in množico črk, vrniti pa mora besedo, v kateri
so "vidne" vse črke, ki so v množici, tiste, ki jih ni, pa je potrebno
zamenjati s piko. Tako mora, recimo,
<code>pokazi_crke("BESEDA", {"E", "D"})</code> vrniti <code>.E.ED.</code>.
</p>
<p>Nalogo rešimo lepo po korakih. Vzemimo neko množico črk in neko besedo.</p>
<pre>>>> crke = {"E", "D"}
>>> beseda = "BESEDA"</pre>
<p>Zdaj razsekajmo besedo na črke.</p>
<pre>>>> [b for b in beseda]
['B', 'E', 'S', 'E', 'D', 'A']</pre>
<p>Zdaj pa naj seznam vsebuje <code>b</code> le, če je <code>b</code> v množici
<code>crke</code>, sicer pa piko.</p>
<pre>>>> [b if b in crke else "." for b in beseda]
['.', 'E', '.', 'E', 'D', '.']</pre>
<p>Da združimo črke v niz, potrebujemo le še večno zeleni <code>join</code>.</p>
<pre>>>> "".join([b if b in crke else "." for b in beseda])
'.E.ED.'</pre>
<p>Celotna rešitev naloge je torej</p>
<pre>def pokazi_crke(beseda, crke):
print "".join((c if c in crke else ".") for c in beseda)
</pre>
<p>V splošnem: vsak kos kode, ki izgleda takole</p>
<pre>r = []
for e in s:
if pogoj(e):
r.append(funkcija(e))</pre>
<p>lahko prepišemo v</p>
<pre>r = [funkcija(e) for e in s if pogoj(e)]</pre>
<p>Kdor želi še kakšen primer, si bo ogledal
<a href="/mod/page/view.php?id=11856">rešitev
kronogramov</a> in
<a href="/mod/page/view.php?id=11814">napadalnih kraljic</a>.
</p>
<h2>Množice</h2>
<p>Množice sestavljamo natančno tako kot sezname, le da namesto oglatih
oklepajev uporabimo zavite. Takole dobimo vse delitelje 60</p>
<pre>>>> {i for i in range(1, 61) if 60 % i == 0}
{1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 60, 30}</pre>
<h2>Slovarji</h2>
<p>Ista reč. Če hočemo narediti slovar, ki bo kot ključe vseboval števila do
10, kot vrednosti pa njihove kvadrate, napišemo</p>
<pre>{i: i**2 for i in range(11)}</pre>
<h2>Generatorji</h2>
<p>Tule bi pričakovali nekaj drugega: terke. Lahko tako kot sezname, množice in
slovarje naredimo tudi terke in nize? Ne. Na takšen način določeni nizi
očitno ne bi imeli nobenega smisla, pa tudi terke ne bi bile preveč
uporabne. Pač pa nas čaka - in bo pogosto v okroglih oklepajih - še nekaj
bolj nenavadnega in imenitnejšega: generatorji.</p>
<pre>>>> g = (x**2 for x in range(10))</pre>
<p>Tale <code>g</code>, kot se hitro prepričamo, ni terka, temveč nekaj
drugega.</p>
<pre>>>> g
<generator object <genexpr> at 0x667bc0></pre>
<p>Kaj je generator, čemu služi in kako ga uporabljamo? Na prvi dve vprašanji
lahko odgovorimo naenkrat: generator je nekaj, kar generira objekte.
Vsakič, ko bomo od njega zahtevali nov objekt, bo vrnil novo število -
najprej 0, potem 1, potem 4, potem 9 ... pač kvadrate naravnih števil do
10. Na tretje vprašanje, kako ga uporabljamo, nam skoraj ni potrebno
odgovarjati, saj generatorje (in njim podobne reči) že dolgo uporabljamo.
Generatorje najpreprosteje uporabimo z zanko for. Še več, zanka for deluje
na tistih rečeh - in samo tistih rečeh - ki se znajo obnašati kot
generatorji (torej: v resnici so generatorji ali pa podpirajo osnovne
funkcije generatorjev).</p>
<pre>>>> for i in g:
... print(i, end=" ")
...
0 1 4 9 16 25 36 49 64 81</pre>
<p>Če poskusimo ponoviti, ne gre: generator je že "iztrošen". Kar je imel
zgenerirati, je zgeneriral.</p>
<pre>>>> for i in g:
... print(i, end=" ")
...
>>></pre>
<p>Generator je torej videti kot izpeljani seznam, le da namesto oglatih
oklepajev uporabimo okrogle. Kadar ga pošljemo kot edini argument funkciji,
smemo oklepaje celo izpustiti. Napišimo funkcijo, ki kot argument dobi
seznam števil in vrne prvo število, ki je večje od 50.</p>
<pre>def nad50(s):
for e in s:
if e > 50:
return e</pre>
<p>Preskusimo jo, trikrat:</p>
<pre>>>> nad50([5, 1, 40, 1, 82, 12, 6])
82
>>> nad50([x**2 for x in range(10)])
64
>>> nad50(x**2 for x in range(10))
64</pre>
<p>V prvem primeru je dobila najobičajnejši seznam. Tako smo si predstavljali,
ko smo jo pisali. V drugem primeru smo ji dali seznam kvadratov števil do
10 in vrnila je prvi kvadrat, ki je večji od 50. V tretjem klicu pa ji
sploh nismo dali seznama, temveč generator, ki je dajal kvadrate -
natančno isto reč kot gornji <code>g</code>. Funkcija je čez generator
pognala zanko <code>for</code> natančno tako, kot jo sicer poganja čez
sezname.</p>
<p>V čem je prednost generatorjev pred seznami? V tem, da ne sestavijo seznama.
Če želimo izračunati vsoto kvadratov prvih stotih števil in za to uporabimo
generator, na ta način ne sestavimo seznama teh števil (kot bi ga, če bi
rekli <code>sum([x**2 for x in range(100)])</code>, temveč števila, namreč
kvadrate, generiramo sproti (tako, da pokličemo
<code>sum([x**2 for x in range(100)])</code>. Hm, pa to v resnici deluje?
No, seveda. Funkcija <code>sum</code> bi lahko bila napisana takole</p>
<pre>def sum(s):
vsota = 0
for e in s:
vsota += e
return vsota</pre>
<p>Zanka for lahko gre prek generatorja (in v resnici vedno gre prek
generatorja), torej ona reč deluje.</p>
<p>Že, že, poreče pozornejši študent: kaj pa <code>range(100)</code>? Mar ta
ne sestavi seznama stotih števil? Smo res kaj dosti pridobili - namesto
seznama kvadratov števil do 100 imamo pač števila do 100 - je to res tak
napredek? Tu lahko študenta pohvalimo za budnost, vendar se moti.</p>
<pre>>>> range(100)
range(0, 100)</pre>
<p>V resnici <code>range</code> ne sestavi seznama, temveč generator. Res se
nam ni predstavil kot kak "generator object" temveč kot "range(0, 100)",
vendar v resnici ni ničesar sestavil. Nobenega seznama s stotimi števili
ni. Kako vem? Preprosto: </p>
<pre>>>> range(1000000000000)
range(0, 1000000000000)</pre>
<p>Če bi <code>range</code> sestavljal sezname, bi bil to seznam z bilijon
elementi. Če bi vsak od njih zavzel samo en bajt (pa jih v resnici najbrž
vsaj 20, verjetneje pa 32), bi shranjevanje takšnega seznama zahtevalo
pomnilnik velik en terabajt.</p>
<p>Tako smo torej generatorje uporabljali že, odkar vemo za <code>range</code>.
(Morda se kdo spomni, da sem vam takrat, na onem davnem predavanju, ko sem
povedal za funkcijo <code>range</code>, le-to pokazal na Pythonu 2.7? Tako
je bilo lažje, saj je takrat še vračal sezname. To je ena od sprememb od
različice 3.0 naprej: po novem vrača generatorji.)</p>
<p>Podobno je s slovarji: metode <code>__keys__</code>, <code>__values__</code>
in <code>__items__</code> vračajo generatorje, ne seznamov.</p>
<h2>Funkcije, ki generirajo</h2>
<p>Še nekoliko naprednejša snov: Bi znali napisati generator Fibonaccijevih
števil, tako kot smo napisali generator kvadratov? Da, vendar bo
preprostejša nekoliko drugačna pot. Napisali bomo funkcijo, ki ne vrača le
enega rezultata temveč "generira" rezultate. Torej, nekaj takšnega:</p>
<pre>def fibonacci(n):
a = b = 1
for i in range(n):
return a # Tole ne deluje!
a, b = b, a+b</pre>
<p>Tale funkcija ne deluje, napisali smo jo le, da ilustriramo idejo: radi bi
naredili zanko. Ko funkcijo prvič pokličemo, bi <code>return</code> vrnil
prvo Fibonaccijevo število. Ko jo pokličemo naslednjič, se funkcija ne bi
izvajala od začetka, temveč od tam, kjer smo nazadnje vrnili rezultat, se
pravi z vrstico, ki sledi <code>return</code>u. No, v resnici naredimo
natanko tako, le namesto <code>return</code>a moramo uporabiti
<code>yield</code>:</p>
<pre>def fibonacci(n):
a = b = 1
for i in range(n):
yield a
a, b = b, a+b</pre>
<p>Preskusimo.</p>
<pre>>>> for i in fibonacci(5):
... print(i)
1
1
2
3
5</pre>
<p>Napišemo lahko celo funkcijo, ki vrne (no, generira) <b>vsa</b>
Fibonaccijeva števila.</p>
<pre>def fibonacci():
a = b = 1
while True:
yield a
a, b = b, a+b</pre>
<p>Neskončno zanko, <code>while True</code>, smo že videli, vendar je bil v
njej vedno <code>break</code>, ki jo je nekoč prekinil. Kdo pa prekine to
zanko? Če nismo previdni, nihče. Če rečemo</p>
<pre>>>> for i in fibonacci():
... print(i)</pre>
<p>bo program izpisoval v nedogled. Pač pa lahko poiščemo, recimo, prvo
Fibonaccijevo število, ki je večje od 50.</p>
<pre>>>> for i in fibonacci():
... if i > 50:
... print(i)
... break
55</pre>
<p>Ali pa, ah, saj imamo za to že funkcijo, <code>nad50</code>. Naj kar ta
pove, katero je prvo Fibonaccijevo število večje od 50!</p>
<pre>>>> nad50(fibonacci())
55</pre>
<p>V zvezi z vsemi temi rečmi bi bilo mogoče povedati še zelo veliko. Tole je
ena najbolj kul tem v Pythonu. Pravzaprav treba priznati, da to niti ni
tema iz Pythona. V ozadju tega, kar počnemo tule, je poseben slog
programiranja,
<a href="https://en.wikipedia.org/wiki/Functional_programming">funkcijsko
programiranje</a>. Python ga omogoča in med "normalnimi" jeziki je za
takšen slog pravzaprav eden boljših. Obstajajo pa jeziki, ki so posebej
narejeni za takšno programiranje. Če je bilo komu tole, kar smo počeli
doslej, všeč naj si nujno ogleda kak
<a href="https://en.wikipedia.org/wiki/Standard_ML">SML</a> ali
<a href="https://en.wikipedia.org/wiki/Haskell_(programming_language)">
Haskell</a>, morda pa ga bo zabaval tudi
<a href="https://en.wikipedia.org/wiki/Racket_(programming_language)">
Racket</a> (dialekt Lispa).</p>
<p>V Pythonu pa si bo ta, ki so mu bile te reči všeč, dobro ogledal module
<a href="https://docs.python.org/3/library/functools.html">functools</a>,
<a href="https://docs.python.org/3/library/itertools.html">iterools</a> in
<a hreF="https://docs.python.org/3/library/operator.html">operator</a>.</p>
<h3>Generator deliteljev</h3>
<p>Še en zanimiv primer je generator, ki vrne vse delitelje podanega števila.
</p>
<pre>def delitelji(n):
for i in range(1, n + 1):
if n % i == 0:
yield i</pre>
<p>Opazimo lahko, da z enim deliteljem dobimo dva: če je <code>i</code> delitelj
<code>n</code>-ja, je tudi <code>n // i</code> delitelj <code>n</code>-ja.
Če je tako, zadošča, da gremo do korena iz <code>n</code> in vrnemo po dva
delitelja.</p>
<pre>from math import sqrt
def delitelji(n):
for i in range(1, int(sqrt(n) + 1)):
if n % i == 0:
yield i
yield n // i</pre>
<p>Koren iz <code>n</code> moramo spremeniti v celo število, ker <code>range</code>
ne mara necelih.</p>
<p>Pazite, tole sta dva <code>yield</code>a. Funkcija se izvaja tako, ad vrne
najprej eno število, in ko zahtevamo naslednje, se izvede naslednji
<code>yield</code>.</p>
<p>Funkcija je zdaj bistveno hitrejša (pri velikih številih bi se to utegnilo
kar poznati - namesto, da gre do milijona, bo šla le do 1000. Vendar žal ne
dela pravilno. Če je <code>n</code>, recimo, <code>25</code>, bo funkcija
dvakrat vrnila 5. A tega se znamo hitro znebiti.</p>
<pre>from math import sqrt
def delitelji(n):
for i in range(1, int(sqrt(n) + 1)):
if n % i == 0:
yield i
if i ** 2 != n:
yield n // i</pre>
<p>Zdaj nas morda moti le še to, da števila ne prihajajo v pravem vrstnem redu.
Kot delitelje 42 bi namesto 1, 2, 3, 6, 7, 14, 21, 42 dobili 1, 42, 2, 21, 3,
14, 6, 7. To lahko popravimo tako, da <code>n // i</code> ne vračamo sproti,
temveč jih le shranjujemo in jih vračamo kasneje.</p>
<pre>from math import sqrt
def delitelji(n):
for i in range(1, int(sqrt(n) + 1)):
if n % i == 0:
yield i
if i ** 2 != n:
ostali.append(n // i)
for e in ostali:
yield e</pre>
<p>Nismo še čisto zmagali. Zdaj imamo 1, 2, 3, 6, 41, 21, 14, 7 - prva polovica
je iz prvega <code>yield</code>a, druga (od 41 naprej) iz drugega. Te, druge,
vrača v enakem vrstnem redu, v katerem jih je vstavljal v seznam, saj
<code>append</code> pač vstavlja na konec.</p>
<p>Pa vstavljajmo raje na začetek! Uporabimo <code>insert</code>.</p>
<pre>from math import sqrt
def delitelji(n):
for i in range(1, int(sqrt(n) + 1)):
if n % i == 0:
yield i
if i ** 2 != n:
ostali.insert(0, n // i)
for e in ostali:
yield e</pre>
<p>Žal se je <code>insert</code>u modro izogibati. Za to, da vstavi element
na prvo mesto, mora enega za drugim premakniti vse ostale. V teoriji (ki se jo
boste učili drugo leto) je ta program enako počasen kot bi bil, če bi prvo
zanko spustili prek <code>range(1, n + 1)</code>. S tem, ko smo zamenjali
<code>append</code> z <code>insert</code>, smo, vsaj v teoriji, zapravili ves
prihranek.</p>
<p>To je preprosto urediti. Vstavljali bomo na konec, z <code>append</code>.
Pač pa bomo seznam nato prehodili v obratnem vrstnem redu. To se da narediti
z indeksiranjem (<code>for i in range(-1, -n - n, -1): yield ostali[i]</code>,
vendar si bomo raje pomagali s priročno funkcijo <code>reversed</code>, ki
obrne seznam.</p>
<pre>def delitelji(n):
ostali = []
for i in range(1, int(sqrt(n)) + 1):
if n % i == 0:
yield i
if i ** 2 != n:
ostali.append(n // i)
for e in reversed(ostali):
yield e</pre>
<script>
renderMathInElement(document.body);
</script>
</body>
</html>
|
