Results for Exercise Sheet 3 (Intersecting Lists)

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.