MPC-Epic Road Trip

JavaScript performance comparison

Test case created by Joshua Piccari

Preparation code

 
<script>
Benchmark.prototype.setup = function() {
    var ben = (function(){
    function longestRoute(start, end, map) {
        var routes = getPossibleRoutes(start, end, map), // Get the possible routes from start to end in a list
            route = false;
       
        if( typeof routes !== 'object' || !routes.length ){
            return false;
        }
       
        // Find the longest of the available routes
        for( var x = 0; x < routes.length; x++ ){
            if( !route || (routes[x].distance && routes[x].distance > route.distance) ){
                route = routes[x];
            }
        }
       
        // console.log(route.path.join(' > ') + ' : DISTANCE ' + route.distance);
   
        return route.distance;
    }
   
    // This is a recursive function that will find every possible route from start to finish
    function getPossibleRoutes(start, end, map, visited, dist){
        var destinations = map[start],
            routes = [],
            result;
       
        // Make sure the start point is in the map, otherwise we'll make an empty destination list
        if( typeof destinations !== 'object' ){
            destinations = [];
        }
       
        // Visited won't exist if this is the first call, so creating it if it doesn't exist yet
        typeof visited === 'object' || (visited = []);
        visited.push(start);
   
        // Make sure we don't get a NaN when we do math on dist on the first call
        typeof dist === 'number' || (dist = 0);
   
        // When called with the start and end as the same, we've reached the end of this path
        if( start === end ){
                routes.push({
                        path: visited,
                        distance: dist
                });
        }
        // If we're not at the end, go through all available paths from this destination
        // This will fork out new paths for each available road and add all possible final routes to this current path
        else{
                for( var x = 0; x < destinations.length; x++ ){
                    if( visited.indexOf(destinations[x].city) === -1 ){
                        result = getPossibleRoutes(destinations[x].city, end, map, visited.slice(0), dist + destinations[x].distance); // The slice() is to make a copy of the array, otherwise all the different paths share it
                        if( result && result.length ){
                            routes = routes.concat(result);
                        }
                    }
                }      
        }
       
        return routes;
    }
    return longestRoute;
    }());
   
    var joshua = (function(){
    function longestRoute(start, end, map, v, explored, dist, maxDist) {
        var i, w;
        v = v || start;
        maxDist = maxDist || -Infinity;
        (explored = explored || {})[v] = true;
   
        if(v !== end) {
                for(i = map[v].length; i--; ) {
                        w = map[v][i];
                        if(!explored[w.city]) {
                                maxDist = longestRoute(start, end, map, w.city, explored, ~~dist + w.distance, maxDist);
                        }
                }
        }
   
        delete explored[v];
        return Math.max(~~dist, maxDist);
    }
    return longestRoute;
    }());
   
    var haebin = (function(){
    function longestRoute(start, end, map) {
        var visited = {};    
        var max = 0, sum = 0;
        visited[start] = 0;
   
        function getDistance(city){
            var n = map[city].length;
   
            for(var i=0; i<n; i++){
               var nextcity = map[city][i].city;
                                                 
               if(!(nextcity in visited)){                             
                        distance = map[city][i].distance;                      
                        visited[nextcity] = distance;                  
   
                        if(nextcity===end){
                                sum = getSum(visited);
                                if (sum > max) {
                                        max = sum;
                                }
                                delete visited[nextcity];
                        } else {
                                max = getDistance(nextcity);
                        }
                }
                }
                delete visited[city];
            return max;
        }
       
        function getSum(hash){
                var sum = 0;
                for(var key in hash) {
                sum += hash[key];
            }
            return sum;
        }  
        return getDistance(start);
    }
   
   
    return longestRoute;
    }());
   
    var map = {
                'Bend': [
                        { city: 'Maryhill State Park', distance: 138 },
                        { city: 'Ochoco National Forest', distance: 83 },
                        { city: 'Portland', distance: 163 }
                ],
   
                'Ellensberg': [
                        { city: 'Lincoln Rock State Park', distance: 74 },
                        { city: 'Maryhill State Park', distance: 116 },
                        { city: 'Pendleton', distance: 177 },
                        { city: 'Seattle', distance: 107 }
                ],
   
                'Lincoln Rock State Park': [
                        { city: 'Ellensberg', distance: 74 }
                ],
   
                'Maryhill State Park': [
                        { city: 'Bend', distance: 138 },
                        { city: 'Ellensberg', distance: 116 },
                        { city: 'Ochoco National Forest', distance: 133 },
                        { city: 'Pendleton', distance: 107 },
                        { city: 'Portland', distance: 104 }
                ],
   
                'Ochoco National Forest': [
                        { city: 'Bend', distance: 83 },
                        { city: 'Maryhill State Park', distance: 133 },
                        { city: 'Pendleton', distance: 188 }
                ],
   
                'Portland': [
                        { city: 'Bend', distance: 163 },
                        { city: 'Maryhill State Park', distance: 104 },
                        { city: 'Seattle', distance: 173 }
                ],
   
                'Pendleton': [
                        { city: 'Ellensberg', distance: 177 },
                        { city: 'Maryhill State Park', distance: 107 },
                        { city: 'Ochoco National Forest', distance: 188 }
                ],
   
                'Seattle': [
                        { city: 'Ellensberg', distance: 107 },
                        { city: 'Portland', distance: 173 }
                ]
        };
};
</script>

Test runner

Warning! For accurate results, please disable Firebug before running the tests. (Why?)

Java applet disabled.

Testing in unknown unknown
Test Ops/sec
Ben P
ben('Seattle', 'Ochoco National Forest', map);
pending…
Joshua P
joshua('Seattle', 'Ochoco National Forest', map);
pending…
Haebin
haebin('Seattle', 'Ochoco National Forest', map);
pending…

You can edit these tests or add even more tests to this page by appending /edit to the URL.

Compare results of other browsers

0 comments

Add a comment