5 ms·
I'm really impressed you implemented this in so many languages! I was curious how fast Javascript would run this, so I ported the lua example over, it ran in 2
by brucer 12y ago
I'm really impressed you implemented this in so many languages!
I was curious how fast Javascript would run this, so I ported the lua example over, it ran in 2200msec on my mac laptop.
I'm not sure it's a great comparison benchmark however, because there are some obvious optimizations you can make. I added a simple cache to avoid recalculating travel costs for leaves and it now runs in 150msec.
var fs = require('fs');
var nodes = [], visited = [];
var visitCache = {};
function readPlaces() {
var lines = fs.readFileSync('agraph','utf8').split('\n');
var numnodes = lines[0]|0;
for(var i=0;i<numnodes;i++) {
nodes[i] = [];
visited[i] = false;
}
for(i=1;i<lines.length;i++) {
var line = lines[i].split(' ');
nodes[line[0]|0].push({dst: line[1]|0, cost: line[2]|0});
}
}
function getLongestPath(nodes, nodeid, visited) {
visited[nodeid] = true;
var neighbours = nodes[nodeid];
var max = 0
for(var i=0;i<neighbours.length;i++) {
if (!visited[neighbours[i].dst]) {
var dist = neighbours[i].cost + getLongestPath(nodes, neighbours[i].dst, visited);
if (dist > max) {
max = dist
}
}
}
visited[nodeid] = false;
return max;
}
function getLongestPathCached(nodes, nodeid, visited, depth) {
var idx;
visited |= 1 << nodeid;
if (depth == nodes.length - 7) {
idx = (visited * 32) + nodeid;
if (visitCache[idx]) {
return visitCache[idx];
}
}
var neighbours = nodes[nodeid];
var max = 0
for(var i=0;i<neighbours.length;i++) {
if (!(visited & (1 << neighbours[i].dst))) {
var dist = neighbours[i].cost + getLongestPathCached(nodes, neighbours[i].dst, visited, depth+1);
if (dist > max) {
max = dist
}
}
}
if (idx) {
visitCache[idx] = max;
}
if (typeof visited != 'number') {
visited[nodeid] = false;
}
return max;
}
readPlaces();
var start = Date.now();
var length;
if (nodes.length < 32) {
length = getLongestPathCached(nodes, 0, 0, 0);
} else {
length = getLongestPath(nodes, 0, visited);
}
console.log(length+' LANGUAGE Javascript: '+(Date.now() - start));
- logicchains 12y agoNice, your cached version is the fastest by far, although it uses a different algorithm. Running with `node js.js` without the cache, it takes around 6 seconds, close to Dart and Haskell.
- brucer 12y agoI just realized I overthought the caching scheme, and removing one check made it 3x faster :) function getLongestPathCached(nodes, nodeid, visited, depth) { var idx; visited |= 1 << nodeid; idx = (visited * 32) + nodeid; if (visitCache[idx]) { return visitCache[idx]; } var neighbours = nodes[nodeid]; var max = 0 for(var i=0;i<neighbours.length;i++) { if (!(visited & (1 << neighbours[i].dst))) { var dist = neighbours[i].cost + getLongestPathCached(nodes, neighbours[i].dst, visited, depth+1); if (dist > max) { max = dist } } } visitCache[idx] = max; return max; }
- logicchains 12y agoNice! That's almost as fast as the C++ one using caching; your algorithm must be better.