Differences between revisions 4 and 39 (spanning 35 versions)

Results for Exercise Sheet 3 (Intersecting Lists)

Add your row to the table below, following the examples already there. In the 1st column, write your account name, or name1+name2 if you work in a group. For each intersection result, write down (1) the runtime of the baseline algorithm, (2) the runtime of your improved algorithm (both in microseconds as an integer) and (3) the speedup ratio as float with exactly two digits of precision, measured as time_for_baseline / time_for_your_algorithm (<1 = slower, >1 = faster). In the last column briefly describe the improvements you implemented.

film + rug

bowling + rug

film + bowling

Name

Baseline

Yours

Ratio

Baseline

Yours

Ratio

Baseline

Yours

Ratio

Language

Summary Improvements

ck1028

8570µs

3298µs

2.59

545µs

520µs

1.05

12920µs

8796µs

1.46

Java

Combination of zipper algorithm & binary search in remainder of longer list; sentinels.

ck1028

1767µs

260µs

6.79

116µs

65µs

1.78

1898µs

1784µs

1.06

C++

Combination of zipper algorithm & galloping search; sentinels.

jt143

5094µs

2566µs

1.98

4518µs

3578µs

1.26

8388µs

6756µs

1.24

Java

Combination of binary search & galloping search; sentinels.

ky18

1328µs

324µs

4.08

81µs

194µs

0.41

2041µs

2394µs

0.85

Java

Combination of binary search, galloping search and zipper; sentinels.

as954

741μs

433μs

1.71

61μs

194μs

0.31

1782μs

5320μs

0.33

Java

Combination of sentinels, galloping search and search in remainder of longer list

ml360

6357μs

2029μs

3,13

550μs

270μs

2,03

11029μs

6854μs

1.61

C++

Combination of sentinels, search in remainder of longer list and binary search and zipper

ak736 + lf124

1880943μs

152283μs

12,35

129737μs

193191μs

0,67

1433462μs

2138159μs

0,67

C++

Combination of binary search & galloping search; sentinels.

ms946

867μs

1008μs

0.86

445μs

503μs

0.88

2139μs

3078μs

0.7

Java

Combination of binary search in remainder of longer list & galloping search in remainder of longer list.

lc133+kt101

4436μs

3513μs

1.26

4492μs

3568μs

1.26

2980μs

2283μs

1.30

Java

Combination of Sentinels, Galloping Search and Binary Search in the remaining longer list.

cn93+aa278

1270μs

775μs

1,64

670μs

553μs

1,21

1149μs

3740μs

0,31

Java

Combination of Sentinels, binary search Search and Binary Search in the remaining longer list.

cn93+aa278

3400μs

983μs

3,46

1801μs

828μs

2,18

3069μs

1907μs

1,61

Java

Combination of Sentinels, Galloping search and Binary Search.

ad289

1010μs

972μs

1.03

1066μs

1015μs

1.05

905μs

567μs

1.60

C++

Combination of Sentinels, Binary Search in the remaining longer list and Skip Pointers.

jd219

1555μs

727μs

2.14

89μs

171μs

0.52

1768μs

9396μs

0.19

C++

Combination of binary search and Sentinels and galloping search.

ar163

872μs

166μs

5.25

41μs

50μs

0.82

1094μs

2176μs

0.50

C++

Combination of galloping search and binary search in both lists.

jh520

4077µs

327µs

12.46

311µs

70µs

4.41

3770µs

326µs

11.53

C++

Combination of sentinels, binary search in the remaining longer list and skip pointers.

vg108

1336µs

255µs

5.23

88µs

50µs

1.76

1569µs

1739µs

0.90

C++

Combination of sentinels, binary search in the remaining longer list and galloping search.

dh234

1757µs

2836µs

0.62

63µs

60µs

1.06

1852µs

15632µs

0.16

java

Combination of binary search in the remaining longer list and galloping search and the baseline zipper algorithm.

em192

14817µs

796µs

18.6143

670µs

397µs

1.69

22091µs

43671µs

0.51

C++

Binary search in the remaining longer list.

pm169+tt93

2909µs

467µs

6.229

116µs

58µs

3105µs

3261µs

0.952

C++

Combination of Sentinels, both binary searches and galloping search.

jd132+mr277

1346µs

833µs

1.61

118µs

99µs

1.19

1879µs

1794µs

1.05

C++

Sentinels; binary search in remainder for intersections with rug.

jh642

1606µs

386µs

4.16

102µs

61µs

1.67

2010µs

2344µs

0.86

C++

Galloping search; binary search in remainder.

pb254

1408µs

863µs

1.63

78µs

59µs

1.32

1610µs

1730µs

0.93

C++

Zipper, Galloping Search Binary Search (and Sentinels).

dv33

1471µs

584µs

2.51

139µs

69µs

2.01

2071µs

1997µs

1.03

Java

Sentinels, Binary search in the remaining longer list for big list differences, else zipper.

mf385

622µs

163µs

3.81

108µs

96µs

1.12

1367µs

1026

1.33

Java

Zipper, Sentinels, Galloping

ch63-nb188

622µs

163µs

3.81

108µs

96µs

1.12

1367µs

1026

1.33

Java

Zipper, Sentinels, Galloping

-  ⇤ ← Revision 4 as of 2018-11-07 01:20:18 → 
  Size: 1601
  Editor: 141
  Comment:
+   ← Revision 39 as of 2018-11-12 20:45:17 → ⇥
  Size: 5475
  Editor: p5DD8D458
  Comment:
-Deletions are marked like this.
+Additions are marked like this.
 Line 4:
