|
Size: 2857
Comment:
|
Size: 9166
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 4: | Line 4: |
|| |||||| ''film + rug'' |||||| ''bowling + rug'' |||||| ''film + bowling'' |||||| || |
||<tablewidth=""" tableheight=""" tablestyle="" & quot; & amp; quot; & amp; amp; quot; 908px& amp; amp; amp; quot; ; 1935px& amp; amp; amp; quot& amp; amp; quot; ; & amp; amp; amp; quot& amp; amp; quot; ; & amp; amp; amp; quot& amp; amp; quot& amp; quot; ; & amp; amp; quot& amp; quot; ; & amp; amp; quot& amp; quot& quot; ; & amp; quot& quot; ; & amp; quot& quot" ;&quot";&quot""> ||||||<style="" & quot; & amp; quot; & amp; amp; quot; & amp; amp; amp; quot;text-align:center& amp; amp; amp; quot; & amp; amp; quot; & amp; quot; & quot; "">''film + rug'' ||||||<style="" & quot; & amp; quot; & amp; amp; quot; & amp; amp; amp; quot;text-align:center& amp; amp; amp; quot; & amp; amp; quot; & amp; quot; & quot; "">''bowling + rug'' ||||||<style="" & quot; & amp; quot; & amp; amp; quot; & amp; amp; amp; quot;text-align:center& amp; amp; amp; quot; & amp; amp; quot; & amp; quot; & quot; "">''film + bowling'' ||||||<style="" & quot; & amp; quot; & amp; amp; quot; & amp; amp; amp; quot;text-align:center& amp; amp; amp; quot; & amp; amp; quot; & amp; quot; & quot; ""> || |
| Line 11: | Line 10: |
| ||as954||703μs||11μs||58.58||48μs||9μs||5.33||1747μs||243μs||7.19||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||769μs||645μs||1,19||693μs||562μs||1.23||1013μs||3809μs||0.27||Java||Combination of Sentinels, binary search Search and Binary Search in the remaining longer list.|| ||ad289||1035μs||355μs||2.92||54μs||96μs||0.56||980μs||4574μs||0.21||C++||Combination of Sentinels, Binary Search in the remaining longer list and Skip Pointers.|| |
||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 ||8134µs ||4410µs ||1.21 ||541µs ||464µs ||1.27 ||8064µs ||4281µs ||1.15 ||C++ ||sentinel, binary search in longer list and binary search in remainder of the longer list || ||sm511 ||1532μs ||2977μs ||1.94 ||39μs ||640μs ||16.41 ||1872μs ||4266μs ||2,2 ||Java ||skip pointers, zipper and binary search in remainder of the longer list || ||lf197+yv6 ||915μs ||4407μs ||1.31 ||56μs ||284μs ||0.20 ||1519μs ||6793μs ||0.22 ||Java ||sentinels & binary search in remainder of longer list || ||eb272 ||2618μs ||1981μs ||1.32 ||184μs ||164μs ||1.13 ||2414μs ||6142μs ||0.39 ||Java ||Combination of basic zipper with sentinels and galloping || ||ne38 ||5208μs ||4461μs ||1.17 ||2462μs ||2222μs ||1.10 ||2644μs ||2132μs ||1.24 ||C++ ||Binary Search, binary search in remainder and zipper with sentinels. || ||rs442 ||1489μs ||8708μs ||0.17 ||113μs ||602μs ||0.19 ||2327μs ||7002μs ||0.33 ||C++ ||Combination of Galloping Search, binary search in remainder and zipper. || ||mk1258 ||939μs ||309μs ||3.04 ||103μs ||517μs ||0.20 ||1918μs ||1191μs ||1.61 ||Java ||Combination of Galloping Search and zipper. || ||sk196 ||569μs ||238μs ||2.39 ||41μs ||126μ ||0.33 ||1211μs ||1462μs ||0.83 ||Java ||Combination of galloping, binary search & sentinels. || ||dm191 ||912μs ||343μs ||2.66 ||41μs ||321μ ||0.13 ||1683μs ||4550μs ||0.37 ||Java ||Combination of galloping, binary search & sentinels. || ||mf387 ||1366μs ||945μs ||1.44 ||75μs ||67μ ||1.11 ||2496μs ||2240μs ||1.11 ||Java ||Combination binary search & sentinels. || ||ss981 ||4961μs ||191895μs || 0.02 ||179μs ||866μ ||0.21 ||4628μs ||209425μs ||0.02 ||C++ ||Combination of galloping, binary search & binary search in remainder of the longer list. || ||kf139 ||2050μs ||947μs || 2.16 ||47μs ||247μs ||0.17 ||2302μs ||9406μs ||0.24 ||Java ||Combination of binary search in remainder of longer list & galloping search in remainder of longer list. || ||ta71 ||2883μs ||565μs || 5.10 ||324μs ||75μs ||4.32 ||2266μs ||4311μs ||0.53 ||Java ||binary search remainder + zipper + sentinel. || ||dc122 ||1216μs ||134μs || 9.07 ||86μs ||24μs ||3.58 ||1334μs ||1571μs ||0.84 ||C++ ||either zypper + sentinels, or galloping search + binary search. || ||by19-ms1512 ||4094μs ||1020μs || 4.01 ||164μs ||200μs ||0.82 ||2769μs ||10798μs ||0.25 ||C++ ||Gallop search, binary search, sentinel. || ||ml501-ur22 ||2620μs ||1089μs || 2.40 ||472μs ||436μs ||1.09 ||4590μs ||4035μs ||1.13 ||Java ||Galloping search and Binary search. || |
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 |
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 |
8134µs |
4410µs |
1.21 |
541µs |
464µs |
1.27 |
8064µs |
4281µs |
1.15 |
C++ |
sentinel, binary search in longer list and binary search in remainder of the longer list |
|
sm511 |
1532μs |
2977μs |
1.94 |
39μs |
640μs |
16.41 |
1872μs |
4266μs |
2,2 |
Java |
skip pointers, zipper and binary search in remainder of the longer list |
|
lf197+yv6 |
915μs |
4407μs |
1.31 |
56μs |
284μs |
0.20 |
1519μs |
6793μs |
0.22 |
Java |
sentinels & binary search in remainder of longer list |
|
eb272 |
2618μs |
1981μs |
1.32 |
184μs |
164μs |
1.13 |
2414μs |
6142μs |
0.39 |
Java |
Combination of basic zipper with sentinels and galloping |
|
ne38 |
5208μs |
4461μs |
1.17 |
2462μs |
2222μs |
1.10 |
2644μs |
2132μs |
1.24 |
C++ |
Binary Search, binary search in remainder and zipper with sentinels. |
|
rs442 |
1489μs |
8708μs |
0.17 |
113μs |
602μs |
0.19 |
2327μs |
7002μs |
0.33 |
C++ |
Combination of Galloping Search, binary search in remainder and zipper. |
|
mk1258 |
939μs |
309μs |
3.04 |
103μs |
517μs |
0.20 |
1918μs |
1191μs |
1.61 |
Java |
Combination of Galloping Search and zipper. |
|
sk196 |
569μs |
238μs |
2.39 |
41μs |
126μ |
0.33 |
1211μs |
1462μs |
0.83 |
Java |
Combination of galloping, binary search & sentinels. |
|
dm191 |
912μs |
343μs |
2.66 |
41μs |
321μ |
0.13 |
1683μs |
4550μs |
0.37 |
Java |
Combination of galloping, binary search & sentinels. |
|
mf387 |
1366μs |
945μs |
1.44 |
75μs |
67μ |
1.11 |
2496μs |
2240μs |
1.11 |
Java |
Combination binary search & sentinels. |
|
ss981 |
4961μs |
191895μs |
0.02 |
179μs |
866μ |
0.21 |
4628μs |
209425μs |
0.02 |
C++ |
Combination of galloping, binary search & binary search in remainder of the longer list. |
|
kf139 |
2050μs |
947μs |
2.16 |
47μs |
247μs |
0.17 |
2302μs |
9406μs |
0.24 |
Java |
Combination of binary search in remainder of longer list & galloping search in remainder of longer list. |
|
ta71 |
2883μs |
565μs |
5.10 |
324μs |
75μs |
4.32 |
2266μs |
4311μs |
0.53 |
Java |
binary search remainder + zipper + sentinel. |
|
dc122 |
1216μs |
134μs |
9.07 |
86μs |
24μs |
3.58 |
1334μs |
1571μs |
0.84 |
C++ |
either zypper + sentinels, or galloping search + binary search. |
|
by19-ms1512 |
4094μs |
1020μs |
4.01 |
164μs |
200μs |
0.82 |
2769μs |
10798μs |
0.25 |
C++ |
Gallop search, binary search, sentinel. |
|
ml501-ur22 |
2620μs |
1089μs |
2.40 |
472μs |
436μs |
1.09 |
4590μs |
4035μs |
1.13 |
Java |
Galloping search and Binary search. |
|