Differences between revisions 57 and 160 (spanning 103 versions)

Your experimental results for exercise sheet 1 and 2

Please sumarize your results from exercise sheet 1 and 2 in a row in the table below. In the first column, write your name (abbreviate if you are in a group, to keep it short). In the second column, put the programming language you used (C++ or Java). In the third column put the average running time (in seconds) for 1000 random queries using Dijkstra's algorithm. In the fourth column put the average running time (in seconds) for 1000 random queries using A-star with the straightline heuristic. In the last column put the name of the dataset you computed these average times on (preferably Ba-Wü, but if that didn't work Saarland).

Here is the table with the correspondence Road Types <-> Speeds.

Note(Hannah): Saarland has about 400K non-isolated nodes, Ba-Wü has about 5M non-isolated nodes. (K stands for thousand, M stands for million, also in the table below.)

Note(Hannah): There are quite a number of road types not considered in our table. These account for more than half of the arcs in the two networks. If I take them into account (with a speed of 5 km/h, but that doesn't really matter) by average query times and the number of settled nodes more than doubles.

Name	Language	Dijkstra	A-Star	Landmarks(random)	Landmarks(farthest)	Dataset	Hardware
Adrian,Kevin,Christoph	C++	0.029s / 84K	0.024s / 36K	0.016s / 37K	0.014s / 34K	Saarland	Core2Duo P8600 @ 2.4Ghz
Adrian,Kevin,Christoph	C++	0.574s / 974K	0.307s / 371K	0.249s / 409K	0.229s / 345K	Ba-Wü	Core2Duo P8600 @ 2.4Ghz
Christoph,Adrian,Kevin	PHP	8.713s / 85K	4.19s / 37K			Saarland	Core2Duo P8600 @ 2.4Ghz
Michael,Sebastian,Simon	Java	0.058s / 73K	0.078s / 34K	0.061s / 60K	0.062s / 61K	Saarland	Core i7 920 @ 2.67 GHz
Michael,Sebastian,Simon	Java	0.927s / 836K	1.030s / 467K	0.999s / 727K	1.018s / 723K	Ba-Wü	Core i7 920 @ 2.67 GHz
Simon,Robin	C++	0.033s / 94K	0.017s / 45K	0.016s / 31K	0.012s / 23K	Saarland	Intel X5560 @ 2.8 GHz
Simon,Robin	C++	0.518s /1.1M	0.242s / 465K	0.240s / 324K	0.160s / 233K	Ba-Wü	Intel X5560 @ 2.8 GHz
Hannah	C++	0.015s / 95K	0.007s / 36K			Saarland	Intel X5560 @ 2.8 GHz
Hannah	C++	0.296s / 1.0M	0.120s / 341K			Ba-Wü	Intel X5560 @ 2.8 GHz
Vincent,Michael,Patrick	Java	0.213s / 95K	0.16s / 47K	0.084s / 37K	0.069s / 31K	Saarland	Intel Core2 Quadcore @ 2,4GHz
Markus,Oleksii,Stefan	Java	0.130s / 95K	0.100s / 44K	0.352s / 35K	0.140s / 50K	Saarland	Intel i5 M430 @ 2,27GHz
Markus,Oleksii,Stefan	Java	3.52s / 1.2M	1.90s / 540K			Ba-Wü	Intel i5 M430 @ 2,27GHz
Eugen	C++	0.287s / 1M	0.170s / 458K	0.183s / 316k	0.127s / 230k	Ba-Wü	Intel i5 750 @ 2.7 GHz
Katja,Matthias	Java	0.169s / 94K	0.138s / 45K	0.073s / 31k	0.074s / 31k	Saarland	Intel i7 M620 @ 2.67 GHz
Mirko,Dirk,Kyanoush	C++	0.026s / 95K	0.025s / 44K	0.021s / 35K	0.018s / 28K	Saarland	Intel Core2Duo @ 2.4 GHz
Mirko,Dirk,Kyanoush	C++	0.408s / 1.1M	0.333s / 455K	0.395s / 349K	0.356s / 281K	Ba-Wü	Intel Core2Duo @ 2.4 GHz
Jens,Alexander	C++	0.066s / 182k *1	0.024s / 70k *1			Saarland	Intel Core2 Duo @ 3.00GHz
Jens,Alexander	C++	0.941s / 2.4M *1	0.173s / 117k *1			Ba-Wü	Intel Core2 Duo @ 3.00GHz
Mauricio	C++	0.0316s / 99k	0.0163s / 47k	0.0082s / 14k	0.0002s / 7k	Saarland	Intel Core2 Quad Q6600 @ 2.4GHz
Markus, Dominik, Luc	C++	1.4/95k	0.7s/ 55k	0.4/35k	1s/72k	Saarland	Intel Atom N270, @ 1.6GHz, 1GB Ram
Denis, Rebecca	Java	0.548s / 507K	0.415 / 502K			Ba-Wü	Intel i7 @ 3.07 GHz
Denis, Rebecca	Java	0.959s / 101K	0.26s / 65K	1.2s / 78k	1.2s / 80k	Saarland	Athlon 3200++ @ 2GHz
Marcel, Felix	Java	0.147s / 100K	0.16s / 93K	NY/A / NY/A	NY/A / NY/A	Saarland	Intel i5 (4GB RAM) @ 2.3GHz
Marcel, Felix	Java	NY/A / NY/A	3.72s / 1.1M	NY/A / NY/A	NY/A / NY/A	Ba-Wü	Intel i5 (4GB RAM) @ 2.3GHz
Philipp, Flo, André	Java	0.087s / 95K	0.112s / 47K	0.189s / 35k	0.104s / 53K	Saarland	Intel i3 @ 2.27GHz
Philipp, Flo, André	Java	1.337s / 1.1M	1.509s / 550K	2.908s / 500K	1.019s / 366K	Ba-Wü	Intel i3 @ 2.27GHz
Jendrik, Jonas, Philip	C++	0.021s / 92K	0.013s / 44K	0.013s / 29K	0.012s / 27K	Saarland	Intel Core2Duo @ 2.5GHz
Jendrik, Jonas, Philip	C++	0.321s / 1.04M	0.199s / 0.44M	0.282s / 0.38M	0.145s / 0.19M	Ba-Wü	Intel Core2Duo @ 2.5GHz
Bettina	C++	0.069s / 122K	0.051s / 54K			Saarland	Intel Core2Duo T5800 @ 2.0GHz
Jeremi, Matthias	Java	0.159s / 94K	0.065s / 22K	0.034s / 20K		Saarland	Intel Core i5 @ 2.67GHz
Tim & Raphael	C++	0.042s / kA	0.035s / kA			Saarland	AMD Phenom II X4 940 @ 3.0 GHz
Tim & Raphael	C++	0.935s / kA	0.671s / kA			Ba-Wü	AMD Phenom II X4 940 @ 3.0 GHz

*1 100 Routen

*2 200 Routen

-  ⇤ ← Revision 57 as of 2011-05-21 00:51:37 → 
  Size: 3312
  Editor: eth0-9
  Comment:
+   ← Revision 160 as of 2011-06-29 14:33:42 → ⇥
  Size: 5417
  Editor: fawp01
  Comment:
-Deletions are marked like this.
+Additions are marked like this.
 Line 1:
-= Your experimental results for exercise sheet 1 =
Please sumarize your results from exercise sheet 1 in a row in the table below. In the first column, write your name (abbreviate if you are in a group, to keep it short). In the second column, put the programming language you used (C++ or Java). In the third column put the average running time (in seconds) for 1000 random queries using Dijkstra's algorithm. In the fourth column put the average running time (in seconds) for 1000 random queries using A-star with the straightline heuristic. In the last column put the name of the dataset you computed these average times on (preferably Ba-Wü, but if that didn't work Saarland).
+= Your experimental results for exercise sheet 1 and 2 =
Please sumarize your results from exercise sheet 1 and 2 in a row in the table below. In the first column, write your name (abbreviate if you are in a group, to keep it short). In the second column, put the programming language you used (C++ or Java). In the third column put the average running time (in seconds) for 1000 random queries using Dijkstra's algorithm. In the fourth column put the average running time (in seconds) for 1000 random queries using A-star with the straightline heuristic. In the last column put the name of the dataset you computed these average times on (preferably Ba-Wü, but if that didn't work Saarland).
 Line 9:
