Differences between revisions 29 and 66 (spanning 37 versions)

Results for Exercise Sheet 3 (List Intersection)

Please read the instructions below, before adding something to the table!

1. Add your row to the table below, following the examples already there. Simple = the simple linear-time algorithm. Gallop = the asymptotically optimal galloping-search algorithm. The number in parantheses after the query is the ratio between the two list length, rounded to the next integer.

2. Provide the query times in microseconds (µs), and round them to the next integer.

3. Provide the programming language and the specs of the machine you used in the same way as the examples already there. In particular, specify the processor frequency with exactly one digit after the dot, the amount of RAM as an integer, and don't provide secondary details about the processor.

Name	university german (2:1)		university berlin (13:1)		university freiburg (198:1)		Processor / RAM	Language
Name	simple	gallop	simple	gallop	simple	gallop	Processor / RAM	Language
Björn	430µs	530µs	134µs	146µs	72µs	21µs	Intel X5560 @ 2.8GHz / 36GB	C++
MartinM	1505µs	1711µs	308µs	318µs	260µs	29µs	Intel i7-3770K @ 3.5GHz / 8GB	Java
DanielL	2071µs	1454µs	595µs	140µs	392µs	44µs	Intel i7-2600 @ 3.4GHz / 16GB	Java
AlexM	6142µs	5751µs	656µs	943µs	416µs	132µs	Intel Core 2 Duo @ 2.0Ghz / 4GB	Java
Oier	4434µs	5948µs	696µs	868µs	1203µs	524µs	Intel Core i5 M 450 @ 2.40GHz / 4GB	Java
Manuel	391µs	568µs	79µs	136µs	30µs	14µs	Intel E3-1230v3 @ 3.7GHz / 2GB (VM)	C++
Sven	1218µs	1833µs	598µs	951µs	494µs	467µs	Intel i7-4650U @ 1.70GHz / 4GB	Java
Janosch	433µs	644µs	183µs	198µs	97µs	60µs	Intel i7-3520M @ 2.9GHz / 8GB	C++
Daniel	381µs	473µs	115µs	141µs	61µs	21µs	Intel i7-920 @ 3.2GHz / 2GB (VM)	C++
Bastian	305µs	461 µs	74µs	144µs	37µs	49µs	Intel i5-3570K @ 3.4GHz / 8GB	C++
Iradj	1171µs	4658 µs	493µs	1715µs	318µs	505µs	Intel i3-2100K @ 2.1GHz / 2GB	C++
Nghia	5295µs	18031µs	2532µs	12679µs	2656µs	10209µs	Intel i7-2630QM @ 2.0GHz / 8GB	Java
Jens	423µs	1103µs	169µs	314µs	120µs	96µs	Intel i7-3770 @ 3.40GHz / 8GB	C++
Yu-Wen	11145µs	15639µs	8499µs	5736µs	5759µs	4092µs	Intel Core i3 M330 @ 2.13GHz / 2GB	Java
Lijun	2310µs	4968µs	1471µs	2855µs	1351µs	582µs	Intel Core2 Quad @ 2.40GHz / 4GB	Java
Igor	2814µs	2047µs	160µs	213µs	73µs	50µs	Intel i7-3630QM @ 2.4GHz / 12GB	Java
Rafael	862 µs	1038 µs	295 µs	270 µs	165 µs	27 µs	Intel i5-3317U @ 1.7 GHz / 4 GB	C++
José	12450 µs	117315µs	3136 µs	16375µs	570 µs	1457 µs	Intel core i5 @ 2.4GHz / 8 GB	Java
MartinK	5516 µs	4034µs	9975µs	4013µs	2641µs	2327µs	Intel Core 2 Duo @ 2.0Ghz / 3GB	Java
Wera	505µs	666µs	114µs	173µs	52µs	28µs	Intel i5-2450M @ 2.5Ghz / 8GB	C++
Ina	326µs	393µs	78µs	106µs	37µs	9µs	Intel i7-3770 @ 3.4GHz / 16GB	C++
Björn H	1144us	20255us	497us	1342us	383us	129us	AMD E-450 APU @ 1.6GHz / 1.6GB	C++
Julien	1367µs	1888µs	715µs	1024µs	634µs	207µs	Intel Core i5-2500k @ 3.3GHz / 8GB	Java
Simon W	571µs	1915µs	168µs	379µs	84µs	47µs	Intel Core i5 M 430 @ 2.27GHz / 4GB	C++
A&J	4370µs	4858µs	362µs	846µs	187µs	198µs	Intel i7-3610QM @ 2.3GHz / 32GB	Java
Rick	666µs	2300µs	228µs	181µs	79µs	81µs	Intel Core i5 M 460 @ 2.5GHz / 2GB	C++
LukasG	331µs	2159µs	96µs	355µs	76µs	29µs	Intel Core i7-2620M @ 2.7GHz / 8GB	C++
Mateusz	3090µs	8988µs	378µs	1189µs	134µs	42µs	Intel Core i5-2520M @ 2.5GHz / 4GB	Java
Anastasia	795µs	1753µs	329µs	876µs	254µs	591µs	Intel Core i5 M 560 @ 2.67GHz × 4 / 8GB	C++
Diego	835µs	1341µs	302µs	412µs	201µs	63µs	Intel Core 2 Duo T5450 @ 1.7GHz / 2GB	C++
Samuel	623µs	838µs	194µs	184µs	70µs	24µs	Intel Core i5-2450M @ 2.5GHz / 1GB	C++
Freya	766µs	1070µs	213µs	283µs	105µs	40µs	Intel T4300 @ 2.1GHz / 4GB	C++

