Results for Exercise Sheet 3 (Intersect)
Add your row to the table below, following the examples already there. Please write down the time in milliseconds 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.
Name |
Average time |
film + 2015 |
film + comedy |
2015 + comedy |
Language |
Machine Spec |
Implementation Summary |
Björn |
27ms |
1.00 |
1.00 |
1.00 |
C++ |
Intel Xeon X5560 @ 2.80GHz - 36GB RAM |
Baseline |
David |
143ms |
1.34 |
8.10 |
1.55 |
Java |
Intel Core i7-2600K @ 3.40GHz - 16 GB RAM |
Gallop-Search(with BS), reduced if-branches |
Heinz |
16 days |
1.36 |
10.09 |
1.61 |
BASIC |
Commodore 64 MOS 6510 @ 1.02 MHz - 64 KB RAM |
Galloping search + shorter list first |
Marco |
31ms |
2.40 |
2.90 |
1.16 |
Java |
Intel Core i5 @ 2.6 GHz - 8GB RAM |
Sentinel, native Arrays, iterate shorter list, gallop search + reuse last found index |
Matteo |
301ms |
12.5 |
9.16 |
4.50 |
Java |
Intel i7 @ 1.80GHz - 8GB RAM |
native arrays, skip pointers, short list first |
Stefan |
? |
1.45 |
3.47 |
1.05 |
C++ |
Virtual box, AMD A10-5750M @ 2.5GHz- 4GB RAM |
use pointers, use gallop+binary-Search |
David |
263ms |
1,30 |
1,17 |
1,20 |
Java |
Intel i7 @ 2,8 GHz - 10GB RAM |
native arrays, galloping, reduced if branches |
Alex |
181ms |
13.00 |
3.54 |
1.50 |
Java |
Virtual machine with 4GB RAM |
Combination of Galloping-Search with binary Search, native arrays |
Kecen |
68ms |
4.66 |
0.87 |
1.48 |
C++ |
Intel i5 1.6GHz - 8GB RAM |
Gallop search, skip pointer, shorter list first and reduced if statement |
Sven |
157ms |
3.64 |
2.95 |
6.20 |
Java |
Intel Core i5-3317U CPU @ 1.70GHz - 8GB RAM |
Skip pointer + BS or Galloping + BS |
Zhang |
15.88ms |
6.85 |
0.83 |
2.04 |
C++ |
Intel Core i7 @ 2.6 GHz - 16GB RAM |
Skip pointers + Galloping + reduced if branches |
DavidS |
19ms |
3.46 |
1.00 |
1.39 |
C++ |
Intel Core i5 @ 2.2 GHz - 8GB RAM |
Galloping + reduced if in BS for not eq. size lists |
34ms |
5.82 |
1.07 |
1.31 |
Java |
Intel Core i5 @ 1.7 GHz - 8GB RAM |
Skip Pointers + Native Arrays + Short List First |
|
Numair+Evgeny |
69ms |
1.18 |
1.57 |
1.33 |
Java |
Intel Core i5 @ 3.50 GHz - 16 GB RAM |
Skip Pointers + Short List First + Binary Search |
Jan |
245ms |
2.84 |
2.09 |
1.18 |
Java |
Intel Core i7 @ 2.0 GHz - 8 GB RAM |
Galloping + Binary Search + sentinels + short list first |
Sam Pling |
141ms |
1.75 |
0.62 |
1.06 |
Java |
Intel Core i5-2520M @ 2.5 GHz - 8 GB RAM |
Binary search starting at the remainder of the larger list |
Robin |
97ms |
3.98 |
0.95 |
1.22 |
C++ |
Intel Core i7 @ 2.0 GHz - 16 GB RAM |
Galloping + Binary Search + Sentinel + short list first |
Raghu |
173ms |
10.66 |
1.07 |
3.71 |
C++ |
AMD A6 @ 1.80 GHz - 4GB RAM |
Galloping search (exp. + binary) + searching remainder of the list + shortest list first |
Matthias |
63ms |
4.60 |
0.89 |
2.65 |
C++ |
Core i7-2600K @ 3.40GHz - 32GB RAM |
Galloping search + reduced branching + shorter list first |
MS-DOS Manfred |
- |
5.84 |
0.16 |
1.13 |
C++ |
MS-DOS on ARM64 @ 3.40 GHz - 32 GB RAM |
Galloping search + shorter list first |
IE |
150ms |
1.85 |
0.84 |
2.00 |
Java |
2.4 GHz i5 16 GB RAM |
Galloping search + shorter list first |
Matia |
37ms |
10.45 |
2.76 |
0.96 |
Java |
2.6 GHz i5 8 GB RAM |
Galloping w/ a static index + sentinel + short list first + native arrays |
Philip |
28.4 ms |
2.53 |
1.06 |
1.76 |
Java |
i5-4590 @ 3.3GHz - 32 GB RAM |
Native Arrays, Shorter List First, Sentinels, Reduced branches |
Daniel |
35.9 ms |
2.37 |
1.00 |
1.02 |
C++ |
Intel Pentium T4500 @ 2.3 GHz - 4 GB RAM |
Reduced if-branches, Sentinels, galloping search |
Patrick |
20 ms |
3.21 |
1.04 |
1.75 |
C++ |
Intel Core i5-3570K @ 3.4 GHz - 8 GB RAM |
Reduced Branches, Sentinels, Galloping search, reuse last index |
Frank |
80.4 ms |
1.68 |
0.32 |
0.68 |
C++ |
Virtual machine - 4 GB RAM |
Sentinels, Galloping search, reuse last index, small list first |
Homer Sexual |
57.4 ms |
2.44 |
1.32 |
0.68 |
C++ |
Virtual machine - 2 GB RAM |
Galloping search, reuse last index, small list first |
Dan |
70.3 ms |
1.13 |
2.84 |
1.0 |
Java |
Intel Core Q8300 @ 2,5 GHz - 4 GB RAM |
Sentinel + Binary Search + reduced if + Native Arrays |
Fabio |
178ms |
1,17 |
1,73 |
1,17 |
Java |
2,5 GHz Intel Core i5 |
binary search on biggest array |
Elias&Maximilian |
159ms |
8.58 |
0.82 |
2.30 |
C++ |
2,5 GHz Intel Core i5 |
Gallping + Binary Search + Skiplists (offset 100) on the larger array |
Rezart |
134ms |
1,51 |
9,84 |
0,99 |
C++ |
2,5 GHz Intel Core i5 |
Galloping on biggest array |