AD Teaching Wiki:

Results for Exercise Sheet 3 (Intersect)

Add your row to the table below, following the examples already there. Please write down the time in microseconds as an integer, and the ratios as floats with exactly two digits of precision. In the first column, write your first name, or name1+name2 if you work in a group. Speedup is always measured as time_for_baseline / time_for_your_version (<1 = slower, >1 faster). In the last column briefly describe the improvements you implemented.

As mentioned in the lecture, repeat each measurement 5 times and take the average!

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 (baseline 1455µs)

184/118=1.56

1213/745=1.63

2968/2433=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)


/!\ Edit conflict - other version:


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


/!\ Edit conflict - your version:


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

pb138

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


/!\ End of edit conflict


AD Teaching Wiki: InformationRetrievalWS1617/ResultsES3 (last edited 2016-11-14 11:58:02 by HSI-KBW-46-223-1-96)