Skip to content

Commit 6c02b4b

Browse files
ASbeletskyASbeletsky
committed
improve algorithm execution
1 parent 02a4f76 commit 6c02b4b

5 files changed

Lines changed: 86 additions & 17 deletions

File tree

‎.babelrc‎

Lines changed: 7 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,9 @@
11
{
2-
presets: ['es2015', 'react']
2+
presets: ['es2015', 'react'],
3+
plugins: [
4+
["transform-runtime", {
5+
"polyfill": false,
6+
"regenerator": true
7+
}]
8+
]
39
}

‎algorithm/shortest_path/dijkstra/shortest_path/pure-code.js‎

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
var s = Integer.random(0, G.length - 1);
2+
var e; // e = end node
3+
do {
4+
e = Integer.random(0, G.length - 1);
5+
} while (s === e);
6+
var MAX_VALUE = Infinity;
7+
var S = [];
8+
for (var i = 0; i < G.length; i++) S[i] = MAX_VALUE;
9+
10+
function Dijkstra(G, start, end) {
11+
var minIndex, minDistance;
12+
var D = [];
13+
for (var i = 0; i < G.length; i++) D.push(false);
14+
S[start] = 0;
15+
var k = G.length;
16+
while (k--) {
17+
minDistance = MAX_VALUE;
18+
for (i = 0; i < G.length; i++) {
19+
if (S[i] < minDistance && !D[i]) {
20+
minDistance = S[i];
21+
minIndex = i;
22+
}
23+
}
24+
if (minDistance === MAX_VALUE) break;
25+
D[minIndex] = true;
26+
for (i = 0; i < G.length; i++) {
27+
if (G[minIndex][i] && S[i] > S[minIndex] + G[minIndex][i]) {
28+
S[i] = S[minIndex] + G[minIndex][i];
29+
}
30+
}
31+
}
32+
33+
return S[end];
34+
}
35+
36+
Dijkstra(G, s, e);

‎js/experiment/algorithm-executer.js‎

Lines changed: 28 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -1,24 +1,38 @@
11
const graphGenerator = require('./graph-generator');
22
const utils = require('./../utils');
3-
const get = require('./..ajax/get');
3+
const get = require('./../server/ajax/get');
44
const Server = require('./../server');
5-
const graphs = graphGenerator();
65

76

8-
const measureExecutionTime = (code) => {
7+
const algorithmsCode = new Map();
8+
const algorithmsMeasure = new Map();
9+
const loadAlgorithms = (problem, algorithms) => {
10+
return Promise.all(algorithms.map(algorithm => {
11+
var codeDir = utils.getFileDir(problem, algorithm, problem);
12+
return get(`${codeDir}pure-code.js`).then(code => algorithmsCode.set(algorithm, code))
13+
}));
14+
};
15+
16+
const measureExecutionTime = (graph, code) => {
17+
var algo = new Function("G", code);
918
const start = performance.now();
10-
eval(code);
19+
algo(graph);
1120
const end = performance.now();
1221
return end - start;
1322
};
1423

15-
// const runAlgorithms = (problem, algorithms) => {
16-
// for(var graph in graphs){
17-
// for(var algorithm in algorithmsNames){
18-
// var codeDir = utils.getFileDir(problem, algorithm, problem);
19-
// get(`${codeDir}code.js`).then((code) => {
20-
// var executionTime = measureExecutionTime(code);
21-
// })
22-
// }
23-
// }
24-
// }
24+
const runAlgorithms = (problem, algorithms, startSize, endSize) => {
25+
const graphs = graphGenerator(startSize, endSize);
26+
return loadAlgorithms(problem, algorithms).then(() => {
27+
for(var graph of graphs){
28+
algorithms.forEach((algorithm) =>{
29+
let executionTime = measureExecutionTime(graph, algorithmsCode.get(algorithm));
30+
algorithmsMeasure.set(algorithm, {graph, executionTime });
31+
});
32+
}
33+
34+
return algorithmsMeasure;
35+
});
36+
};
37+
38+
module.exports = runAlgorithms;

‎js/experiment/components/experiment_settings/ExperimentForm.js‎

Lines changed: 11 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -3,6 +3,7 @@ import GraphSizeSlider from './GraphSizeSlider';
33
import ExperimentProgressBar from './ExperimentProgressBar';
44
import Select from 'react-select';
55
const app = require('./../../../app');
6+
const algoritmsExecute = require('./../../algorithm-executer');
67

78
export default class ExperimentForm extends React.Component{
89
constructor(props) {
@@ -22,7 +23,7 @@ export default class ExperimentForm extends React.Component{
2223

2324
this.state = {
2425
selectedProblem: defaultProblem,
25-
selectedAlgorithms: [],
26+
selectedAlgorithms: "",
2627
graphProblems: this.getGraphProblems(),
2728
problemAlgorithms: this.getProblemAlgorithms(defaultProblem)
2829
};
@@ -31,7 +32,7 @@ export default class ExperimentForm extends React.Component{
3132
handleChangeProblem (selectedProbem){
3233
this.setState({
3334
selectedProblem: selectedProbem,
34-
selectedAlgorithms: [],
35+
selectedAlgorithms: "",
3536
problemAlgorithms: this.getProblemAlgorithms(selectedProbem.value)
3637
});
3738
};
@@ -42,6 +43,13 @@ export default class ExperimentForm extends React.Component{
4243
});
4344
};
4445

46+
runAlgorithms(){
47+
algoritmsExecute(this.state.selectedProblem.value,
48+
this.state.selectedAlgorithms.split(","),
49+
10,
50+
20);
51+
}
52+
4553
render(){
4654
return (
4755
<div className="form-horizontal">
@@ -57,6 +65,7 @@ export default class ExperimentForm extends React.Component{
5765
<Select simpleValue className="col-md-5" name="algorithms" multi onChange={this.handleChangeAlgomithms.bind(this)} value={this.state.selectedAlgorithms} options={this.state.problemAlgorithms} />
5866
</div>
5967
<h3>Step 3. Run experiment</h3>
68+
<button onClick={this.runAlgorithms.bind(this)}>Run</button>
6069
<div className="col-md-8">
6170
<ExperimentProgressBar percentComplete={0} />
6271
</div>

‎package.json‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -25,6 +25,7 @@
2525
"babel-core": "^6.9.0",
2626
"babel-preset-es2015": "^6.9.0",
2727
"babel-preset-react": "^6.24.1",
28+
"babel-runtime": "^6.26.0",
2829
"babelify": "^7.3.0",
2930
"bootstrap": "^3.3.7",
3031
"bootstrap-slider": "^10.0.0",
@@ -45,5 +46,8 @@
4546
"rsvp": "^3.2.1",
4647
"vinyl-buffer": "^1.0.0",
4748
"vinyl-source-stream": "^1.1.0"
49+
},
50+
"devDependencies": {
51+
"babel-plugin-transform-runtime": "^6.23.0"
4852
}
4953
}

0 commit comments

Comments
 (0)