AD Teaching Wiki:

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.

ma269

1901µs

1538µs

1.24

1332µs

566µs

2.35

122µs

52µs

2.32

C++

Log(n)-step baseline or galloping search with sentinels.

cb382 + mz111

4842µs

2992µs

1.62

5428µs

1487µs

3.65

1687µs

803µs

2.10

Java

Combination of zipper with sentinels & galloping search

yl100

2061µs

1943µs

1.06

1381µs

483µs

2.86

141µs

66µs

2.14

C++

Combination of zipper ,sentinels, and galloping search

fk234

2127µs

1670µs

1.27

1896

466

4.07

146µs

91µs

1.60

C++

Zipper algorithm with sentinels and galloping search

pk104

1514µs

1318µs

1.14

1293

355

3.65

95µs

50µs

1.87

C++

galloping search

AD Teaching Wiki: InformationRetrievalWS1718/ResultsES3 (last edited 2017-11-12 14:06:06 by x5d84e0e7)