Differences between revisions 41 and 70 (spanning 29 versions)

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).

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
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
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.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.069s / 92K	0.037s / 43K			Saarland	Intel i5 750 @ 2.7 GHz
Eugen	C++	0.809s / 1M	0.350s / 446K			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.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.155s / 94K *2	0.140s / 47K *2			Saarland	Intel Pentium D @ 2.8GHz

*1 100 Routen

*2 200 Routen

-  ⇤ ← Revision 41 as of 2011-05-20 13:03:03 → 
  Size: 4504
  Editor: remote218-132
  Comment:
+   ← Revision 70 as of 2011-05-26 14:32:23 → ⇥
  Size: 3385
  Editor: liwip10
  Comment:
-Deletions are marked like this.
+Additions are marked like this.
 Line 9:
----- /!\ '''Edit conflict - other version:''' ----
||'''Name''' ||'''Language''' ||'''Dijkstra''' ||'''A-Star''' ||'''Dataset''' ||'''# of routes tested''' ||'''Hardware''' ||
||Adrian,Kevin,Christoph ||C++ ||0.031s (#settled:  84K) ||0.029s (#settled:  45K) ||Saarland ||1000 ||Core2Duo P8600 @ 2.4Ghz ||
||Adrian,Kevin,Christoph ||C++ ||0.574s (#settled: 974K) ||0.417s (#settled: 484K) ||Ba-Wü ||500 ||Core2Duo P8600 @ 2.4Ghz ||
||Michael,Sebastian,Simon ||Java ||0.018s ||0.027s ||Saarland ||1000 ||Core i7 920 @ 2.67 GHz ||
||Michael,Sebastian,Simon ||Java ||0.282s ||0.435s ||Ba-Wü ||1000 ||Core i7 920 @ 2.67 GHz ||
||Simon,Robin ||C++ ||0.033s (#settled:  94K) ||0.017s (#settled:  45K) ||Saarland ||1000 ||Intel X5560 @ 2.8 GHz ||
||Simon,Robin ||C++ ||0.518s (#settled: 1.1M) ||0.242s (#settled: 465K) ||Ba-Wü ||1000 ||Intel X5560 @ 2.8 GHz ||
||Hannah ||C++ ||0.015s (#settled:  95K) ||0.007s (#settled:  36K) ||Saarland ||1000 ||Intel X5560 @ 2.8 GHz ||
||Hannah ||C++ ||0.296s (#settled: 1.0M) ||0.120s (#settled: 341K) ||Ba-Wü ||1000 ||Intel X5560 @ 2.8 GHz ||
||Vincent,Michael,Patrick ||Java ||0.251s ||0.039s ||Saarland ||1000 ||Intel Core2 Quadcore @ 2,4GHz ||
||Vincent,Michael,Patrick ||Java ||9.88s ||0.239s ||Ba-Wü ||200 ||Intel Core2 Quadcore @ 2,4GHz ||
||Markus,Oleksii,Stefan ||Java ||0.351s ||0.472s ||Saarland ||1000 ||Core i5 M430 @ 2,27GHz ||


||Eugen ||C++ ||0.08s (#settled: 81217) ||0.05s (#settled: 43901) ||Saarland ||1000 ||Intel i5 750 @ 2.7 GHz ||
||Eugen ||C++ ||1.27s (#settled: 1091146) ||0.51s (#settled: 412290) ||Ba-Wü ||100 ||Intel i5 750 @ 2.7 GHz ||
+||'''Name''' ||'''Language''' ||'''Dijkstra''' ||'''A-Star''' ||<style="font-weight:bold;">Landmarks(random) ||<style="font-weight:bold;">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 ||
||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 ||
||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.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.069s / 92K ||0.037s / 43K || || ||Saarland ||Intel i5 750 @ 2.7 GHz ||
||Eugen ||C++ ||0.809s / 1M  ||0.350s / 446K || || ||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.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.155s / 94K *2 ||0.140s / 47K *2 || || ||Saarland ||Intel Pentium D @ 2.8GHz ||
-Line 30:
+Line 31:
----- /!\ '''Edit conflict - your version:''' ----
||'''Name''' ||'''Language''' ||'''Dijkstra''' ||'''A-Star''' ||'''Dataset''' ||'''# of routes tested''' ||'''Hardware''' ||
||Adrian,Kevin,Christoph ||C++ ||0.031s (#settled:  84K) ||0.029s (#settled:  45K) ||Saarland ||1000 ||Core2Duo P8600 @ 2.4Ghz ||
||Adrian,Kevin,Christoph ||C++ ||0.574s (#settled: 974K) ||0.417s (#settled: 484K) ||Ba-Wü ||500 ||Core2Duo P8600 @ 2.4Ghz ||
||Michael,Sebastian,Simon ||Java ||0.018s ||0.027s ||Saarland ||1000 ||Core i7 920 @ 2.67 GHz ||
||Michael,Sebastian,Simon ||Java ||0.282s ||0.435s ||Ba-Wü ||1000 ||Core i7 920 @ 2.67 GHz ||
||Simon,Robin ||C++ ||0.033s (#settled:  94K) ||0.017s (#settled:  45K) ||Saarland ||1000 ||Intel X5560 @ 2.8 GHz ||
||Simon,Robin ||C++ ||0.518s (#settled: 1.1M) ||0.242s (#settled: 465K) ||Ba-Wü ||1000 ||Intel X5560 @ 2.8 GHz ||
||Hannah ||C++ ||0.015s (#settled:  95K) ||0.007s (#settled:  36K) ||Saarland ||1000 ||Intel X5560 @ 2.8 GHz ||
||Hannah ||C++ ||0.296s (#settled: 1.0M) ||0.120s (#settled: 341K) ||Ba-Wü ||1000 ||Intel X5560 @ 2.8 GHz ||
||Vincent,Michael,Patrick ||Java ||0.251s ||0.039s ||Saarland ||1000 ||Intel Core2 Quadcore @ 2,4GHz ||
||Vincent,Michael,Patrick ||Java ||9.88s ||0.239s ||Ba-Wü ||200 ||Intel Core2 Quadcore @ 2,4GHz ||
||Mirko,Dirk,Kyanoush||C++||0.0789s (#settled 37k)||0.07757s (#settled 37k)||Saarland||1000 ||Intel Core2Duo @ 2,0GHz ||
||Mirko,Dirk,Kyanoush||C++||0.9997s (#settled 442k)||0.9837s (#settled 436k)||Ba-Wü||100 ||Intel Core2Duo @ 2,0GHz ||
-Line 45:
+Line 32:
----- /!\ '''End of edit conflict''' ----
+'' *1 '' 100 Routen

''*2'' 200 Routen