-  ⇤ ← Revision 29 as of 2013-11-09 12:37:25 → 
  Size: 2118
  Editor: HSI-KBW-095-208-111-091
  Comment:
+   ← Revision 66 as of 2013-11-12 10:24:44 → ⇥
  Size: 4906
  Editor: fp-192-52-27-183
  Comment:
-Deletions are marked like this.
+Additions are marked like this.
 Line 5:
-. Add your row to the table below, following the examples already there. Simple = the simple linear-time algorithm. Gallop = the asymptotically optimal galloping-search algorithm.
+. Add your row to the table below, following the examples already there. Simple = the simple linear-time algorithm. Gallop = the asymptotically optimal galloping-search algorithm. The number in parantheses after the query is the ratio between the two list length, rounded to the next integer.
 Line 10:
-||<style="text-align:center" |2>'''Name''' ||||<style="text-align:center">''university german'' ||||<style="text-align:center">''university berlin'' ||||<style="text-align:center">''university freiburg'' ||<style="text-align:center" |2>'''Processor / RAM''' ||<style="text-align:center" |2>'''Language''' ||
+||<style="text-align:center" |2>'''Name''' ||||<style="text-align:center">''university german (2:1)'' ||||<style="text-align:center">''university berlin (13:1)'' ||||<style="text-align:center">''university freiburg (198:1)'' ||<style="text-align:center" |2>'''Processor / RAM''' ||<style="text-align:center" |2>'''Language''' ||
-Line 13:
+Line 12:
-||Björn ||430µs ||610µs ||134µs ||146µs ||72µs || 21µs|| Intel X5560 @ 2.8GHz / 36GB ||C++ ||
||MartinM ||1505µs ||1711µs ||308µs ||318µs ||260µs || 29µs|| Intel i7-3770K @ 3.5GHz / 8GB ||Java ||
||DanielL||2071µs ||1454µs ||595µs ||140µs ||392µs || 44µs|| Intel i7-2600 @ 3.4GHz / 16GB ||Java ||
||AlexM||6142µs ||5751µs ||656µs ||943µs ||416µs ||132µs || Intel Core 2 Duo @ 2.0Ghz / 4GB ||Java||
||Oier||4434µs || 5948µs || 696µs || 868µs || 1203µs || 524µs|| Intel Core i5  M 450  @ 2.40GHz / 4GB ||Java||
||Manuel||391µs ||568µs ||79µs ||136µs ||30µs || 14µs|| Intel E3-1230v3 @ 3.7GHz / 2GB (VM) ||C++ ||
||Sven||1218µs || 1833µs || 598µs || 951µs || 494µs || 467µs|| Intel i7-4650U  @ 1.70GHz / 4GB ||Java||
||Janosch||433µs || 644µs || 183µs || 198µs || 97µs || 60µs|| Intel i7-3520M @ 2.9GHz / 8GB ||C++||
||Daniel||381µs || 473µs || 115µs || 141µs || 61µs || 21µs|| Intel i7-920 @ 3.2GHz / 2GB (VM)||C++||
+||Björn ||430µs ||530µs ||134µs ||146µs ||72µs ||21µs ||Intel X5560 @ 2.8GHz / 36GB ||C++ ||
||MartinM ||1505µs ||1711µs ||308µs ||318µs ||260µs ||29µs ||Intel i7-3770K @ 3.5GHz / 8GB ||Java ||
||DanielL ||2071µs ||1454µs ||595µs ||140µs ||392µs ||44µs ||Intel i7-2600 @ 3.4GHz / 16GB ||Java ||
||AlexM ||6142µs ||5751µs ||656µs ||943µs ||416µs ||132µs ||Intel Core 2 Duo @ 2.0Ghz / 4GB ||Java ||
||Oier ||4434µs ||5948µs ||696µs ||868µs ||1203µs ||524µs ||Intel Core i5  M 450  @ 2.40GHz / 4GB ||Java ||
||Manuel ||391µs ||568µs ||79µs ||136µs ||30µs ||14µs ||Intel E3-1230v3 @ 3.7GHz / 2GB (VM) ||C++ ||
||Sven ||1218µs ||1833µs ||598µs ||951µs ||494µs ||467µs ||Intel i7-4650U  @ 1.70GHz / 4GB ||Java ||
||Janosch ||433µs ||644µs ||183µs ||198µs ||97µs ||60µs ||Intel i7-3520M @ 2.9GHz / 8GB ||C++ ||
||Daniel ||381µs ||473µs ||115µs ||141µs ||61µs ||21µs ||Intel i7-920 @ 3.2GHz / 2GB (VM) ||C++ ||
||Bastian ||305µs ||461 µs ||74µs ||144µs ||37µs ||49µs ||Intel i5-3570K @ 3.4GHz / 8GB ||C++ ||
||Iradj ||1171µs ||4658 µs ||493µs ||1715µs ||318µs ||505µs ||Intel i3-2100K @ 2.1GHz / 2GB ||C++ ||
||Nghia ||5295µs ||18031µs ||2532µs ||12679µs ||2656µs ||10209µs ||Intel i7-2630QM @ 2.0GHz / 8GB ||Java ||
||Jens || 423µs || 1103µs || 169µs || 314µs || 120µs || 96µs || Intel i7-3770 @ 3.40GHz / 8GB || C++ ||
||Yu-Wen || 11145µs || 15639µs || 8499µs || 5736µs || 5759µs || 4092µs || Intel Core i3 M330 @ 2.13GHz / 2GB || Java ||
||Lijun || 2310µs || 4968µs || 1471µs || 2855µs || 1351µs || 582µs || Intel Core2 Quad @ 2.40GHz / 4GB || Java ||
||Igor || 2814µs || 2047µs || 160µs || 213µs || 73µs || 50µs || Intel i7-3630QM @ 2.4GHz / 12GB || Java ||
||Rafael || 862 µs || 1038 µs || 295 µs || 270 µs || 165 µs || 27 µs || Intel i5-3317U @ 1.7 GHz / 4 GB || C++ ||
||José || 12450 µs ||117315µs|| 3136 µs ||16375µs|| 570 µs || 1457 µs || Intel core i5 @ 2.4GHz / 8 GB || Java ||
||MartinK || 5516 µs || 4034µs || 9975µs || 4013µs || 2641µs || 2327µs || Intel Core 2 Duo @ 2.0Ghz / 3GB || Java ||
||Wera || 505µs || 666µs || 114µs || 173µs || 52µs || 28µs || Intel i5-2450M @ 2.5Ghz / 8GB || C++ ||
||Ina||326µs||393µs||78µs||106µs||37µs||9µs||Intel i7-3770 @ 3.4GHz / 16GB||C++||
||Björn H|| 1144us || 20255us || 497us || 1342us || 383us || 129us || AMD E-450 APU @ 1.6GHz / 1.6GB || C++ ||
||Julien || 1367µs || 1888µs || 715µs || 1024µs || 634µs || 207µs || Intel Core i5-2500k @ 3.3GHz / 8GB || Java ||
||Simon W || 571µs || 1915µs || 168µs || 379µs || 84µs || 47µs || Intel Core i5 M 430  @ 2.27GHz / 4GB || C++ ||
||A&J || 4370µs || 4858µs || 362µs || 846µs || 187µs || 198µs || Intel i7-3610QM @ 2.3GHz / 32GB || Java ||
||Rick || 666µs || 2300µs || 228µs || 181µs || 79µs || 81µs || Intel Core i5 M 460  @ 2.5GHz / 2GB || C++ ||
||LukasG || 331µs || 2159µs || 96µs || 355µs || 76µs || 29µs || Intel Core i7-2620M @ 2.7GHz / 8GB || C++ ||
||Mateusz || 3090µs || 8988µs || 378µs || 1189µs || 134µs || 42µs || Intel Core i5-2520M @ 2.5GHz / 4GB || Java ||
||Anastasia || 795µs || 1753µs || 329µs || 876µs || 254µs || 591µs || Intel Core i5 M 560 @ 2.67GHz × 4 / 8GB || C++ ||
||Diego || 835µs || 1341µs || 302µs || 412µs || 201µs || 63µs || Intel Core 2 Duo T5450 @ 1.7GHz / 2GB || C++ ||
||Samuel || 623µs || 838µs || 194µs || 184µs || 70µs || 24µs || Intel Core i5-2450M  @ 2.5GHz / 1GB || C++ ||
||Freya || 766µs || 1070µs || 213µs || 283µs || 105µs || 40µs || Intel T4300  @ 2.1GHz / 4GB || C++ ||