Results for Exercise Sheet 3 (Intersect)

Name

Average time

existence + bielefeld

them + bielefeld

them + existence

Language

Machine Spec

Implementation Summary

Patrick

1698µs

1.00

1.00

1.00

C++

Intel i5-3320M @ 2.60GH - 8 GB RAM

None (Baseline)

dk295

1099µs (bl 1455µs)

1.56

1.63

1.22

C++

Intel Core i7-5600U CPU @ 2.60GHz - 12 GB RAM

bin search for big list len diff, zipper else. mult non-algorithmic optim

jk544

1993µs

1.65

2.31

1.32

C++

Intel Core i3-5005U CPU @ 2.00GHz - 4GB RAM

Galloping search for big len diff, simple skipping of 30 elements for medium diff, non-alg improved zipper for small len diff

km151

8230µs

1.64

1.46

17.22

Java

Intel® Core™ i5-2410M CPU @ 2.30GHz × 4 - 6GB RAM

Binary search kwith predictable branches if just one of the Lists < 10000 else zipper, non-alg improved zipper with Sentinels, predictable branches, native arrays

kh143

2004µs

1.09

7.94

3.79

Java

AMD Phenom II X4 955 @ 3.20GHz - 12 GB RAM

galloping search for lists with length1 < 10000 and length2 > 100000, baseline for lists both < 200000, else zipper with sentinels and native int array

ts341

6187µs

1.65

4.07

2.34

Java

Intel Core i5-4210U CPU @ 1.70GHz × 4 - 8GB RAM

Binary search if list length difference factor > 100, else zipper; sentinels; predictable branches; native arrays.

mf233

1762µs

1.46

1.88

1.13

C++

Intel Celeron CPU G1610 @ 2.6GHz - 4GB RAM

For short list differences --> improved zipper. For long differences --> combination of binary search and linear search (always skipping 32 elements)

ff115

1876µs

1.65

0.84

1.11

C++

Intel® Core™ i5-3337U CPU @ 1.80GHz × 4 - 4GB RAM

Galloping search if list length difference factor > 50, else zipper with sentinels

ms801

1356µs

1.26

1.91

1.23

C++

Intel® Core™ i5-3210M CPU @ 2.50GHz × 2 - 8GB RAM

Zipper with sentinels for medium list difference, else binary search

jb657

6667µs

1.00

1.00

5.50

C++

Intel® Core™ i5-2520M CPU @ 2.50GHz × 2 - 4GB RAM

if shorter list 100 times shorter than longer list: Galloping search. else: zipper

bt45

1756µs

2.53

1.46

1.34

Java

Intel i7-2620M @ 2.7GHz - 8 GB RAM

if length-ratio < 15 use skipper, else binary with remainders

sh477

1720µs

1.02

4.52

2.43

Java

Intel Core i7-6700K CPU @ 4.00GHz - 16 GB RAM

binary search if difference of list lengths bigger than factor 20, else zipper with sentinels, less if and native arrays

jg292

1220µs(BL: 1547)

1.19

2.12

1.08

C++

Intel(R)Core(TM) i5-4200M CPU @ 2.50GHz 12 GB RAM

Sentinel, pred. branches, use skipper of 60 elements if length ratio >4

ss515

926µs(BL: 1138)

1,03

2,57

1,00

C++

Intel(R) Core(TM) i5-4590 CPU @ 3.30GHz 16 GB RAM

pred. branches, galloping search with shorter list, switch method depending of length difference (factor 50)

pb138

5444µs

1.41

2.52

1.15

Java

Intel® Core™ i7-3632QM CPU @ 2.20GHz - 4GB RAM

native arrays, sentinels, if length dif factor 100 bin search, else zipper

lm310

1044µS

0.97

2.58

2.09

C++

Intel® Core™ i7-4770 CPU @ 3.40GHz - 24GB RAM

Use binary search for length differences with factor > 100, else zipper; some compiler flags; zipper is a bit faster with clang, but binary search is much slower than with gcc

dt36

14008µS

1.02

3.73

1.36

Java

Intel® Core™ i5-2410M CPU @ 2.30GHz × 4 - 6GB RAM

Galloping for length diff ratio < 1%, else zipper; linked list instead of arraylist (resulting list)

cz4

6077µs

1.10

1.24

1.90

Java

Intel® Core™ i7-4770 CPU @ 3.40GHz × 8 - 6GB RAM

Binary: one list much longer, Galloping: (almost) same length, Zipper: else; no use of ArrayList, only native int arrays

hr55-pg74

2208µS (Baseline: 4044 µS)

1.44

1.2

1.4

Java

Intel® Core™ i7-4700MQ CPU @ 2.4GHz - 12GB RAM

Native Arrays, Sentinels , if List1 > 1000000 && List2 < 1000 use Skippointer, Zipper else

sh590

7473µS (Baseline: 11746µS)

1.10

1.61

6.36

Java

Intel® Core™ i5-5200U CPU @ 2.20GHz - 8GB RAM

If length difference (factor 50) then Galloping : else;Zipper with Native Array and Sentinels

la109 + os90

1329µS

1.5

1.73

2.1

Java

Intel(R) Core(TM) i7-3770 CPU @ 3.40GHz - 8GB RAM

If length difference (factor 50) then Galloping : else;Zipper with Native Array and Sentinels

jw355

2633µs

1.44

2.46

1.06

Java

Intel® Core™ i7-4790K CPU @ 4GHz - 16GB RAM

Binary Search if length difference > 10000, else zipper, with native arrays and predictable branches

dw118

1112µs

1.05

2.08

1.05

C++

Intel® Core™ i7-2700K CPU @ 3.50GHz - 32GB RAM

Galloping search if one list > 100 times bigger

hm101

1319 µs

1.55

2.45

1.8

Java

Intel(R) Core(TM) i5-4210M CPU @ 2.6GHz - 8GB RAM

If length difference (factor 50) then Galloping : else;Zipper with Native Array;

ep90-je177

1303.67

0.96

0.98

0.92

C++

Intel® Core™ i7-3770 CPU @ 3.40GHz - 16GB RAM

Zipper with sentinel optimization seems to be the fastest approach always for us.

eb162

8288.8 (BL:17526.2)

0.26

3.71

1.77

Java

Intel Core i5-5287U @ 2.9 GHz - 8 GB RAM

Binary search if one list > 100 times bigger than the other, else zipper with sentinel. Both with native array.

or17

1399 (BL:1843)

1,03

1,51

1.27

C++

Intel® Core™ i5-4210U CPU @ 1.70GHz × 4

Galloping search and zipper with sentinals

db278-om46

11274 µs

0.80

3.42

1.47

Java

Intel® Core™ i5-3317U CPU @ 1.70GHz × 4

Zipper or Galloping search if k*log(n)*1,2 < n where n is the size of the longer list and k the size of the shorter list. Both algorithms use sentinels and native arrays.

aw281

3900

0,64

1,44

0,77

C++

Intel® Core™ M-5Y51 CPU @ 1.10GHz

Binary search and zipper with sentinals