3 ms·
Nice, 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,
by logicchains 12y ago
Nice, 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.