#acl All:read,write
= Results for Exercise Sheet 3 (Intersect) =
Add your row to the table below, following the examples already there. Please write down the time in '''micro'''seconds 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 (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. ||