Differences between revisions 77 and 125 (spanning 48 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.

he41

8957µs

1446µs

6.19

2631µs

1575µs

1.67

8184µs

1465µs

5.59

Java

Combination of zipper algorithm & galloping search; sentinels; Bitwise Operations.

ma269

1332µs

566µs

2.35

122µs

52µs

2.32

1901µs

1538µs

1.24

C++

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

cb382 + mz111

5428µs

1487µs

3.65

1687µs

803µs

2.10

4842µs

2992µs

1.62

Java

Combination of zipper with sentinels & galloping search

yl100

1381µs

483µs

2.86

141µs

66µs

2.14

2061µs

1943µs

1.06

C++

Combination of zipper ,sentinels, and galloping search

fk234

1896µs

466µs

4.07

146µs

91µs

1.60

2127µs

1670µs

1.27

C++

Zipper algorithm with sentinels and galloping search

pk104

1293µs

355µs

3.65

95µs

50µs

1.87

1514µs

1318µs

1.14

C++

galloping search

pg152

12301µs

3078µs

3.99

4777µs

1334µs

3.58

17024µs

11518µs

1.47

Java

Binsearch at beginning, Galloping at end

dd74

1631µs

575µs

2.84

144µs

143µs

1.01

1785µs

1951µs

0.91

C++

Zipper algorithm with sentinels, binary search

je113

1124µs

497µs

2.26

90µs

89µs

1.01

2049µs

1872µs

1.09

Java

Skip pointers with sentinels

ck407

2102µs

1168µs

1.80

1447µs

1098µs

1.32

30959µs

28967µs

1.07

Java

Combination of zipper with sentinels and galloping search.

sm362

1549µs

432µs

3.58

127µs

81µs

1.57

1854µs

1831µs

1.01

C++

Combination of zipper algorithm & galloping search

ak745

6060µs

1026µs

5.91

1893µs

790µs

2.40

6292µs

5245µs

1.20

Java

Combination of Galloping search and binary search.

yb36

1374µs

227µs

6.03

133µs

38µs

3.47

1443µs

1271µs

1.14

C++

Zipper + Galloping search + Binary search + Sentinels

ph193

1249µs

541µs

2.30

81µs

39µs

2.06

1725µs

1589µs

1.09

C++

Combination of galloping search with zipper algorithm; sentinels

sr285

969µs

587µs

1.65

255µs

118µs

2.16

4866µs

1533µs

3.17

Java

Combination of Sentinels, Binary and Galloping

fb234

11562µs

2570µs

4.50

1103µs

535µs

2.06

17199µs

9772µs

1.76

Java

Skip pointers in remainder

hn52

5996µs

4235µs

1.42

6178µs

4319µs

1.43

2990µs

2997µs

1.00

C++

Zipper with sentinels and galloping search

es260 + ic30

1067µs

262µs

4.07

85µs

104µs

0.82

1293µs

5086µs

0.25

C++

Combination of galloping, binary and sentinel

js603

1551µs

350µs

4.43

106µs

92µs

1.15

1385µs

1274µs

1.09

C++

Combination of galloping / binary search and baseline

hs211+lb319

1816µs

591µs

3.07

123µs

66µs

1.86

1911µs

2272µs

0.84

C++

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

rb201

25315µs

9240µs

2.74

10713µs

7272µs

1.47

28211µs

27367µs

1.03

Java

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

ls305

8931µs

7499µs

1.19

4270µs

739µs

5.77

12293µs

7353µs

1.67

Java

Zipper + Sentinels or Galloping

ns202

1421µs

351µs

4.04

103µs

140µs

0.73

1434µs

2380µs

0.60

C++

Galloping

nf55

1149µs

201µs

5.70

68µs

25µs

2.67

1254µs

1068µs

1.17

C++

Combining Zipper, Galloping search and Binary search

fj47

4841µs

831µs

5.82

1948µs

1384µs

1.41

4395µs

6061µs

0.89

Java

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

df121+km109

7352µs

4937µs

1.49

3445µs

2895µs

1.19

7227µs

22216µs

0.33

Java

Galloping search, skip pointers and Binary search

cs568

10457µs

4071µs

2.57

824µs

1884µs

0.44

11487µs

51787µs

0.22

C++

Galloping and binary search in interval

bb245

1066µs

369µs

2.89

150µs

125µs

1.20

1322µs

1862µs

0.71

C++

Galloping search

mk813

1806µs

256µs

7.05

128µs

56µs

2.29

1935µs

2027µs

0.95

C++

Galloping search

ds371

1083µs

260µs

4.23

62µs

31µs

2.00

1217µs

1147µs

1.06

C++

Zipper, Galloping search, Sentinels

ss844

1704µs

349µs

4.88

128µs

93µs

1.37

2100µs

2042µs

1.02

C++

Zipper, Binary Search, Sentinels

br106-ms1512

2274µs

531µs

4.28

159µs

150µs

1.06

2443µs

8665µs

0.28

C++

Galloping search, binary search, sentinels

ht48

3004µs

1979µs

1.52

187µs

113µs

1.65

8388µs

4373µs

1.92

C++

Zipper, sentinels

ds467

18113µs

8663µs

2.09

14441µs

5058µs

2.85

18535µs

19735µs

0.93

Java

Galloping + Binary search

pd95

24618µs

4248µs

5.79

6773µs

3847µs

1.76

22536µs

15037µs

1.49

Java

Galloping + Binary search from remainder

ak721 + bf87

1116µs

302µs

3.70

74µs

99µs

0.75

1376µs

1878µs

0.73

C++

Combination of Zipper with Sentinels and Galloping search with Sentinels

rv25

38843µs

6917µs

5.61

13568µs

5924µs

2.29

37194µs

35132µs

1.06

Java

Combination of Zipper and binary search with remainder plus sentinels

kg190

57987µs

32344µs

1.79

6124µs

4293µs

1.43

37310µs

22280µs

1.67

Java

Combination of zipper algorithm & binary search in longer list; sentinels and skip pointer.

rs325 + ej35

1260µs

470µs

2.68

129µs

108µs

1.49

1956µs

1471µs

1.33

C++

Galloping and Binary

mb930 + ng153

1184µs

461µs

2.57

107µs

90µs

1.19

1326µs

1260µs

1.05

C++

Zipper, Galloping search, Sentinels

mg290

8943µs

7624µs

1.17

3628µs

3130µs

1.16

4657µs

4427µs

1.05

Java

Combination of zipper algorithm with sentinels & Galloping

pj46

1903µs

436µs

4.36

101µs

57µs

1.76

2748µs

2082µs

1.34

C++

Galloping & binary search + sentinels

mf401

2012µs

504µs

3.99

236µs

138µs

1.71

2500µs

1574µs

1.59

C++

Galloping + Zipper with sentinels

jh442

3242µs

264µs

12.28

178µs

49µs

3.63

3186µs

2596µs

1.23

C++

Skip Pointers for list A, Zipper + Galloping for list B, Sentinels

sn144

534µs

360µs

1.48

135µs

1.00

367µs

519µs

0.7

Java

Binary search in remaining ,Galloping,Sentinels

my28 + ab717

58394µs

348878µs

1.67

10117µs

9901µs

1.02

39431µs

90009µs

0.43

Java

Binary search in remaining, Binary search in remaining ,Galloping

ye14

13218.2μs

5620.8μs

2.35

3759.6μs

2465.2μs

1.52

11873.0μs

16458.0μs

0.72

Java

Galloping search, sentinel, binary search

vb128

14198μs

2754μs

5.15

6008μs

754μs

7.98

14887μs

8958μs

1.66

Java

Zipper + Galloping with Binary search in range of gallop and last + sentinel.

fc54

8815μs

1340μs

6.58

1475μs

1912μs

0.77

13724μs

11116μs

1.23

Java

Galloping search, sentinel, binary search

ms1323

5838μs

1809μs

3.23

440μs

413μs

1.07

1875μs

2689μs

0.70

c++

Combination of zipper with sentinel and Galloping search.

ch285

44375μs

7303μs

6.08

10964μs

6841μs

1.60

32075μs

21204μs

1.51

Java

Combination of Zipper+Sentinel+Binary Search in Remainder of longer list

uw18

18979μs

3812μs

4.98

8497μs

2459μs

3.46

21383μs

12295μs

1.74

Java

Zipper + Sentinels + Galloping Search

dk182

43156μs

13012μs

3.31

11096μs

10486μs

1.05

18792μs

6931μs

2.71

Java

Combination of zipper with sentinels & galloping search & binary search.

pc49

3525μs

722μs

4.88

207μs

94μs

2.23

5063μs

4590μs

1.10

C++

Galloping search & sentinels & binary search.

jt20

1224µs

418µs

2.93

66µs

57µs

1.16

2157µs

1429µs

0.66

C++

Galloping search, sentinels, binary search, misc optimizations.

cf147

682µs

408µs

1.67

120µs

110µs

1.09

1201µs

2086µs

0.58

C++

Galloping search + binary search + Sentinels

sa194 + lf189

38165µs

5906µs

6.46

6599µs

3648µs

1.81

30105µs

51320µs

0.59

Java

Galloping + Binary search in Remainder

cg248 + ar288

5858µs

3593µs

1.63

6139µs

2518µs

2.44

4606µs

4021µs

1.15

Java

Zipper with sentinels (+ galloping search + binary search + shrinking search range)

mu38

21664µs

3119µs

6.95

8234µs

2915µs

2.82

19449µs

18171µs

1.07

Java

Binary search

fe73

6872µs

5684µs

1.21

93µs

74µs

1.26

2535µs

2337µs

1.08

Java

Zipper with sentinels, logical simplification

jh363 + os85

1724µs

681 µs

2.53

141µs

139µs

1.01

1831µs

3369µs

0.54

C++

Galloping search

dr189-jb729

6378µs

2381µs

2.68

57µs

871µs

0.065

1975µs

10617µs

0.19

Java

Zipper with binary search, galloping search & SkipPointers

dz31 + lk202

1610µs

1371µs

1.17

114µs

100µs

1.14

1843µs

3839µs

0.48

C++

Skip pointer + sentinels

nh189

54615µs

20918µs

2.61

25062µs

46982μs

0.53

55479μs

46481μs

1.19

Java

Galloping

-  ⇤ ← Revision 77 as of 2017-11-13 19:59:11 → 
  Size: 6607
  Editor: pD9E15293
  Comment:
+   ← Revision 125 as of 2017-11-14 13:19:22 → ⇥
  Size: 10834
  Editor: adpult
  Comment:
-Deletions are marked like this.
+Additions are marked like this.
 Line 1:
-#acl All:read,write
+#acl All:read
 Line 5:
-{{{#!html
<span style="color:red; font-weight: bold">When you add your row after November 13, 5:30pm, please note that the order of columns has changed.</a>
}}}
|| ||||||<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;"> ||
+|| |||||| ''film + rug'' |||||| ''bowling + rug'' |||||| ''film + bowling'' |||||| ||
-Line 36:
+Line 33:
-||fj47 ||4841µs ||831µs ||5.82 ||1948µs ||1384µs ||1.41 ||4395µs ||6061µs ||0.89 ||Java ||Switch between Zipper, binary on rest or Galopping. Use Sentinels ||
+||fj47 ||4841µs ||831µs ||5.82 ||1948µs ||1384µs ||1.41 ||4395µs ||6061µs ||0.89 ||Java ||Switch between Zipper, binary on rest or Galloping. Use Sentinels ||
-Line 41:
+Line 38:
+||ds371 ||1083µs ||260µs ||4.23 ||62µs ||31µs ||2.00 ||1217µs ||1147µs ||1.06 ||C++ ||Zipper, Galloping search, Sentinels ||
||ss844 ||1704µs ||349µs ||4.88 ||128µs ||93µs ||1.37 ||2100µs ||2042µs ||1.02 ||C++ ||Zipper, Binary Search, Sentinels ||
-Line 46:
+Line 45:
+||rv25 ||38843µs ||6917µs ||5.61 ||13568µs ||5924µs ||2.29 ||37194µs ||35132µs ||1.06 ||Java ||Combination of Zipper and binary search with remainder plus sentinels ||
||kg190 ||57987µs ||32344µs ||1.79 ||6124µs ||4293µs ||1.43 ||37310µs ||22280µs ||1.67 ||Java ||Combination of zipper algorithm & binary search in longer list; sentinels and skip pointer. ||
||rs325 + ej35 ||1260µs ||470µs ||2.68 ||129µs ||108µs ||1.49 ||1956µs ||1471µs ||1.33 ||C++ ||Galloping and Binary ||
||mb930 + ng153 ||1184µs ||461µs ||2.57 ||107µs ||90µs ||1.19 ||1326µs ||1260µs ||1.05 ||C++ ||Zipper, Galloping search, Sentinels ||
||mg290 ||8943µs ||7624µs ||1.17 ||3628µs ||3130µs ||1.16 ||4657µs ||4427µs ||1.05 ||Java ||Combination of zipper algorithm with sentinels & Galloping ||
||pj46 ||1903µs ||436µs ||4.36 ||101µs ||57µs ||1.76 ||2748µs ||2082µs ||1.34 ||C++ ||Galloping & binary search + sentinels ||
||mf401 ||2012µs ||504µs ||3.99 ||236µs ||138µs ||1.71 ||2500µs ||1574µs ||1.59 ||C++ ||Galloping + Zipper with sentinels ||
||jh442 ||3242µs ||264µs ||12.28 ||178µs ||49µs ||3.63 ||3186µs ||2596µs ||1.23 ||C++ ||Skip Pointers for list A, Zipper + Galloping for list B, Sentinels ||
||sn144 ||534µs ||360µs ||1.48 ||135µs ||135µs ||1.00 ||367µs ||519µs ||0.7 ||Java ||Binary search in remaining ,Galloping,Sentinels ||
||my28 + ab717 ||58394µs ||348878µs ||1.67 ||10117µs ||9901µs ||1.02 ||39431µs ||90009µs ||0.43 ||Java ||Binary search in remaining, Binary search in remaining ,Galloping ||
||ye14 ||13218.2μs ||5620.8μs ||2.35 ||3759.6μs ||2465.2μs ||1.52 ||11873.0μs ||16458.0μs ||0.72 ||Java ||Galloping search, sentinel, binary search ||
||vb128 ||14198μs ||2754μs ||5.15 ||6008μs ||754μs ||7.98 ||14887μs ||8958μs ||1.66 ||Java ||Zipper + Galloping with Binary search in range of gallop and last + sentinel. ||
||fc54 ||8815μs ||1340μs ||6.58 ||1475μs ||1912μs ||0.77 ||13724μs ||11116μs ||1.23 ||Java ||Galloping search, sentinel, binary search ||
||ms1323 ||5838μs ||1809μs ||3.23 ||440μs ||413μs ||1.07 ||1875μs ||2689μs ||0.70 ||c++ ||Combination of zipper with sentinel and Galloping search. ||
||ch285 ||44375μs ||7303μs ||6.08 ||10964μs ||6841μs ||1.60 ||32075μs ||21204μs ||1.51 ||Java ||Combination of Zipper+Sentinel+Binary Search in Remainder of longer list ||
||uw18 ||18979μs ||3812μs ||4.98 ||8497μs ||2459μs ||3.46 ||21383μs ||12295μs ||1.74 ||Java ||Zipper + Sentinels + Galloping Search ||
||dk182 ||43156μs ||13012μs ||3.31 ||11096μs ||10486μs ||1.05 ||18792μs ||6931μs ||2.71 ||Java ||Combination of zipper with sentinels & galloping search & binary search. ||
||pc49 ||3525μs ||722μs ||4.88 ||207μs ||94μs ||2.23 ||5063μs ||4590μs ||1.10 ||C++ ||Galloping search & sentinels & binary search. ||
||jt20 ||1224µs ||418µs ||2.93 ||66µs ||57µs ||1.16 ||2157µs ||1429µs ||0.66 ||C++ ||Galloping search, sentinels, binary search, misc optimizations. ||
||cf147 ||682µs ||408µs ||1.67 ||120µs ||110µs ||1.09 ||1201µs ||2086µs ||0.58 ||C++ ||Galloping search + binary search + Sentinels ||
||sa194 + lf189 ||38165µs ||5906µs ||6.46 ||6599µs ||3648µs ||1.81 ||30105µs ||51320µs ||0.59 ||Java ||Galloping + Binary search in Remainder ||
||cg248 + ar288 ||5858µs ||3593µs ||1.63 ||6139µs ||2518µs ||2.44 ||4606µs ||4021µs ||1.15 ||Java ||Zipper with sentinels (+ galloping search + binary search +  shrinking search range) ||
||mu38 ||21664µs ||3119µs ||6.95 ||8234µs ||2915µs ||2.82 ||19449µs ||18171µs ||1.07 ||Java ||Binary search ||
||fe73 ||6872µs ||5684µs ||1.21 ||93µs ||74µs ||1.26 ||2535µs ||2337µs ||1.08 ||Java ||Zipper with sentinels, logical simplification ||
||jh363 + os85 ||1724µs ||681 µs ||2.53 ||141µs ||139µs ||1.01 ||1831µs ||3369µs ||0.54 ||C++ ||Galloping search ||
||dr189-jb729 ||6378µs ||2381µs ||2.68 ||57µs ||871µs ||0.065 ||1975µs ||10617µs ||0.19 ||Java ||Zipper with binary search, galloping search & SkipPointers ||
||dz31 + lk202 ||1610µs ||1371µs ||1.17 ||114µs ||100µs ||1.14 ||1843µs ||3839µs ||0.48 ||C++ ||Skip pointer + sentinels ||
||nh189 ||54615µs ||20918µs ||2.61 ||25062µs ||46982μs ||0.53 ||55479μs ||46481μs ||1.19 ||Java ||Galloping ||

Links

Previous Courses

Results for Exercise Sheet 3 (Intersecting Lists)