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µs

0,64

1,44

0,77

C++

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

Binary search and zipper with sentinals

ab766

7480µs

1.62

4.48

1.53

Java

Intel® Core™ i5-5200U CPU @ 2.20GHz × 4 16GB RAM

if shorter list 25 times shorter than longer list: Binary search. else: zipper; sentinels; native arrays

ch160

2669µs

1.06

0.85

0.40

Java

Intel® Core2 Duo @ 2.40GHz x 4

Binary Search if length diff big otherwise zipper, non algorithmic optim

ma277

5575µs

3.21

2.18

1.83

Java

Intel® Core™ i5-6200 CPU @ 2.30GHz - 12GB RAM

Galloping search if one list 50 times larger than other, else zipper with sentinels. Multi non algorithmic improvements

jl387

9928µs

1.97

2.0

1.98

Java

Intel® Core™ i5-3230M CPU @ 2.60GHz x 4

Binary Search with Native Arrays and Sentinels

an145-jc142

9423µs (BL: 14941)

0.71

4.36

0.70

Java

Intel® Core™ i5 @ 2.3GHz - 8GB RAM

If |listA| < 10%|listB|, do Binary Search. Else, do SkipPointer with linear search.

lm283

7109µs (BL: 9408µs)

1.10

 1.97

1.15

Java

Intel Core i7-3615QM CPU @ 2.3 Ghz - 8GB RAM

 Native arrays, special binary search (optimized for intersect) if list sizes differ a lot, slightly improved zipper otherwise.

co41-jr76

16052µs

3.52

 1.02

0.56

Java

Intel Core i5-5200U CPU @ 2.2 Ghz - 8GB RAM

 SkipPointer for Zipper for small lists, Galloping Search for large lists

jk59

7006µs

1.24

8.44

1.45

Java

Intel Core i5-2430M CPU @ 2.40GHz × 4 - 4GB RAM

Native arrays and sentinels. IF one of the arrays is 100 times bigger THEN zipper algorithm with galloping search and binary search in the bigger array ELSE standard zipper algorithm.

fe66

9364µs

0.86

1.45

1.72

Java

Intel i5 @ 2.70 GHz - 16 GB RAM

Native datatypes, Sentinels, Stepper which steps 50 steps once lists differ by factor 100.

dn47

6284µs

1.33

0.69

0.54

C++

Intel(R) Core(TM) i7-6700 CPU @ 3.40GHz

binarySearch if one list is 200 times the size of the other zipper else

sa215

1174 µs

1.72

1.05

1.03

Java

Intel® Core™ i7 CPU Q 740 @ 1.73GHz × 8 - 4GB RAM

galloping search if size diff ratio > 100, otherwise binary search. Used Java native arrays.

nz21

2548µs

1.05

2.45

1.16

C++

AMD A6-6310 @ 1.8-2.4 GHz

recursive binary search if bigger list 40 times bigger, otherwise zipper with sentinels, always intersect smaller with bigger list.

lg254

2195 µs (BL: 3179 µs)

1.31

1.71

1.30

Java

Intel i7-3610QM @ 2.30 GHz, 8GB RAM

Sentinels + Native Arrays, Galopping Search if input length ratio < 1 %

bg117 + me192

12126 µS

2.59

3.87

1.08

Java

Intel(R) Core(TM) i3-5005U CPU @ 2.00GHz - 4GB RAM

smaller list length (binary search) otherwise galloping; built in binary search function used;smaller list considered as first list

ak346

1338µs

1.03

1.14

0.93

C++

Intel i7-4558U @ 2.80GH - 16 GB RAM

zipper with sentinels

re55

5.479µs (BL: 6.869µs)

1.29

1.12

1.58

Java

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

Galloping search (with remainder) if one list > 20 times bigger than the other one, else simple zipper.

kb285

1380 µs (bl: 2257 µs)

1.26

2.36

1.47

Intel i5-3317U @ 1.70GHz × 4 4GB RAM

C++

if list sizes differ a lot, do galloping search, else use zipper method with non-algorithmic improvements

si52

19370 µs

0.25

8.36

0.85

Java

Intel i5-5300 @ 2.30GHz × 4 2 GB RAM (Virtual Box with one processor)

galloping search

yr18

17556µs

1.09

0.35

0.04

Java

Intel i7-4770 @ 3.40GHz - 6 GB RAM

Binary search for length > 10000 else zipper algorithm. Use of native arrays.

gs121

4893µs (BL:6401µs)

1.06

6.34

4.74

Java

Intel i5-4200M @2.5GHz - 8 GB

Native arrays, binary search, various non algorithmic improvements

tm130

1572µs

0.92

1.80

1.07

C++

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

Binary search (with remainder) if listsize ratio > 35 else zipper, smaller list = first list

do43

5000µs (BL:5950µs)

0.97

2.93

0.96

C++

Intel i7-2630QM @2.0GHz - 16 GB

galloping search, zipper

dr189

2204µs (bl: 8347µs)

1.29

6.68

3.42

Java

Intel(R) Core(TM) i7-4770HQ CPU @ 2.20GHz 16GB RAM

binary & galopping search depending on length difference, native arrays, sentinels

fb289

7500µs

Java

Intel(R) Core(TM) i7-3517U CPU @ 1.90GHz 10GB RAM

binary search with int arrays

as885+tm165

1197µs (bl 1429µs)

1.02

1.85

1.04

C++

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

galopping (smaller list first in) + zipp with sentinals

dv33

1718µs (BL:2139µs)

1.00

2.45

1.00

C++

Intel i5-M 480 @ 2.67GHz × 4 - 8 GB RAM

galloping + binary search for listA.size < listB.size / 50, else zipper

mk847

5523µ

2.42

2.56

2.32

Java

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

native arrays and sentinel and if list is smaller than 100 times binary search

pj23

990µs (baseline 1485)

1.4

6.28

1.14

C++

Intel(R) Core(TM) i5-4288U CPU @ 2.60GHz - 16 GB RAM

Binary search, pred. branches

ia42

6578µs

2.15

9.18

0.68

Java

Intel Core i5 @2.5 GHz 6.00 GB Ram

Efficient Binary search + Native arrays

dv33

1718µs (BL:2139µs)

1.00

2.45

1.00

C++

Intel i5-M 480 @ 2.67GHz × 4 - 8 GB RAM

galloping + binary search for listA.size < listB.size / 50, else zipper

jr187

15407µs

0.76

0.10

0.08

C++

Intel i5-4200U @ 1.6GHz, 8 GB RAM, VirtualBox

sentinel zipper + binary search with branching for size < 100000

hs138

990µs (baseline 1265µs)

1.3

2.6

1.03

C++

Intel® Core™ i7-5820K Processor (15M Cache) @ 3.60GHz, 16GB RAM

galloping search, if one list is at least a factor of 250 bigger than the other, and the baseline zipper search otherwise. Various non-algorithmic optimizations.