Differences between revisions 15 and 119 (spanning 104 versions)

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 (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 klog(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.

-  ⇤ ← Revision 15 as of 2016-11-13 11:38:25 → 
  Size: 2365
  Editor: p54985927
  Comment:
+   ← Revision 119 as of 2016-11-15 14:01:50 → ⇥
  Size: 12804
  Editor: HSI-KBW-046-005-176-024
  Comment:
-Deletions are marked like this.
+Additions are marked like this.
 Line 4:
 Speedup is always measured as time_for_baseline / time_for_your_version  (<1 = slower, >1 faster).
 Line 11:
-||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||
+||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||
 Line 16:
-||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 (skipping 32 elements) ||
+||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. ||