|
Size: 1249
Comment:
|
Size: 1522
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 1: | Line 1: |
| #acl Claudius Korzen:read,write All:read | #acl All:read,write |
| Line 10: | Line 10: |
| || ck1028 || ? || ? || 0.00 || ? || ? || 0.00 || ? || ? || 0.00 || Java || Combination of zipper algorithm & galloping search; sentinels. || || ck1028 || ? || ? || 0.00 || ? || ? || 0.00 || ? || ? || 0.00 || C++ || Combination of zipper algorithm & galloping search; sentinels. || |
|| ck1028 || 12920µs || 8796µs || 1.46 || 8570µs || 3298µs || 2.59 || 545µs || 520µs || 1.05 || Java || Combination of zipper algorithm & binary search in remainder of longer list; sentinels. || || ck1028 || 1898µs || 1784µs || 1.06 || 1767µs || 260µs || 6.79 || 116µs || 65µs || 1.78 || C++ || Combination of zipper algorithm & galloping search; sentinels. || || he41 || 8184µs || 1465µs || 5.59 || 8957µs || 1446µs || 6.19 || 2631µs || 1575µs || 1.67 || Java || Combination of zipper algorithm & galloping search; sentinels; Bitwise Operations. || |
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 + bowling |
film + rug |
bowling + rug |
|
||||||||
Name |
Baseline |
Yours |
Ratio |
Baseline |
Yours |
Ratio |
Baseline |
Yours |
Ratio |
Language |
Summary Improvements |
|
ck1028 |
12920µs |
8796µs |
1.46 |
8570µs |
3298µs |
2.59 |
545µs |
520µs |
1.05 |
Java |
Combination of zipper algorithm & binary search in remainder of longer list; sentinels. |
|
ck1028 |
1898µs |
1784µs |
1.06 |
1767µs |
260µs |
6.79 |
116µs |
65µs |
1.78 |
C++ |
Combination of zipper algorithm & galloping search; sentinels. |
|
he41 |
8184µs |
1465µs |
5.59 |
8957µs |
1446µs |
6.19 |
2631µs |
1575µs |
1.67 |
Java |
Combination of zipper algorithm & galloping search; sentinels; Bitwise Operations. |
|