|
Size: 2568
Comment:
|
Size: 3102
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 18: | Line 18: |
| ||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 || |
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 |