-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathAlgorithms.html
More file actions
959 lines (958 loc) · 46.7 KB
/
Algorithms.html
File metadata and controls
959 lines (958 loc) · 46.7 KB
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
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
<!DOCTYPE html><html lang="de"><head>
<title>Variationen zum Thema: Algorithmen</title>
<meta name="title" content="Variationen zum Thema: Algorithmen">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta charset="UTF-8">
<meta name="description" content="Eine Einführung anhand von Beispielen">
<meta name="keywords" content="Java,Algorithmen,Datenstrukturen">
<meta name="author" content="Ralph P. Lano">
<meta name="robots" content="index,follow">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="stylesheet" type="text/css" href="book.css">
</head>
<body><center>
<div id="wrap">
<ul class="sidenav">
<p><a href="index.html">Variationen zum Thema</a><a href="index.html">Algorithmen</a></p>
<li><a href="Introduction.html">Introduction</a></li>
<li><a href="Lists.html">Lists</a></li>
<li><a href="Maps.html">Maps</a></li>
<li><a href="Recursion.html">Recursion</a></li>
<li><a href="Algorithms.html" class="active">Algorithms</a></li>
<li><a href="Sorting.html">Sorting</a></li>
<li><a href="Trees.html">Trees</a></li>
<li><a href="Graphs.html">Graphs</a></li>
<li><a href="Text.html">Text</a></li>
<li><a href="Techniques.html">Techniques</a></li>
</ul>
<div class="content"><p>
<img src="images/AsymptoticGrowth.png" style="display: block; margin-left: auto; margin-right: auto; width: 227px; height: 228px;" /></p>
<h1>
Algorithmic Analysis</h1>
<p>
Wir haben jetzt schon einige Algorithmen gesehen, und u.a. festgestellt, dass es sehr häufig mehr als einen Algorithmus gibt um ein gegebenes Problem zu lösen. Die Frage stellt sich, welchen soll ich denn verwenden? In diesem Kapitel beschäftigen wir uns damit welcher denn der schnellste ist, und wie man das vorhersagt oder misst. Geschwindigkeit ist aber nicht das einzige Kriterium das für die Wahl entscheidend sein kann: manchmal ist es Speicherplatz, manchmal ist es Zuverlässigkeit, und manchmal Einfachheit. Aber in aller Regel hilft es einem wenig, wenn eine Algorithmus Jahre braucht bis er fertig ist, deswegen ist das häufigste Optimierungskriterium die Zeit. Außerdem stellen wir auf den folgenden Seiten auch ein paar neue Techniken vor: Approximation, Dynamische Programmierung und Divide and Conquer.</p>
<p>
.</p>
<h2>
Approximation</h2>
<p>
Als wir Leute in einem Stadium zählen wollten, haben wir das erste Mal gesehen, dass es u.U. genügt nur ungefähr zu wissen wieviel Leute es sind. Also eine grobe <em>Abschätzung</em> oder eine Annäherung an den genauen Wert. Das ist eine Technik die nicht selten verwendet wird, vor allem wenn es schnell gehen muss. </p>
<p>
Wenn wir die Fakultät einer Zahl berechnen wollen, also <em>n!</em>, dann haben wir im letzte Kapitel schon zwei Methoden gesehen, und zwar Iteration und Rekursion. Eine dritte ist Approximation. In der Regel muss man da einen Mathematiker als Kumpel haben, die kennen sich mit so Sachen nämlich gut aus. Für die Fakultät gibt es nämlich eine Formel die sehr gute Näherungswerte für große Fakultäten liefert die sogenannte Stirling-Formel [1]:</p>
<p style="margin-left: 40px; text-align: center;">
<img alt="" src="images/Stirling.png" style="margin-left: 10px; margin-right: 10px; width: 125px; height: 35px;" /></p>
<p>
Wobei man bei den Mathematikern immer aufpassen muss: was heisst denn groß? Manchmal bedeutet das riesengroß, also total nutzlos eigentlich. Aber hier heisst groß so ab drei, und das ist eigentlich gar nicht so groß. Deswegen ist das eine Superformel um Fakultäten auszurechnen (genauer anzunähern) sobald n größer als drei ist.</p>
<p>
.</p>
<h2>
Dynamic Programming</h2>
<p>
Kommen wir zur Technik der <em>Dynamischen Programmierung</em> [2,3]. Der Name ist wohl der dümmste der einem einfallen kann, denn die Technik ist eigentlich nicht besonders dynamisch, noch hat sie irgendetwas mit Programmierung zu tun. Wenn man unbedingt will, dann wäre dynamische Nachschlagetabelle, also <em>dynamic lookup table</em>, schon beschreibender.</p>
<p>
Worum geht es? Wenn wir die Fakultät von 11 berechnen wollen, dann brauchen wir ja die Fakultät von 10 erstmal, weil ja</p>
<pre style="margin-left: 40px;">
11! = 11 * 10!</pre>
<p>
So was wäre wenn wir irgendwann schon mal 10! ausgerechnet hätten und uns das gemerkt hätten? Das ist Dynamischen Programmierung: einfach merken was man schon mal ausgerechnet hat. Oder genauer, das wiederverwenden was man schon mal ausgerechnet hat.</p>
<p>
Schauen wir uns mal an wie man das in Java macht. Das "Merken" machen wir in einem Array:</p>
<pre style="margin-left: 40px;">
public long[] factorialLookupTable;</pre>
<p>
Dann berechnen wir einfach mal die ersten zwanzig Fakultäten im Voraus:</p>
<pre style="margin-left: 40px;">
public void initFactorialLookupTable() {
factorialLookupTable = new long[20+1];
for (int i = 1; i < factorialLookupTable.length; i++) {
factorialLookupTable[i] = factorialIterative(i);
}
}
</pre>
<p>
Wenn uns jetzt irgendjemand nach einer Fakultät fragt, schauen wir einfach in unserem Array nach:</p>
<pre style="margin-left: 40px;">
public long factorialLookupTable(int n) {
return factorialLookupTable[n];
}
</pre>
<p>
und das geht super-schnell. Technisch gesehen schummeln wir hier ein bischen, weil wir die ganzen Werte im Voraus berechnen. Aber das Kernprinzip der Dynamischen Programmierung ist es das wieder zu verwenden was wir schon ausgerechnet haben.</p>
<p>
.</p>
<h2>
Fastest</h2>
<p>
Wir haben ja schon angedeutet, dass es in diesem Kapitel um Geschwindigkeit geht und wie man sie misst. Wir haben inzwischen schon vier verschiedene Algorithmen um die Fakultät einer Zahl zu berechnen:</p>
<ul>
<li>
Iteration</li>
<li>
Rekursion</li>
<li>
Dynamischen Programmierung</li>
<li>
Abschätzung</li>
</ul>
<p>
Welcher ist nun der schnellste? Zeitmessungen in Java machen wir mit der <em>System.currentTimeMillis()</em> Methode, die gibt uns die Zeit die seit dem 01.01.1970 vergangen ist in Millisekunden. Wir nehmen also die Zeit bevor wir mit unserer Berechnung beginnen und ziehen dann die Zeit danach davon ab:</p>
<pre style="margin-left: 40px;">
long start = <span style="color:#0000ff;">System.currentTimeMillis()</span>;
for (int i = 0; i < NR_OF_ITERATIONS; i++) {
x = Factorial.factorialIterative(20);
}
long duration = <span style="color:#0000ff;">System.currentTimeMillis()</span> - start;
System.out.println("time iterative: " + duration);</pre>
<p>
Wenn eine Berechnung sehr kurz ist, also im Milli- oder Nanosekunden Bereich, dann sollten wir diese Berechnung mehrmals (so hundertmillionenmal) ausführen, sonst sind die gewonnen Resultate nicht besonders aussagekräftig. Überhaupt kann bei Zeitmessungen recht viel schief gehen.</p>
<p>
Und, wer ist der Gewinner?</p>
<pre style="margin-left: 40px;">
iteration: 1262ms
recursion: 2524ms
dynamic programming: 4ms
approximation: 6ms</pre>
<p>
Der Unterschied ist schon ziemlich massiv: Dynamischen Programmierung und Abschätzung schlagen die Iteration und Rekusion um Längen! Analysieren wir die Ergebnisse aber etwas genauer:</p>
<ul>
<li>
Abschätzung ist zwar schnell aber nicht genau. Man muss schon wissen ob man mit einer Abschätzung leben kann, aber sie ist schnell und braucht wenig Speicher.</li>
<li>
Dynamischen Programmierung ist genau und schnell. Aber auch hier gibt es zu bedenken: einmal muss ich die Nachschlagtabelle ja ausrechnen, und das dauert Zeit. Und die Nachschlagtabelle benötigt Speicher, teilweise sehr viel Speicher. </li>
<li>
Iteration ist zwar nicht so schnell, ist aber sehr effektiv was den Speicher angeht. Und sie ist immer noch doppelt so schnell wie die Rekursion (aber nicht immer).</li>
<li>
Rekursion ist eigentlich so das schlimmste was man machen kann: sie ist langsam und braucht viel Speicher. Sehr häufig sind rekursive Lösungen aber sehr elegant, und bekanntlich ist Eleganz ja teuer. Man fragt sich natürlich warum wir uns dann das ganze letzte Kapitel damit rumgeschlagen haben... die Antwort kommt gleich.</li>
</ul>
<p>
Zusammenfassend kann man allerdings sagen, wenn ein Algorithmus schnell ist, dann geht er meist nicht sehr effektiv mit Speicher um, und umgekehrt.</p>
<p>
.</p>
<h2>
Divide and Conquer</h2>
<p>
Ist Rekursion immer am langsamsten? Meistens ja, aber es gibt Ausnahmen. Schauen wir uns mal das Berechnen von Potenzen an. Nehmen wir an wir wollen zwei hoch acht berechnen:</p>
<pre style="margin-left: 40px;">
2^8 = 2*2*2*2*2*2*2*2 = 256</pre>
<p>
Eine Möglichkeit ist mittels Iteration:</p>
<pre style="margin-left: 40px;">
int powerIt(int x, int n) {
int power = 1;
for (int i = 0; i < n; i++) {
power *= x;
}
return power;
}
</pre>
<p>
Eine zweite ist mittels Rekursion. Erinnern wir uns, dass</p>
<pre style="margin-left: 40px;">
2^8 = 2 * 2^7</pre>
<p>
dann sehen wir hier sofort eine rekursive Beziehung. Mit dem <em>base case</em> dass 2<sup>0</sup> = 1, können wir das folgendermaßen in Java umsetzen:</p>
<pre style="margin-left: 40px;">
int powerRe(int x, int n) {
if (n == 0)
return 1;
else
return x * powerRe(x, n-1);
}</pre>
<p>
Interessanterweise ist das aber nicht die einzige rekursive Lösung. Es gibt nämlich noch eine andere:</p>
<pre style="margin-left: 40px;">
2^8 = 2^4 * 2^4</pre>
<p>
Das sieht jetzt ganz unscheinbar aus, ist es aber nicht. Es ist das erste Mal dass wir einem Algorithmus aus der Kategorie <em>divide and conquer</em> begegnen. Die haben's in sich. Zunächst setzen wir das in Java um:</p>
<pre style="margin-left: 40px;">
int powerDC(int x, int n) {
if (n == 0)
return 1;
else {
int temp = powerDC(x, n/2);
if (n % 2 == 0)
return temp * temp;
else
return x * temp * temp;
}
}
</pre>
<p>
Jetzt stellt sich natürlich wieder die Frage, welcher ist denn der schnellste? Wir lassen unsere Stoppuhren laufen und stellen fest:</p>
<pre style="margin-left: 40px;">
iteration: 6ms
recursion: 778ms
divide & conquer: 89ms
approximation: 3ms</pre>
<p>
Wie erwartet, ist die Approximation die schnellste. Iteration ist auch verflucht schnell, aber die Überraschung kommt wenn wir Rekusion mit Divide and Conquer vergleichen: Divide and Conquer ist fast zehnmal schneller! Es kommt sogar noch besser: je größer die Zahlen werden, desto besser wird Divide and Conquer, am Ende schlägt er sogar die Iteration. Wie wir in späteren Kapiteln noch sehen werden, Divide and Conquer ist unser Freund.</p>
<p>
.</p>
<h2>
Algorithm Analysis</h2>
<p>
Wie bewertet man denn einen Algorithmus? Bisher haben wir einfach die Stoppuhr ausgepackt und gemessen. Das funktioniert, aber es ist nicht sehr wissenschaftlich, und wir wissen eigentlich auch nicht warum ein Algorithmus besser ist als ein anderer. Darum geht es in der algorithmischen Analyse, man versucht Algorithmen mathematisch zu untersuchen, zu bewerten und einzuordnen. Da wir keine ausgebildeten Mathematiker sind, werden wir das ganze etwas vereinfachen: im Prinzip was wir im Folgenden machen ist nichts anderes als zählen.</p>
<h3>
Constant Performance: O(1)</h3>
<p>
Wir beginnen ganz einfach, wir nutzen die Tatsache, dass die meisten modernen CPUs die Potenz einer Zahl direkt berechnen können:</p>
<pre style="margin-left: 40px;">
int powerApprox(int x, int n) {
return (int) Math.pow(x, n);
}
</pre>
<p>
Dies dauert eine feste Anzahl von CPU-Zyklen (etwa 28 CPU-Zyklen) und egal, was die Werte von x oder n sind, wird es immer die gleiche Zeit in Anspruch nehmen. Wir nennen dies konstante Performanz, weil sich die Zeit nicht ändert, auch wenn wir x oder n ändern. In Kurzform: O(1).</p>
<h3>
Linear Performance, Iteration: O(n)</h3>
<p>
Als nächstes betrachten wir unsere iterative Lösung:</p>
<pre style="margin-left: 40px;">
1. int powerIt(int x, int n) {
2. int power = 1;
3. <span style="color:#0000ff;">for (int i = 0; i < n; i++)</span> {
4. power *= x;
5. }
6. return power;
7. }
</pre>
<p>
Wir wollen ermitteln, wieviele CPU-Zyklen für diese Berechnung notwendig sind. Bei modernen CPUs dauern die meisten Anweisungen etwa 2 bis 3 Zyklen. Damit kann man dann ausrechnen wie lange es dauert. Deshalb genügt es für uns eigentlich zu wissen wieviele Anweisung für eine gewisse Berechnung nötig sind. Also analysieren wir den Code oben Zeile für Zeile:</p>
<ol>
<li>
die Werte von x und n müssen wir in den CPU-Registern speichern, das benötigt 2 Anweisungen;</li>
<li>
eine einfache Zuweisung, braucht 1 Anweisung;</li>
<li>
Schleifen sind etwas knifflig:
<ol>
<li>
einmal haben wir eine Zuordnung, int i = 0, das ist 1 Anweisung, wird nur einmal ausgeführt;</li>
<li>
dann haben wir einen Vergleich, i < n, auch 1 Anweisung, wird u.U. mehrmal ausgeführt;</li>
<li>
schließlich haben wir noch ein Inkrement, i++, auch 1 Anweisung, wird u.U. mehrmal ausgeführt;</li>
</ol>
</li>
<li>
eine einfache Multiplikation, dauert 1 Anweisung;</li>
<li>
eine geschloßene geschweifte Klammer benötigt natürlich keine Zeit, aber wenn die Schleife mehrmals durchlaufen wird, bedeutet sie, dass wir wieder zurück zur Zeile 3 gehen;</li>
<li>
return heißt soviel wie "schreibe es irgendwo in den Speicher", d.h. 1 Anweisung.</li>
</ol>
<p>
Also, wielange dauert es? Dass hängt von <em>n</em> ab. Je größer <em>n</em> ist, desto länger dauert es. Um genau zu sein</p>
<pre style="margin-left: 40px;">
# of instructions = 2+1+1 + n*( 1+1+1) + 1 = 5 + 3*n ~ n</pre>
<p>
D.h. je größer <em>n</em> wird, desto länger dauert es. Man nennt das auch lineare Performanz, linear in <em>n</em>. Oder in Kurzform: O(n).</p>
<h3>
Linear Performance, Recursion: O(n)</h3>
<p>
Auch Rekursion kann lineare Performanz haben. Unsere erste rekursive Lösung war wie folgt:</p>
<pre style="margin-left: 40px;">
1. int powerRe(int x, int n) {
2. if (n == 0)
3. return 1;
4. else
5. return x * <span style="color:#0000ff;">powerRe(x, n-1)</span>;
6. }
</pre>
<p>
Wir analysieren wieder Zeile für Zeile:</p>
<ol>
<li>
wir müssen x und n in den CPU-Registern speichern, das sind 2 Anweisungen;</li>
<li>
ein einfacher Vergleich, 1 Anweisung;</li>
<li>
return schreibt etwas in den Speicher, d.h. 1 Anweisung;</li>
<li>
<em>else</em> zählt nicht als Anweisung, ist Teil von <em>if</em>, also 0 Anweisungen;</li>
<li>
das ist jetzt wieder etwas komplizierter, gehen wir von rechts nach links vor:
<ol>
<li>
wir subtrahieren 1 von n, 1 Anweisung;</li>
<li>
wir rufen uns selbst auf: keine Ahnung wie lange das dauert, also ? Anweisungen</li>
<li>
eine Multiplikation, 1 Anweisung;</li>
<li>
wir geben etwas zurück, das ist 1 Anweisung.</li>
</ol>
</li>
</ol>
<p>
Heiklig ist der rekursive Aufruf. Wie kann man den abschätzen? Um ein Gefühl dafür zu bekommen was passiert, wählen wir einfach mal verschiedene <em>n</em>, beginnend mit n = 0:</p>
<ul>
<li>
<strong>n=0:</strong> es gibt gar keinen rekursiven Anruf, wir kommen nur zur Zeile 3, macht insgesamt 4 Anweisungen;</li>
<li>
<strong>n=1:</strong> hier gibt es einen rekursiven Anruf, der benötigt 4 Anweisungen (d.h. n = 0), womit wir insgesamt bei 2 + 1 +1 + <span style="color:#0000ff;">4</span> + 1 + 1 = <span style="color:#0000ff;">4</span> + 6 = 10 Anweisungen wären;</li>
<li>
<strong>n=2:</strong> hier gibt es einen rekursiven Aufruf zu n = 1, der 9 Anweisungen benötigt, wie wir gerades festgestellt haben, also in Summe 2 + 1 + 1 + <span style="color:#0000ff;">9</span> + 1 + 1 = <span style="color:#0000ff;">9</span> + 6 = 15 Anweisungen.</li>
</ul>
<p>
Wie wir sehen, fügen wir mit jedem weiteren Schritt weitere 6 Anweisungen hinzu. Damit können wir die Anzahl der Anweisungen für ein beliebiges <em>n</em> vorhersagen:</p>
<pre style="margin-left: 40px;">
# of instructions = 4 + 6*n ~ n</pre>
<p>
Das sieht fast genauso aus wie bei der Iteration, nur mit einem anderen Faktor. Wieder, je größere <em>n</em> wird, desto länger dauert es. Auch hier haben wir es mit linearer Performanz zu tun. In Kurzform: O(n).</p>
<h3>
Logarithmic Performance, Divide and Conquer: O(log(n))</h3>
<p>
Kommen wir zu unserem zweiten rekursiven Ansatz, der <em>Divide and Conquer</em> Lösung:</p>
<pre style="margin-left: 40px;">
1. int powerDC(int x, int n) {
2. if (n == 0)
3. return 1;
4. else {
5. int temp = powerDC(x, n/2);
6. return temp * temp;
7. }
8. }
</pre>
<p>
Wir haben eine etwas einfachere Version des Algorithmus ausgewählt, die nur für Potenzen von 2 funktioniert, also n = 1, 2, 4, 8, 16, .... Wir könnten auch die genaue Lösung von vorher nehmen, aber es wäre ein bischen komplizierter. Wir analysieren wieder jede Zeile:</p>
<ol>
<li>
wir speichern wieder x und n in den Registern der CPU, also 2 Anweisungen;</li>
<li>
ein einfacher Vergleich, 1 Anweisung;</li>
<li>
return speichert in den Speicher, d.h., 1 Anweisung;</li>
<li>
<em>else</em> zählt wieder nicht, 0 Anweisungen;</li>
<li>
hier wird es wieder etwas komplizierter:
<ol>
<li>
erst mal dividieren wir durch 2, bei Ganzzahlen ist das ein einfacher Shift, also 1 Anweisung;</li>
<li>
dann rufen wir uns selbst auf: hängt von <em>n</em> ab wie lange das dauert, ? Anweisungen;</li>
<li>
und zu letzt, noch ein Zuweisung, macht 1 Anweisung;</li>
</ol>
</li>
<li>
hier haben wir eine Multiplikation und ein <em>return</em> Statement, sollten 2 Anweisungen sein.</li>
</ol>
<p>
Wie vorher ist auch hier der rekursive Aufruf den wir uns genauer ansehen müssen. Wie oben, nehmen wir einfach mal ein paar verschiedene <em>n</em>, beginnend mit 0:</p>
<ul>
<li>
<strong>n=0:</strong> es gibt keinen rekursiven Anruf, wir kommen nur zur Zeile 3, also insgesamt 4 Anweisungen;</li>
<li>
<strong>n=1:</strong> es gibt einen rekursiven Anruf, der 4 Befehle benötigt (d.h. n=0), in Summe also: 2 + 1 + 1 + <span style="color:#0000ff;">4</span> + 1 + 2 = <span style="color:#0000ff;">4</span> + 7 = 11 Anweisungen;</li>
<li>
<strong>n=2:</strong> es gibt einen rekursiven Aufruf zu n=2, der 11 Befehle benötigt, in Summe also: 2+1+1+<span style="color:#0000ff;">11</span>+1+2 = <span style="color:#0000ff;">11</span> + 7 = 18 Anweisungen;</li>
<li>
<strong>n=4:</strong> es gibt einen rekursiven Aufruf zu n=4, der 18 Befehle benötigt, in Summe also: 2+1+1+<span style="color:#0000ff;">18</span>+1+2 = <span style="color:#0000ff;">18</span> + 7 = 25 Anweisungen.</li>
</ul>
<p>
Also keine große Sache, oder? Vergleichen wir mal Äpfel mit Birnen, soll heißen, vergleichen wir mal den einfachen rekursiven Ansatz mit der Divide and Conquer Lösung:</p>
<table border="1" cellpadding="1" cellspacing="1" style="width: 400px; height: 64px;">
<tbody>
<tr>
<td style="text-align: center;">
log_2(n)</td>
<td align="center">
n</td>
<td align="center">
recursion</td>
<td align="center">
divide & conquer</td>
</tr>
<tr>
<td style="text-align: center;">
0</td>
<td align="center">
1</td>
<td align="center">
9</td>
<td align="center">
11</td>
</tr>
<tr>
<td style="text-align: center;">
1</td>
<td align="center">
2</td>
<td align="center">
14</td>
<td align="center">
18</td>
</tr>
<tr>
<td style="text-align: center;">
2</td>
<td align="center">
4</td>
<td align="center">
24</td>
<td align="center">
25</td>
</tr>
<tr>
<td style="text-align: center;">
3</td>
<td align="center">
8</td>
<td align="center">
44</td>
<td align="center">
32</td>
</tr>
<tr>
<td style="text-align: center;">
4</td>
<td align="center">
16</td>
<td align="center">
84</td>
<td align="center">
39</td>
</tr>
<tr>
<td style="text-align: center;">
5</td>
<td align="center">
32</td>
<td align="center">
164</td>
<td align="center">
46</td>
</tr>
<tr>
<td style="text-align: center;">
6</td>
<td align="center">
64</td>
<td align="center">
324</td>
<td align="center">
53</td>
</tr>
</tbody>
</table>
<p>
Solange <em>n</em> klein ist, ist kaum ein Unterschied festzustellen. Aber sobald <em>n</em> ein bischen größer wird, z.B. 64, dann beginnt man einen Unterschied festzustellen. Und je größer <em>n</em> wird, desto größer wird auch der Unterschied. Wir können ganz einfach sehen, dass für den Divide and Conquer Algorithmus die Anzahl der Anweisungen gegeben ist durch</p>
<pre style="margin-left: 40px;">
# of instructions = 11 + 7* Log_2( n )</pre>
<p>
Dabei ist <em>log_2()</em> der Logarithmus zu Basis zwei. Dies ist das erste Mal, dass wir einem Algorithmus begegnen der logarithmisch in seiner Performanz ist, in Kurzform: O(log(n)). Logarithmisch ist gut, weil es schnell bedeutet!</p>
<p>
.</p>
<h2>
Comparing Algorithms and Big-O Notation</h2>
<p>
Für die vier Algorithmen die wir bisher genauer analysiert haben, haben wir folgendes herausgefunden:</p>
<table border="1" cellpadding="1" cellspacing="1" style="width: 400px; height: 64px;">
<tbody>
<tr>
<td>
</td>
<td align="center">
# of instructions</td>
<td align="center">
Big-O</td>
</tr>
<tr>
<td>
powerApprox()</td>
<td align="center">
28</td>
<td align="center">
O( 1 )</td>
</tr>
<tr>
<td>
powerIt()</td>
<td align="center">
5 + 3 * n</td>
<td align="center">
O( n )</td>
</tr>
<tr>
<td>
powerRe()</td>
<td align="center">
4 + 5 * n</td>
<td align="center">
O( n )</td>
</tr>
<tr>
<td>
powerDC()</td>
<td align="center">
4 + 7 * log( n )</td>
<td align="center">
O( log(n) )</td>
</tr>
</tbody>
</table>
<p>
Wenn die <em>n</em> sehr groß werden, dann spielen konstante Faktoren eigentlich nur eine sehr geringe Rolle, weswegen wir sie vernachlässigen. Wir benutzen dann etwas, das wir als Big-O Notation bezeichnen: uns interessiert nur wie das Laufzeitverhalten, die Performanz, von <em>n</em> abhängt. Noch genauer, uns interessiert eigentlich nur das Verhalten für den schlimmsten Fall, deswegen ignorieren wir alle Faktoren die für große <em>n</em> unwichtig werden:</p>
<pre style="margin-left: 40px;">
Time = 2 * n + 4 -> O(n)
Time = 4 * n - 1 -> O(n)
Time = 1/4 * n² - n -> O(n²)
Time = 2n + n² -> O(2n)
</pre>
<p>
Der Grund warum Big-O so nützlich ist, hat damit zu tun, dass es uns erlaubt abzuschätzen wie lange eine Berechnung dauern wird. </p>
<p>
Nehmen wir an wir hätten drei Algorithmen, einen der linear ist, O(n), einen der quadratisch ist, O(n²), und einen der exponentiell ist, O(2<sup>n</sup>). Bei ersten Tests konnten wir messen, dass die Berechnung für n=1 ungefähr 1 Millisekunde gedauet hat. Die Frage ist wie lange wird es wohl dauern für n=100?</p>
<ul>
<li>
<strong>O(n):</strong> da der Algorithmus linear ist, wird er proportional zu n sein, d.h. er wird ca. 100 Millisekunden benötigen, das ist eine Zehntelsekunde. Das ist ok.</li>
<li>
<strong>O(n²):</strong> der Algorithmus ist quadratisch, d.h., wir müssen die n=100 quadrieren, also 10000, d.h. es dauert ca. 10 Sekunden, das ist auch noch o.k.</li>
<li>
<strong>O(2<sup>n</sup>):</strong> der Algorithmus ist exponentiell, d.h., wir müssen 2 hoch 100 nehmen, was in etwa 10<sup>30</sup> Millisekunden oder 10<sup>27</sup> Sekunden sind. </li>
</ul>
<p>
Ist das viel oder wenig? Nun das Alter des Universum ist ungefähr 10<sup>17</sup> Sekunden. Wir werden also das Ende der Rechnung nicht mehr erleben.</p>
<p>
.</p>
<h2>
Best-Worst-Average Case</h2>
<p>
Häufig hängt das Laufzeitverhalten eines Algorthmus von der Eingabe ab. Als Beispiel betrachten wir die Suche in einem Array von Strings:</p>
<pre style="margin-left: 40px;">
boolean search(String[] names, String key) {
for (int i=0; i < names.length; i++) {
if (names[i] == key) return true;
}
return false;
}
</pre>
<p>
Wie lange dauert es, wenn der gesuchte String am Anfang, in der Mitte, am Ende oder vielleicht gar nicht im Array ist?</p>
<ul>
<li>
Best case:<br />
Wenn der gesuchte String am Anfang ist, dann ist das super-schnell. Ein Vergleich und wir sind fertig.<br />
</li>
<li>
Worst case:<br />
Ist der gesuchte String am Ende oder vielleicht gar nicht im Array, dann dauert das am längsten: wir müssen durch das gesamte Array suchen. Das ist also der schlimmste Fall.<br />
</li>
<li>
Average case:<br />
Der gesuchte String ist irgendwo in der Mitte. Das ist der Durchschnittsfall. Der ist allerdings sehr häufig gar nicht so einfach zu berechnen.</li>
</ul>
<p>
Deswegen interessiert uns eigentlich in der Regel der schlimmste Fall, und das ist was uns die Big-O Notation gibt.</p>
<p>
.</p>
<hr />
<h1>
Review</h1>
<p>
In diesem Kapitel haben wir mehrere neue Konzepte kennengelernt, dazu gehören Approximation, Dynamische Programmierung und der Divide and Conquer Ansatz. Im Allgemeinen gilt, dass es sehr häufig mehrere Algorithmen gibt ein bestimmtes Problem zu lösen. Wir haben gesehen, wie man die Performanz eines Algorithmus messen kann, aber auch wie man mittels detailierter Analyse auch die Performanz eines Algorithmus vorhersagen kann. Dabei war aber auch wichtig festzuhalten, dass nicht immer Geschwindigkeit das Kriterium sein muss nach dem man einen bestimmten Algorithmus auswählt.</p>
<p>
.</p>
<hr />
<h1>
Projekte</h1>
<p>
In den Projekten wollen wir das jetzt ein bischen durch Beispiele vertiefen. Wir sollten dabei auch ein Gefühl dafür bekommen welches Laufzeitverhalten, O(...), vertretbar ist, und welches für alle praktischen Anwendungen nutzlos ist, weil es einfach zu lange dauert.</p>
<p>
.</p>
<h2>
<img alt="" src="images/MinimumMaximumAndAverage.png" style="margin-left: 10px; margin-right: 10px; width: 200px; height: 100px; float: right;" />Minimum, Maximum and Average</h2>
<p>
Nehmen wir an wir haben ein Array mit den folgenden Ganzzahlen gegeben:</p>
<pre style="margin-left: 40px;">
int[] arrOfInts = { 5, 55, 2, 7, 45, 3, 1, 8, 23, 12 };</pre>
<p>
Wir wollen nun drei Methoden schreiben,</p>
<ol>
<li>
eine, die das kleinste Element findet,</li>
<li>
eine, die das größte Element findet,</li>
<li>
und eine Methode die den Durchschnitt berechnet.</li>
</ol>
<p>
Dabei wollen wir das Laufzeitverhalten dieser drei Algorithmen bestimmen, entweder über Messungen oder über eine algorithmische Analyse wie wir es oben getan haben.</p>
<p>
Die Frage die sich stellt, ist der Algorithmus den wir gefunden haben der einzige oder gibt es auch andere? Und ist er der schnellste? Was wäre denn wenn unser Array sortiert wäre? Könnten wir dann einen anderen Algorithmus finden, und wie wäre sein Laufzeitverhalten?</p>
<p>
.</p>
<h2>
<img alt="" src="images/rabbits.png" style="margin-left: 10px; margin-right: 10px; width: 200px; height: 100px; float: right;" />Rabbits</h2>
<p>
Jeder der schon mal Kaninchen hatte weiß, dass diese eine interessante Eigenschaft haben: sie vermehren sich und zwar rasant. Wir wollen also ein Programm schreiben welches berechnet wie sich unsere Kaninchen-Population über die Monate entwickelt. Wir folgen dazu dem Modell von Fibonacci [6]:</p>
<ul>
<li>
"Jedes Paar Kaninchen wirft pro Monat ein weiteres Paar Kaninchen.</li>
<li>
Ein neugeborenes Paar bekommt erst im zweiten Lebensmonat Nachwuchs (die Austragungszeit reicht von einem Monat in den nächsten).</li>
<li>
Die Tiere befinden sich in einem abgeschlossenen Raum, sodass kein Tier die Population verlassen und keines von außen hinzukommen kann."</li>
</ul>
<p>
Wenn wir die Simulation richtig schreiben, dann müsste dabei die Fibonacci-Folge, also</p>
<pre style="margin-left: 40px;">
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...</pre>
<p>
herauskommen. Interessant ist vielleicht zu beobachten, dass jede Zahl die Summe ihrer zwei Vorgängerzahlen ist.</p>
<p>
.</p>
<h2>
<img alt="" src="images/FibonacciGraphics.png" style="margin-left: 10px; margin-right: 10px; width: 200px; height: 200px; float: right;" />FibonacciGraphics</h2>
<p>
Die Fibonacci Zahlen kann man sehr schön visualisieren, eine davon ist die Fibonacci-Spirale [6]. Schauen wir uns die Zahlen noch einmal an:</p>
<pre style="margin-left: 40px;">
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...</pre>
<p>
Wir wollen daraus ein Kachelmuster aus Quadraten generieren, deren Kantenlängen den Fibonacci Zahlen entspricht. Wir gehen wie folgt vor:</p>
<ol>
<li>
lege in die Mitte das ersten Quadrat, rechts daneben legen wir das zweite Quadrat;</li>
<li>
dann machen wir eine 90 Grad Drehung gegen den Uhrzeigersinn, und legen dort das nächste Quadrat hin;</li>
<li>
wir wiederholen Schritt 2.</li>
</ol>
<p>
Obwohl der Algorithmus total trivial aussieht, kann man bei der Umsetzung verzweifeln. Man darf sich die Lösung anschauen!</p>
<p>
.</p>
<h2>
Fibonacci</h2>
<p>
Bisher haben wir nur Fakultät und Potenzen ausführlich behandelt. Ein anderes sehr schönes Beispiel das mit vielen unterschiedlichen Algorithmen gelöst werden kann ist die Berechnung der Fibonacci-Folge.</p>
<h3>
Iteration</h3>
<p>
Für den iterativen Algorithmus muss man lediglich wissen, dass jede Zahl die Summe ihrer zwei Vorgängerzahlen ist. Man beginnt dann einfach mit den ersten beiden, die ja bekannt sind, und berechnet dann eine nach der anderen, bis man diejenige hat die gewünscht war.</p>
<h3>
Recursion</h3>
<p>
Die rekursive Version ist sehr elegant:</p>
<pre style="margin-left: 40px;">
public static long fibonacciRecursive(int n) {
switch (n) {
case 0:
return 0;
case 1:
return 1;
default:
return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}
}</pre>
<p>
aber auch ätzend langsam. Sobald n größer als 40 wird ist die rekursive Version nicht zu gebrauchen.</p>
<h3>
Divide and Conquer</h3>
<p>
Es gibt auch eine Divide and Conquer Version zur Berechnung der Fibonacci-Folge, die kann man bei Referenz [7] auf Seite 457 finden.</p>
<h3>
Dynamic Programming</h3>
<p>
Die Fibonacci-Folge ist eigentlich eine sehr schöne Anwendung um Dynamische Programmierung richtig zu machen. Sie basiert auf der rekursiven Version, aber anstelle immer und immer wieder die gleichen Zahlen auszurechnen, merkt sie sich wenn sie etwas schon mal ausgerechnet hat:</p>
<pre style="margin-left: 40px;">
public static long[] fibonacciDynamicProgrammingTable = new long[91 + 1];
private static long fibonacciDynamicProgramming(int n) {
if (n == 0) {
return 0;
} else if (fibonacciDynamicProgrammingTable[n] > 0) {
// we have done this calculation before
return fibonacciDynamicProgrammingTable[n];
} else {
long result = 1;
switch (n) {
case 1:
break;
default:
result = fibonacciDynamicProgramming(n - 1)
+ fibonacciDynamicProgramming(n - 2);
}
// remember for future use, in case we need it again
fibonacciDynamicProgrammingTable[n] = result;
return result;
}
}</pre>
<p>
Diese Version ist extrem schnell.</p>
<h3>
Lookup Table</h3>
<p>
Klar Lookup Tables haben wir schon mal gesehen. Aber in diesem Beispiel sehen wir auch den Unterschied zwischen Lookup Tables und Dynamischer Programmierung: Bei Lookup Tables werden alle Werte vorausberechnet. Bei Dynamischer Programmierung werden nur die Werte berechnet die wirklich benötigt werden.</p>
<h3>
Approximation</h3>
<p>
Auch für die Fibonacci Zahlen gibt es eine Näherungsformel [6]:</p>
<p style="margin-left: 40px;">
<img alt="" src="images/FibonacciApproximation.png" style="margin-left: 10px; margin-right: 10px; width: 163px; height: 53px;" /></p>
<p>
wobei</p>
<p style="margin-left: 40px;">
<img alt="" src="images/FibonacciPhi.png" style="margin-left: 10px; margin-right: 10px; width: 265px; height: 47px;" /></p>
<p>
die <em>Goldene Zahl</em> ist.</p>
<h3>
Results</h3>
<p>
Hier sind meine Resultate:</p>
<pre style="margin-left: 40px;">
time iterative: 268ms
time divide and conquer: 2418ms
time dynamic programming: 3ms
time lookup table: 3ms
time approximation: 11ms</pre>
<p>
Interessant ist hier die Dynamische Programmierung: sie ist super-schnell, aber sie hat die Eleganz des rekursiven Algorithmus, macht aber keine unnötigen Berechnungen so wie der Lookup Table Algorithmus, wo ja alles im Voraus berechnet werden muss. (Direkte Rekursion ist nicht dabei, weil sie zu lange dauert, das Buch muss ja irgendwann in den Druck).</p>
<p>
.</p>
<h2>
Exponential vs. Factorial Time</h2>
<p>
Bisher haben wir uns eigentlich nur mit "schnellen" Algorithmen beschäftigt, also solchen deren Laufzeitverhalten O(n), O(log(n) oder O(1) waren. Jetzt wollen wir uns mal kurz mit Algorithmen beschäftigen, deren Laufzeitverhalten eher schlecht ist. Im nächsten Kapitel sehen wir welche mit O(n²) deswegen beschränken wir uns hier auf die mit exponentiellem Laufzeitverhalten oder noch schlimmer faktoriellem.</p>
<p>
Im letzten Kapitel haben wir vier interessante rekursive Algorithmen kennen gelernt:</p>
<ul>
<li>
Subsets,</li>
<li>
Combinationen,</li>
<li>
Permutationen</li>
<li>
und das Tower of Hanoi Problem.</li>
</ul>
<p>
Die Frage die wir hier beantworten wollen, wie ist ihr Laufzeitverhalten? Es gibt zwei Möglichkeiten das zu tun:</p>
<ol>
<li>
den Code für verschieden große Inputs ausführen und die Zeit zu messen;</li>
<li>
eine asymptotische Analyse wie oben ausführen, in der man für verschiedene n zählt oder abschätzt wieviele Anweisungen notwendig sein werden.</li>
</ol>
<p>
Viel Spaß!</p>
<p>
.</p>
<hr />
<h1>
Challenges</h1>
<p>
.</p>
<h2>
<img alt="" src="images/HowMany.png" style="margin-left: 10px; margin-right: 10px; width: 200px; height: 150px; float: right;" />How Many</h2>
<p>
Bevor wir mit dieser Übung beginnen, sollten wir uns erst einmal ausrechnen wieviele Sekunden hat ein Tag, hat ein Jahr, macht ein durchschnttliches Menschenleben aus, und wie alt ist das Universum in Sekunden.</p>
<p>
In der Übung geht es darum einfach mal die Werte der mathematischen Funktionen</p>
<ul>
<li>
log(n)</li>
<li>
n</li>
<li>
n * log(n)</li>
<li>
n²</li>
<li>
2<sup>n</sup></li>
<li>
n!</li>
</ul>
<p>
für verschiedene <em>n</em> tabellarisch auszugeben. Dabei wollen wir uns aber auf die folgenden <em>n</em> beschränken: 2, 4, 8, 16, 32, 64, 128, 256, 512 und 1024. Das Ganze machen wir mit einem ConsoleProgram. (log(n) ist hier der Logarithmus zur Basis zwei).</p>
<p>
Wenn wir jetzt einfach mal annehmen, dass die Zahlen in der Tabelle proportional zur Anzahl der CPU Zyklen sind, und ein CPU Zyklus typisch im 100 Nanosekunden (10<sup>-7</sup> Sekunden) Bereich liegt, können wir abschätzen wielange die entsprechenden Algorithmen benötigen würden um fertig zu werden.</p>
<p>
.</p>
<h2>
<img alt="" src="images/algorthmic_growth.png" style="margin-left: 10px; margin-right: 10px; width: 200px; height: 225px; float: right;" />FunctionPlot</h2>
<p>
Vielleicht noch besser als die tabellarische Darstellung ist die graphische. Die meiste Arbeit haben wir in der vorhergehenden Übung schon gemacht, jetzt geht es nur noch darum das in ein GraphicsProgram zu verpacken. Dabei lassen wir die x-Werte von 0.1 bis 40 variieren, berechnen die jeweiligen y-Werte für die verschiedenen Funktionen von oben, und zeichnen dieses. Z.B. die Methode die die lineare Funktion zeichnet, könnte wie folgt aussehen:</p>
<pre style="margin-left: 40px;">
private void plotLinear() {
double x0 = 0;
double y0 = SIZE;
for (double x = 0; x < SIZE; x++) {
double x1 = 0 + x * SCALE;
double y = (SIZE - x1 / SCALE);
if (y < 0)
break;
drawLine(x0, y0, x, y, Color.BLUE);
x0 = x;
y0 = y;
}
}</pre>
<p>
dabei zeichnet die Methode <em>drawLine()</em> einfach eine GLine zwischen zwei Punkten:</p>
<pre style="margin-left: 40px;">
private void drawLine(double x0, double y0, double x, double y, Color col) {
GLine line = new GLine(x0, y0, x, y);
line.setColor(col);
add(line);
}</pre>
<p>
.</p>
<h2>
<img alt="" src="images/rabbits.png" style="margin-left: 10px; margin-right: 10px; width: 200px; height: 100px; float: right;" />Lookup Table</h2>
<p>
Wenn wir den Sinus einer Zahl berechnen wollen verwenden wir normalerweise die Taylorreihen Entwicklung [4]:</p>
<p style="margin-left: 40px;">
<img alt="" src="images/SineTaylorSeries.png" style="margin-left: 10px; margin-right: 10px; width: 269px; height: 48px;" /></p>
<p>
wobei hier <em>x</em> im Bogenmaß ist. </p>
<p>
Als erstes wollen wir eine Methode namens <em>sineTaylor(double x)</em> schreiben die den Sinus einer beliebigen Zahl mittels der Taylorreihen Entwicklung berechnet. </p>
<p>
Als zweites, benutzen wir die in Java gegebenen Methode <em>Math.sin()</em> zum Vergleich, ob unsere Methode auch taugt.</p>
<p>
Als drittes, verwenden wir Lookup-Tables, also Nachschlagetabellen. Dazu schreiben wir eine Methode <em>sineLookup(double x)</em>, die eine vorher berechnete Lookup-Table verwendet um den Sinus "zu berechnen". Übrigens, moderne GPUs verwenden genau diesen Ansatz [5].</p>
<p>
Jetzt ist die Frage, welcher der drei Ansätze ist der schnellste? Wir können hier auch wieder einfach Zeitmessungen machen, oder wir können eine algorithmische Analyse durchführen. Dieses mal machen wir ein Zeitmessung.</p>
<h3>
Careful!</h3>
<p>
Eine kurze Anmerkung: wenn man Performanztests macht, muss man immer sehr vorsichtig sein nicht einer Compiler-Optimierung zum Opfer zu fallen. Der Test könnte erst mal naiv so aussehen:</p>
<pre style="margin-left: 40px;">
long start = System.currentTimeMillis();
for (int i = 0; i < NR_OF_ITERATIONS; i++) {
<span style="color:#ff0000;">int x = Math.sin(1.2);</span>
}
long duration = System.currentTimeMillis() - start;
System.out.println("time Math.sin(): " + duration);</pre>
<p>
Ganz kritisch ist dabei was genau in der Schleife steht. Wenn wir das so schreiben wie oben, erkennt der Compiler nämlich dass <em>x</em> eine lokale Variable ist, und dass danach gar nichts mehr mit ihr passiert. D.h. er ist schlau genug zu wissen, dass er <em>x</em> gar nicht ausrechnen muss. Deswegen macht er es auch nicht. </p>
<p>
Deswegen rüsten wir auf, und deklarieren x als Instanz- oder Klassenvariable:</p>
<pre style="margin-left: 40px;">
x = Math.sin(1.2);</pre>
<p>
Jetzt kann der Compiler nicht wissen ob wir evtl. <em>x</em> irgendwo anders brauchen, und muss es daher ausrechnen. Aber der Compiler ist immer noch schlauer als wir: er sieht nämlich, dass 1.2 eine Konstante ist. Also warum soll er das denn zig-millionenmal ausrechnen, kommt ja doch immer dasselbe raus. Deswegen müssen wir noch einen drauflegen:</p>
<pre style="margin-left: 40px;">
x = Math.sin(Math.random());</pre>
<p>
Erst jetzt kann man mit den Zeiten die rauskommen etwas anfangen. Und da stellt sich folgendes heraus:</p>
<pre style="margin-left: 40px;">
time Math.sin(): 6473ms
time sineTaylor(): 3324ms
time sineLookup(): 2476ms </pre>
<p>
Unsere selbstgeschriebe <em>sineTaylor()</em> Methode ist ungefähr doppelt so schnell wie die Java native (unsere ist aber viel ungenauer) und die <em>sineLookup()</em> Methode ist noch mal 30% schneller, allerdings auch ungenauer. Man kann mit ein paar Tricks die Genauigkeit der Lookup Methode aber so erhöhen, dass es sich einfach nicht rentiert Taylor loszuschicken [5].</p>
<p>
.</p>
<hr />
<h1>
Research</h1>
<p>
Diesem Kapitel war ziemlich anstrengend, deswegen wollen wir hier nicht ganz so viel forschen.</p>
<p>
.</p>
<h2>
Why is recursion so slow?</h2>
<p>
Wenn wir unsere algorithmische Analyse z.B. für das Power Problem betrachten, wo wir ja die Iteration mit der Rekursion vergleichen, dann würde man naiv erwarten, dass die Rekursion etwa zweimal langsamer ist als die Iteration. In Wirklichkeit sieht der Unterschied eher wie ein Faktor Tausend aus. Warum ist das? Um der Sache auf die Spur zu kommen, müssen wir uns erkundigen was denn auf der Maschinesprach-Ebene alles passiert wenn eine Methode aufgerufen wird.</p>
<p>
.</p>
<hr />
<h1>
Fragen</h1>
<ol>
<li>
Kommt es bei Permutationen auf die Reihenfolge an?<br />
</li>
<li>
Geben Sie ein Beispiel für einen <em>Divide and Conquer</em> Algorithmus.<br />
</li>
<li>
Betrachten Sie den folgenden Code:<br />
<pre style="margin-left: 40px;">
boolean search(List<String> names, String key) {
for (int i=0; i < names.size(); i++) {
if (names[i] == key) return true;
}
return false;
}</pre>
Wie ist sein Laufzeitverhalten im besten Fall, im schlimmsten Fall und was ist das durchschnittliche Laufzeitverhalten?<br />
</li>
<li>
Hat das "Tower of Hanoi" -Problem exponentielles oder faktorielles Laufzeitverhalten? Welches ist schlimmer? (Hinweis: Stirling's Formel)<br />
</li>
<li>
Algorithmen können präzise oder ungenau sein. Geben Sie ein Beispiel für einen ungenauen Algorithmus.<br />
</li>
<li>
Welche Art von asymptotischem Laufzeitverhalten (d.h. Big-O-Notation) hat der folgende Algorithmus?<br />
<pre style="margin-left: 40px;">
double celsiusToFahrenheit(double temp) {
return temp*9.0/5.0 + 32;
}</pre>
</li>
<li>
Geben Sie einen Algorithmus zur Schätzung der Anzahl der Personen in einem Fußballstadion, der von Ordnung O(log (n)) ist.<br />
</li>
<li>
Wann würden Sie einen Algorithmus als effizient bezeichnen?<br />
</li>
<li>
Schätzen Sie das Laufzeitverhalten (große O-Notation) für die folgenden Algorithmen:
<ul>
<li>
f(n) = 24*n + 14</li>
<li>
f(n) = 54333*n</li>
<li>
f(n) = 3*n² + 4<br />
</li>
</ul>
</li>
<li>
Betrachten Sie den folgenden Code. Nehmen Sie an, dass eine Anweisung ca. 1ms dauert. Geben Sie zunächst eine grobe Formel, um die Laufzeit in Bezug auf n zu abzuschätzen. Dann nehmen Sie an, dass n = 1000 ist und dass eine Anweisung ca. 1ms dauert. Wie lange dauert es bis die Methode fertig ist?<br />
<pre style="margin-left: 40px;">
public void selectionSortFast(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
}
}</pre>
</li>
</ol>
<p>
.</p>
<hr />
<h1>
Referenzen</h1>
<p>
Die Referenzen für dieses Kapitel sind etwas speziell. Es lohnt sich aber auf jeden Fall einen genaueren Blick auf das Buch von Bruno R. Preiss [7] zu werfen.</p>
<p>
[1] Stirling's approximation, <a href="https://en.wikipedia.org/wiki/Stirling's_approximation">https://en.wikipedia.org/wiki/Stirling's_approximation</a></p>
<p>
[2] Dynamic programming, <a href="https://en.wikipedia.org/wiki/Dynamic_programming">https://en.wikipedia.org/wiki/Dynamic_programming</a></p>
<p>
[3] Wikibook Algorithms, R.Impagliazzo, Ma.Shonle, M.Wilson, M.Krischik, <a href="https://en.wikibooks.org/wiki/Algorithms/Dynamic_Programming">https://en.wikibooks.org/wiki/Algorithms/Dynamic_Programming</a></p>
<p>
[4] Sine, <a href="https://en.wikipedia.org/wiki/Sine">https://en.wikipedia.org/wiki/Sine</a></p>
<p>
[5] Nvidia, Cg 3.1 Toolkit Documentation, <a href="http://http.developer.nvidia.com/Cg/sin.html">http://http.developer.nvidia.com/Cg/sin.html</a></p>
<p>
[6] Fibonacci number, <a href="https://en.wikipedia.org/wiki/Fibonacci_number">https://en.wikipedia.org/wiki/Fibonacci_number</a></p>
<p>
[7] Data Structures and Algorithms, Bruno R. Preiss, <a href="https://www.brpreiss.com/books/opus4/html/page457.html">https://www.brpreiss.com/books/opus4/html/page457.html</a></p>
<p>
.</p>
<p class="footer">
Copyright © 2016-2021 <a href="http://www.lano.de">Ralph P. Lano</a>. All rights reserved.
</p>
</div>
</center>
</div>
</body>
</html>