Differences between revisions 16 and 58 (spanning 42 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 + 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

pg152

17024µs

11518µs

1.47

12301µs

3078µs

3.99

4777µs

1334µs

3.58

Java

Binsearch at beginning, Galloping at end

dd74

1785µs

1951µs

0.91

1631µs

575µs

2,84

144µs

143µs

1.01

C++

Zipper algorithm with sentinels, binary search

je113

2049µs

1872µs

1.09

1124µs

497µs

2,26

90µs

89µs

1.01

Java

Skip pointers with sentinels

ck407

30959µs

28967µs

1.07

2102µs

1168µs

1.80

1447µs

1098µs

1.32

Java

Combination of zipper with sentinels and galloping search.

sm362

1854µs

1831µs

1.01

1549µs

432µs

3.58

127µs

81µs

1.57

C++

Combination of zipper algorithm & galloping search

ak745

6292µs

5245µs

1.20

6060µs

1026µs

5.91

1893µs

790µs

2.40

Java

Combination of Galloping search and binary search.

yb36

1443µs

1271µs

1.14

1374µs

227µs

6.03

133µs

38µs

3.47

C++

Zipper + Galloping search + Binary search + Sentinels

ph193

1725µs

1589µs

1.09

1249µs

541µs

2.30

81µs

39µs

2.06

C++

Combination of galloping search with zipper algorithm; sentinels

sr285

4866µs

1533µs

3.17

969µs

587µs

1.65

255µs

118µs

2.16

Java

Combination of Sentinels, Binary and Galloping

fb234

17199µs

9772µs

1.76

11562µs

2570µs

4.50

1103µs

535µs

2.06

Java

Skip pointers in remainder

hn52

2990µs

2997µs

1.00

5996µs

4235µs

1.42

6178µs

4319µs

1.43

C++

Zipper with sentinels and galloping search

es260 + ic30

1293µs

5086µs

0.25

1067µs

262µs

4.07

85µs

104µs

0.82

C++

Combination of galloping, binary and sentinel

js603

1385µs

1274µs

1.09

1551µs

350µs

4.43

106µs

92µs

1.15

C++

Combination of galloping / binary search and baseline

hs211+lb319

1911µs

2272µs

0.84

1816µs

591µs

3.07

123µs

66µs

1.86

C++

Combination of galloping search, predictable branches and remove of redundant initialization

rb201

28211µs

27367µs

1.03

25315µs

9240µs

2.74

10713µs

7272µs

1.47

Java

Zipper + Galloping search + Binary search + Sentinels (yes my hardware is old)

ls305

12293µs

7353µs

1.67

8931µs

7499µs

1.19

4270µs

739µs

5.77

Java

Zipper + Sentinels or Galloping

ns202

1434µs

2380µs

0.60

1421µs

351µs

4.04

103µs

140µs

0.73

C++

Galloping

nf55

1254µs

1068µs

1.17

1149µs

201µs

5.70

68µs

25µs

2.67

C++

Combining Zipper, Galloping search and Binary search

fj47

4395µs

6061µs

0.89

4841µs

831µs

5.82

1948µs

1384µs

1.41

Java

Switch between Zipper, binary on rest or Galopping. Use Sentinels

df121+km109

6297µs

21583µs

0.29

9715µs

5328µs

1.82

2444µs

3466µs

0.71

Java

Galloping search, skip pointers and Binary search

cs568

11487µs

51787µs

0.22

10457µs

4071µs

2.57

824µs

1884µs

0.44

C++

Galloping and binary search in interval

-  ⇤ ← Revision 16 as of 2017-11-07 12:10:36 → 
  Size: 1309
  Editor: Claudius Korzen
  Comment:
+   ← Revision 58 as of 2017-11-13 15:25:10 → ⇥
  Size: 5242
  Editor: 10
  Comment:
-Deletions are marked like this.
+Additions are marked like this.
 Line 1:
-#acl Claudius Korzen:read,write All:read
+#acl All:read,write
-Line 4:
+Line 3:
-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 '''micro'''seconds 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    || 14756µs || 3211µs || 4.59 || 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    || ? || ? || 0.00 || ? || ? || 0.00 || ? || ? || 0.00 || C++  || Combination of zipper algorithm & galloping search; sentinels. ||
+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 '''micro'''seconds 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 ||
||pg152 ||17024µs ||11518µs ||1.47 ||12301µs ||3078µs ||3.99 ||4777µs ||1334µs ||3.58 ||Java ||Binsearch at beginning, Galloping at end ||
||dd74 ||1785µs ||1951µs ||0.91 ||1631µs ||575µs ||2,84 ||144µs ||143µs ||1.01 ||C++ ||Zipper algorithm with sentinels, binary search ||
||je113 ||2049µs ||1872µs ||1.09 ||1124µs ||497µs ||2,26 ||90µs ||89µs ||1.01 ||Java ||Skip pointers with sentinels ||
||ck407 ||30959µs ||28967µs ||1.07 ||2102µs ||1168µs ||1.80 ||1447µs ||1098µs ||1.32 ||Java ||Combination of zipper with sentinels and galloping search. ||
||sm362 ||1854µs ||1831µs ||1.01 ||1549µs ||432µs ||3.58 ||127µs ||81µs ||1.57 ||C++ ||Combination of zipper algorithm & galloping search ||
||ak745 ||6292µs ||5245µs ||1.20 ||6060µs ||1026µs ||5.91 ||1893µs ||790µs ||2.40 ||Java ||Combination of Galloping search and binary search. ||
||yb36 ||1443µs ||1271µs ||1.14 ||1374µs ||227µs ||6.03 ||133µs ||38µs ||3.47 ||C++ ||Zipper + Galloping search + Binary search + Sentinels ||
||ph193 ||1725µs ||1589µs ||1.09 ||1249µs ||541µs ||2.30 ||81µs ||39µs ||2.06 ||C++ ||Combination of galloping search with zipper algorithm; sentinels ||
||sr285 ||4866µs ||1533µs ||3.17 ||969µs ||587µs ||1.65 ||255µs ||118µs ||2.16 ||Java ||Combination of Sentinels, Binary and Galloping ||
||fb234 ||17199µs ||9772µs ||1.76 ||11562µs ||2570µs ||4.50 ||1103µs ||535µs ||2.06 ||Java ||Skip pointers in remainder ||
||hn52 ||2990µs ||2997µs ||1.00 ||5996µs ||4235µs ||1.42 ||6178µs ||4319µs ||1.43 ||C++ ||Zipper with sentinels and galloping search ||
||es260 + ic30||1293µs||5086µs||0.25||1067µs||262µs||4.07||85µs||104µs||0.82||C++||Combination of galloping, binary and sentinel||
||js603||1385µs||1274µs||1.09||1551µs||350µs||4.43||106µs||92µs||1.15||C++||Combination of galloping / binary search and baseline||
||hs211+lb319||1911µs||2272µs||0.84||1816µs||591µs||3.07||123µs||66µs||1.86||C++||Combination of galloping search, predictable branches and remove of redundant initialization||
||rb201||28211µs||27367µs||1.03||25315µs||9240µs||2.74||10713µs||7272µs||1.47||Java||Zipper + Galloping search + Binary search + Sentinels (yes my hardware is old)||
||ls305||12293µs||7353µs||1.67||8931µs||7499µs||1.19||4270µs||739µs||5.77||Java||Zipper + Sentinels or Galloping||
||ns202||1434µs||2380µs||0.60||1421µs||351µs||4.04||103µs||140µs||0.73||C++||Galloping||
||nf55 ||1254µs ||1068µs ||1.17 ||1149µs ||201µs ||5.70 ||68µs ||25µs ||2.67 ||C++ ||Combining Zipper, Galloping search and Binary search ||
||fj47 ||4395µs ||6061µs ||0.89||4841µs ||831µs ||5.82 ||1948µs ||1384µs ||1.41 ||Java ||Switch between Zipper, binary on rest or Galopping. Use Sentinels ||
||df121+km109 ||6297µs ||21583µs ||0.29 ||9715µs ||5328µs ||1.82 ||2444µs ||3466µs ||0.71 ||Java ||Galloping search, skip pointers and Binary search ||
||cs568||11487µs||51787µs||0.22||10457µs||4071µs||2.57||824µs||1884µs||0.44||C++||Galloping and binary search in interval||

Links

Previous Courses

Results for Exercise Sheet 3 (Intersecting Lists)