-|| |||||| ''film + rug'' |||||| ''bowling + rug'' |||||| ''film + bowling'' |||||| ||
+||<tablewidth="&quot" tableheight="&quot" tablestyle="908px&quot;;1935px&quot"> ||||||<style="&quot;text-align:center&quot;">''film + rug'' ||||||<style="&quot;text-align:center&quot;">''bowling + rug'' ||||||<style="&quot;text-align:center&quot;">''film + bowling'' ||||||<style="&quot;text-align:center&quot;"> ||
-Line 10:
+Line 9:
-||ky18 ||5094µs ||2566µs ||1.98 ||4518µs ||3578µs ||1.26 ||8388µs ||6756µs ||1.24 ||Java ||Combination of binary search & galloping search; sentinels. ||
+||ky18 ||1328µs ||324µs ||4.08 ||81µs ||194µs ||0.41 ||2041µs ||2394µs ||0.85 ||Java ||Combination of binary search, galloping search and zipper; sentinels. ||
||as954 ||741μs ||433μs ||1.71 ||61μs ||194μs ||0.31 ||1782μs ||5320μs ||0.33 ||Java ||Combination of sentinels, galloping search and search in remainder of longer list ||
||ml360 ||6357μs ||2029μs ||3,13 ||550μs ||270μs ||2,03 ||11029μs ||6854μs ||1.61 ||C++ ||Combination of sentinels, search in remainder of longer list and binary search and zipper ||
||ak736 + lf124 ||1880943μs ||152283μs ||12,35 ||129737μs ||193191μs ||0,67 ||1433462μs ||2138159μs ||0,67 ||C++ ||Combination of binary search & galloping search; sentinels. ||
||ms946 ||867μs ||1008μs ||0.86 ||445μs ||503μs ||0.88 ||2139μs ||3078μs ||0.7 ||Java ||Combination of binary search in remainder of longer list & galloping search in remainder of longer list. ||
||lc133+kt101 ||4436μs ||3513μs ||1.26 ||4492μs ||3568μs ||1.26 ||2980μs ||2283μs ||1.30 ||Java ||Combination of Sentinels, Galloping Search and Binary Search in the remaining longer list. ||
||cn93+aa278 ||1270μs ||775μs ||1,64 ||670μs ||553μs ||1,21 ||1149μs ||3740μs ||0,31 ||Java ||Combination of Sentinels, binary search Search and Binary Search in the remaining longer list. ||
||cn93+aa278 ||3400μs ||983μs ||3,46 ||1801μs ||828μs ||2,18 ||3069μs ||1907μs ||1,61 ||Java ||Combination of Sentinels, Galloping search and Binary Search. ||
||ad289 ||1010μs ||972μs ||1.03 ||1066μs ||1015μs ||1.05 ||905μs ||567μs ||1.60 ||C++ ||Combination of Sentinels, Binary Search in the remaining longer list and Skip Pointers. ||
||jd219 ||1555μs ||727μs ||2.14 ||89μs ||171μs ||0.52 ||1768μs ||9396μs ||0.19 ||C++ ||Combination of binary search and Sentinels and galloping search. ||
||ar163 ||872μs ||166μs ||5.25 ||41μs ||50μs ||0.82 ||1094μs ||2176μs ||0.50 ||C++ ||Combination of galloping search and binary search in both lists. ||
||jh520 ||4077µs ||327µs ||12.46 ||311µs ||70µs ||4.41 ||3770µs ||326µs ||11.53 ||C++ ||Combination of sentinels, binary search in the remaining longer list and skip pointers. ||
||vg108 ||1336µs ||255µs ||5.23 ||88µs ||50µs ||1.76 ||1569µs ||1739µs ||0.90 ||C++ ||Combination of sentinels, binary search in the remaining longer list and galloping search. ||
||dh234 ||1757µs ||2836µs ||0.62 ||63µs ||60µs ||1.06 ||1852µs ||15632µs ||0.16 ||java ||Combination of binary search in the remaining longer list and galloping search and the baseline zipper algorithm. ||
||em192 ||14817µs ||796µs ||18.6143 ||670µs ||397µs ||1.69 ||22091µs ||43671µs ||0.51 ||C++ ||Binary search in the remaining longer list. ||
||pm169+tt93 ||2909µs ||467µs ||6.229 ||116µs ||58µs ||2 ||3105µs ||3261µs ||0.952 ||C++ ||Combination of Sentinels, both binary searches and galloping search. ||
||jd132+mr277 ||1346µs ||833µs ||1.61 ||118µs ||99µs ||1.19 ||1879µs ||1794µs ||1.05 ||C++ ||Sentinels; binary search in remainder for intersections with rug. ||
||jh642 ||1606µs ||386µs ||4.16 ||102µs ||61µs ||1.67 ||2010µs ||2344µs ||0.86 ||C++ ||Galloping search; binary search in remainder. ||
||pb254 ||1408µs ||863µs ||1.63 ||78µs ||59µs ||1.32 ||1610µs ||1730µs ||0.93 ||C++ ||Zipper, Galloping Search Binary Search (and Sentinels). ||
||dv33 ||1471µs ||584µs ||2.51 ||139µs ||69µs ||2.01 ||2071µs ||1997µs ||1.03 ||Java ||Sentinels, Binary search in the remaining longer list for big list differences, else zipper. ||
||mf385 ||622µs ||163µs ||3.81 ||108µs ||96µs ||1.12 ||1367µs ||1026 ||1.33 ||Java ||Zipper, Sentinels, Galloping ||
||ch63-nb188||622µs ||163µs ||3.81 ||108µs ||96µs ||1.12 ||1367µs ||1026 ||1.33 ||Java ||Zipper, Sentinels, Galloping ||

Links

Previous Courses

Results for Exercise Sheet 3 (Intersecting Lists)