-||'''Name''' ||'''Language''' ||'''Dijkstra''' ||'''A-Star''' ||<style="font-weight:bold;">Landmarks(random) ||<style="font-weight:bold;">Landmarks(farthest) ||'''Dataset''' ||'''Hardware''' ||
+||<tablewidth="1208px" tableheight="637px">'''Name''' ||'''Language''' ||'''Dijkstra''' ||'''A-Star''' ||<style="font-weight: bold;">Landmarks(random) ||<style="font-weight: bold;">Landmarks(farthest) ||'''Dataset''' ||'''Hardware''' ||
 Line 11:
-||Adrian,Kevin,Christoph ||C++ ||0.574s / 974K ||0.322s / 377K ||0.285s / 427K ||0.261s / 390K ||Ba-Wü ||Core2Duo P8600 @ 2.4Ghz ||
||Michael,Sebastian,Simon ||Java ||0.018s ||0.027s || || ||Saarland ||Core i7 920 @ 2.67 GHz ||
||Michael,Sebastian,Simon ||Java ||0.282s ||0.435s || || ||Ba-Wü ||Core i7 920 @ 2.67 GHz ||
||Simon,Robin ||C++ ||0.033s /  94K ||0.017s /  45K || || ||Saarland ||Intel X5560 @ 2.8 GHz ||
||Simon,Robin ||C++ ||0.518s /1.1M ||0.242s / 465K || || ||Ba-Wü ||Intel X5560 @ 2.8 GHz ||
+||Adrian,Kevin,Christoph ||C++ ||0.574s / 974K ||0.307s / 371K ||0.249s / 409K ||0.229s / 345K ||Ba-Wü ||Core2Duo P8600 @ 2.4Ghz ||
||Christoph,Adrian,Kevin ||PHP :D ||8.713s / 85K ||4.19s / 37K || || ||Saarland ||Core2Duo P8600 @ 2.4Ghz ||
||Michael,Sebastian,Simon ||Java ||0.058s / 73K ||0.078s / 34K ||0.061s / 60K ||0.062s / 61K ||Saarland ||Core i7 920 @ 2.67 GHz ||
||Michael,Sebastian,Simon ||Java ||0.927s / 836K ||1.030s / 467K ||0.999s / 727K ||1.018s / 723K ||Ba-Wü ||Core i7 920 @ 2.67 GHz ||
||Simon,Robin ||C++ ||0.033s /  94K ||0.017s /  45K ||0.016s / 31K ||0.012s / 23K ||Saarland ||Intel X5560 @ 2.8 GHz ||
||Simon,Robin ||C++ ||0.518s /1.1M ||0.242s / 465K ||0.240s / 324K ||0.160s / 233K ||Ba-Wü ||Intel X5560 @ 2.8 GHz ||
-Line 18:
+Line 19:
-||Vincent,Michael,Patrick ||Java ||0.251s ||0.039s || || ||Saarland ||Intel Core2 Quadcore @ 2,4GHz ||
||Vincent,Michael,Patrick ||Java ||9.88s *2 ||0.239s *2 || || ||Ba-Wü ||Intel Core2 Quadcore @ 2,4GHz ||
||Markus,Oleksii,Stefan ||Java ||0.351s ||0.472s || || ||Saarland ||Core i5 M430 @ 2,27GHz ||
||Eugen ||C++ ||0.08s / 81K ||0.05s / 43K || || ||Saarland ||Intel i5 750 @ 2.7 GHz ||
||Eugen ||C++ ||1.27s / 1M *1 ||0.51s / 412K *1 || || ||Ba-Wü ||Intel i5 750 @ 2.7 GHz ||
||Mirko,Dirk,Kyanoush ||C++ ||0.032s / 94K ||0.047s / 45K || || ||Saarland ||Intel Core2Duo @ 1.8 GHz ||
||Mirko,Dirk,Kyanoush ||C++ ||0.495s / 1.1M ||0.592s / 465K || || ||Ba-Wü ||Intel Core2Duo @ 1.8 GHz ||
||Jens,Alexander ||C++ ||0.10s / 414k *1 ||0.02s / 42k *1 || || ||Saarland ||Intel(R) Core(TM)2 Duo CPU E8400 @ 3.00GHz ||
||Jens,Alexander ||C++ ||1.50s / 5M *1 ||0.21s / 49k *1 || || ||Ba-Wü ||Intel(R) Core(TM)2 Duo CPU E8400 @ 3.00GHz ||
+||Vincent,Michael,Patrick ||Java ||0.213s / 95K ||0.16s / 47K ||0.084s / 37K ||0.069s / 31K ||Saarland ||Intel Core2 Quadcore @ 2,4GHz ||
||Markus,Oleksii,Stefan ||Java ||0.130s / 95K ||0.100s / 44K ||0.352s / 35K ||0.140s / 50K ||Saarland ||Intel i5 M430 @ 2,27GHz ||
||Markus,Oleksii,Stefan ||Java ||3.52s / 1.2M ||1.90s / 540K || || ||Ba-Wü ||Intel i5 M430 @ 2,27GHz ||
||Eugen ||C++ ||0.287s / 1M ||0.170s / 458K ||0.183s / 316k ||0.127s / 230k ||Ba-Wü ||Intel i5 750 @ 2.7 GHz ||
||Katja,Matthias ||Java ||0.169s / 94K ||0.138s / 45K || 0.073s / 31k || 0.074s / 31k ||Saarland ||Intel i7 M620 @ 2.67 GHz ||
||Mirko,Dirk,Kyanoush ||C++ ||0.026s / 95K ||0.025s / 44K ||0.021s / 35K ||0.018s / 28K ||Saarland ||Intel Core2Duo @ 2.4 GHz ||
||Mirko,Dirk,Kyanoush ||C++ ||0.408s / 1.1M ||0.333s / 455K ||0.395s / 349K ||0.356s / 281K ||Ba-Wü ||Intel Core2Duo @ 2.4 GHz ||
||Jens,Alexander ||C++ ||0.066s / 182k *1 ||0.024s / 70k *1 || || ||Saarland ||Intel Core2 Duo @ 3.00GHz ||
||Jens,Alexander ||C++ ||0.941s / 2.4M *1 ||0.173s / 117k *1 || || ||Ba-Wü ||Intel Core2 Duo @ 3.00GHz ||
||Mauricio ||C++ ||0.0316s / 99k ||0.0163s / 47k ||0.0082s / 14k ||0.0002s / 7k ||Saarland ||Intel Core2 Quad Q6600 @ 2.4GHz ||
||Markus, Dominik, Luc ||C++ ||1.4/95k ||0.7s/ 55k ||0.4/35k ||1s/72k ||Saarland ||Intel Atom N270, @ 1.6GHz, 1GB Ram ||
||Denis, Rebecca ||Java ||0.548s / 507K ||0.415 / 502K || || ||Ba-Wü ||Intel i7 @ 3.07 GHz ||
||Denis, Rebecca ||Java ||0.959s / 101K ||0.26s / 65K ||1.2s / 78k ||1.2s / 80k ||Saarland ||Athlon 3200++ @ 2GHz ||
||Marcel, Felix ||Java ||0.147s / 100K ||0.16s / 93K ||NY/A / NY/A ||NY/A / NY/A ||Saarland ||Intel i5 (4GB RAM) @ 2.3GHz ||
||Marcel, Felix ||Java ||NY/A / NY/A||3.72s / 1.1M ||NY/A / NY/A ||NY/A / NY/A ||Ba-Wü||Intel i5 (4GB RAM) @ 2.3GHz ||
||Philipp, Flo, André ||Java ||0.087s / 95K ||0.112s / 47K ||0.189s / 35k ||0.104s / 53K ||Saarland ||Intel i3 @ 2.27GHz ||
||Philipp, Flo, André ||Java ||1.337s / 1.1M ||1.509s / 550K ||2.908s / 500K ||1.019s / 366K ||Ba-Wü ||Intel i3 @ 2.27GHz ||
||Jendrik, Jonas, Philip ||C++ ||0.021s / 92K ||0.013s / 44K ||0.013s / 29K ||0.012s / 27K ||Saarland ||Intel Core2Duo @ 2.5GHz ||
||Jendrik, Jonas, Philip ||C++ ||0.321s / 1.04M ||0.199s / 0.44M ||0.282s / 0.38M ||0.145s / 0.19M ||Ba-Wü ||Intel Core2Duo @ 2.5GHz ||
||Bettina ||C++ ||0.069s / 122K ||0.051s / 54K || || ||Saarland ||Intel Core2Duo T5800 @ 2.0GHz ||
||Jeremi, Matthias ||Java ||0.159s / 94K ||0.065s / 22K ||0.034s / 20K || ||Saarland ||Intel Core i5 @ 2.67GHz ||
||Tim & Raphael ||C++ ||0.042s / kA ||0.035s /  kA || || ||Saarland ||AMD Phenom II X4 940 @ 3.0 GHz ||
||Tim & Raphael ||C++ ||0.935s / kA ||0.671s / kA || || ||Ba-Wü ||AMD Phenom II X4 940 @ 3.0 GHz ||