9
\$\begingroup\$

I've been learning Python for about a year and now I'm trying to improve my JavaScript. I wrote this simple d3 visualization that shows your Facebook friends as a force-directed graph. Here's a live version and here's the source on GitHub. It works well, but it can be slow.

I understand that the number of edges to calculate grows \$O(n^2)\$ with nodes, so complexity increases quickly for users with lots of friends, but I'm wondering if:

  1. there are any obvious optimizations I could make

  2. what bad habits I might be importing from Python

  3. how I might tweak the layout parameters to reach equilibrium faster

I'm pretty new to programming and very new to JavaScript, so I'm sure I'm making some mistakes.

Content of file friendgraph.js:

// Facebook SDK

// Initialize the Facebook SDK
window.fbAsyncInit = function () {
    FB.init({
        appId: '341827359241906', // App ID
        channelUrl: 'channel.html', // Path to your Channel File
        status: true, // check login status
        cookie: true, // enable cookies to allow the server to access the session
        xfbml: true  // parse XFBML
});

// Listen for and handle auth.statusChange events
FB.Event.subscribe('auth.statusChange', function(response) {
    if (response.authResponse) {
        // On login...
        FB.api('/me', function(me) {
            if (me.name) {
                // Display user name
                document.getElementById('auth-displayname').innerHTML = me.name;
                // Retrieve friends API object
                FB.api('/me/friends', getFriends);
            }
        })
        document.getElementById('auth-loggedout').style.display = 'none';
        document.getElementById('auth-loggedin').style.display = 'block';
    } else {
        // User has not authorized your app or isn't logged in
        document.getElementById('auth-loggedout').style.display = 'block';
        document.getElementById('auth-loggedin').style.display = 'none';
    }
    });

    // Respond to clicks on login and logout links
    document.getElementById('auth-loginlink').addEventListener('click', function() {
        FB.login();
    });
    document.getElementById('auth-logoutlink').addEventListener('click', function(){
        FB.logout();
    });
}

function indexWithAttribute(array, attr, value) {
    // Iterates over an array and returns the index of the element
    // whose attribute matches the given value. 
    for(var i=0; i < array.length; i++) {
        if(array[i][attr] === value) {
            return i;
        } 
    }
}

function showName(d) {
    // Displays given d3 node's 'name' attribute.
    document.getElementById('selected-friend-name').innerHTML = d['name'];
}

function getMutualFriends(id, friends, friendlinks) {
    // Retrieves a Facebook API object containing mutual friends
    // for a given user ID. Passes it to the getLinks() function.
    FB.api('/me/mutualfriends/' + id, function (response) {
        getLinks(response, id, friends, friendlinks); }
    );
}

function getLinks(response, id, friends, friendlinks) {
    // Calculates links between mutual friends and pushes them to an array.
    // Displays percent of friend links completed in 'load-status' div. 
    var mutualFriends = response['data'];
    var sourceIndex = indexWithAttribute(friends, 'id', id);

    var completed = Math.round(100*(sourceIndex/friends.length));

    document.getElementById('load-status').innerHTML = 'Calculating mutual friend links: ' + completed + '%'    
    for (i=0; i< mutualFriends.length; i++) {
            friends[sourceIndex]['value'] = mutualFriends.length;
            targetIndex = indexWithAttribute(friends, 'id', mutualFriends[i]['id']);
            friendlinks.push({'source':sourceIndex, 
                              'target':targetIndex,
                              'value':mutualFriends.length });
    }       

    if (sourceIndex === friends.length - 1) { 
        graphFriends(friends, friendlinks); }        
}

function getFriends(response) {
    // Loads friend nodes as an array. Creates array to hold links between mutual friends.
    var friends = response['data']
    var friendlinks = []

    for (i=0; i < friends.length; i++) {
        var id = friends[i]['id'];
        getMutualFriends(id, friends, friendlinks);
    }
}

function graphFriends(friends, friendlinks) {
    // Configures a d3 force-directed graph of friends and friend links.
    document.getElementById('load-status').innerHTML = ''

    // Set dimensions of svg
    var width = window.innerWidth - 100,
        height = window.innerHeight - 100;

    // Set up a 10-color scale for node colors
    var color = d3.scale.category10()

    // Set up a linear scale to map number of mutual
    // friends to node radius
    var r = d3.scale.linear()
                .domain([1,100])
                .range([5,15])

    // Set the initial parameters of the force() layout
    var force = d3.layout.force()
        .charge(-75)
        .linkDistance(40)
        .size([width / 1.2, height / 2])

    // Add svg and start visualization
    var svg = d3.select("#viz").append("svg")
        .attr("width", width)
        .attr("height", height);

    // Pass in friends array as graph nodes and friendlinks
    // array as graph edges.
    force.nodes(friends)
        .links(friendlinks)
        .start();

    var link = svg.selectAll("line.link")
        .data(friendlinks)
      .enter().append("line")
        .attr("class", "link")
        .style("stroke", "#eee")
        .style("stroke-width", 1);

    var node = svg.selectAll("circle.node")
        .data(friends)
      .enter().append("circle")
        .attr("class", "node")
        .attr("r", function(d) { return r(d.value); })
        .style("stroke", "#eee")
        .style("fill", function(d) { return color(d.value); })
        .on("mouseover", function(d) { showName(d); })
        .call(force.drag);

    force.on("tick", function() {
       link.attr("x1", function(d) { return d.source.x; })
           .attr("y1", function(d) { return d.source.y; })
           .attr("x2", function(d) { return d.target.x; })
           .attr("y2", function(d) { return d.target.y; });

       node.attr("cx", function(d) { return d.x; })
           .attr("cy", function(d) { return d.y; });
     });
}

index.html:

<!DOCTYPE html>
<html>
    <head>
        <script type="text/javascript" src="http://d3js.org/d3.v2.js"></script>
        <script type="text/javascript" src="http://connect.facebook.net/en_US/all.js">
        </script>
        <script type="text/javascript" src="friendgraph.js">        
        </script>
        <title>d3.js Facebook friend visualization</title>
    </head>
    <body>
        <div id="viz">
        </div>
        <div id="fb-root">
            <div><p>
                <h3>d3.js Facebook graph visualization</h3>
                by <a href="http://twitter.com/ecmendenhall">ecmendenhall</a></p>
            </div>
            <div id="selected-friend-name"></div>
            <div id="auth-status">
                <div id="auth-loggedout">
                    <a href="#" id="auth-loginlink">Login</a>
                </div>
            <div id="auth-loggedin" style="display:none">
          Logged in as <span id="auth-displayname"></span>  
        (<a href="#" id="auth-logoutlink">logout</a>)
            </div>
            <div id="load-status"></div>
        </div>
    </body>
</html>
\$\endgroup\$

2 Answers 2

9
\$\begingroup\$

I couldn't test out your application since I don't have a facebook account but here are some tips:

1) Use dot notation instead of bracket notation to access known property names.

Old Code:

friends[sourceIndex]['value'];

New Code:

friends[sourceIndex].value;

2) Keep the operations peformed within a loop to the bare minimum.

For performance, it's best to avoid nested loops and function calls within a loop.

From your code:

//...
function indexWithAttribute(array, attr, value) {
    for (var i = 0; i < array.length; i++) {
        if (array[i][attr] === value) {
            return i;
        }
    }
}
//...
function getLinks(response, id, friends, friendlinks) {
//...
    for (i = 0; i < mutualFriends.length; i++) {
        friends[sourceIndex]['value'] = mutualFriends.length;
        targetIndex = indexWithAttribute(friends, 'id', mutualFriends[i]['id']);
//...

The code above is bad for performance because the for loop contains calls to indexWithAttribute(), which contains another for loop. The deeply nested iterations will result in O(N^2) completion time.

One possible solution for this problem would be to create a hash table for the ids to index relationship. Hash tables take O(1) to find a value but require more memory, unlike a for loop O(n/2).

Code:

/**
* Returns a lookup table for the relationship (key)attribute to (value)index from an array of objects.
* This function expects that all referenced attributes will have a unique value.
* 
* @author Larry Battle <bateru.com/news>
* @param [Array] arr - An array of objects.
* @param [String] attr - A common property name amoung all the objects in `arr`.
* @returns [Object]
* @example

    var arr = [
        { id: 2 },
        { id: 12 },
        { id: 89 }
    ];
    var hash = createAttributeToIndexTable( arr, "id" );
    console.log( JSON.stringify( hash ) = '{"2":0,"12":1,"89":2}' );

**/
var createAttributeToIndexTable = function( arr, attr ){
    var hash = {};
    for( var i = 0, len = arr.length; i < len; i++ ){
        hash[ arr[i][attr] ] = i;
    }
    return hash;
};

Old code:

function getLinks(response, id, friends, friendlinks) {
    var mutualFriends = response['data'];
    var sourceIndex = indexWithAttribute(friends, 'id', id);
    var completed = Math.round(100*(sourceIndex/friends.length));

    document.getElementById('load-status').innerHTML = 'Calculating mutual friend links: ' + completed + '%'    
    for (i=0; i< mutualFriends.length; i++) {
            friends[sourceIndex]['value'] = mutualFriends.length;
            targetIndex = indexWithAttribute(friends, 'id', mutualFriends[i]['id']);
            friendlinks.push({'source':sourceIndex, 
                              'target':targetIndex,
                              'value':mutualFriends.length });
    }       
    if (sourceIndex === friends.length - 1) { 
        graphFriends(friends, friendlinks); 
    }        
}

New code:

var createAttributeToIndexTable = function( arr, attr ){
    var hash = {};
    for( var i = 0, len = arr.length; i < len; i++ ){
        hash[ arr[i][attr] ] = i;
    }
    return hash;
};
function getLinks(response, id, friends, friendlinks) {
    var mutualFriends = response.data;
    var idToIndexTable = createAttributeToIndexTable( friends, 'id' );
    var sourceIndex = idToIndexTable[id];
    var completed = Math.round(100 * (sourceIndex / friends.length));
    document.getElementById('load-status').innerHTML = 'Calculating mutual friend links: ' + completed + '%'
        for (i = 0; i < mutualFriends.length; i++) {
            friends[sourceIndex].value = mutualFriends.length;
            targetIndex = idToIndexTable[ mutualFriends[i].id ];
            friendlinks.push({
                'source' : sourceIndex,
                'target' : targetIndex,
                'value' : mutualFriends.length
            });
        }
        if (sourceIndex === friends.length - 1) {
            graphFriends(friends, friendlinks);
        }
}

3) Add a small delay to avoid locking up the webpage. Or use webworkers.

Old Code:

function getMutualFriends(id, friends, friendlinks) {
    FB.api('/me/mutualfriends/' + id, function (response) {
        getLinks(response, id, friends, friendlinks);
    });
}

New Code:

function getMutualFriends(id, friends, friendlinks) {
    FB.api('/me/mutualfriends/' + id, function (response) {
        setTimeout(function(){
            getLinks(response, id, friends, friendlinks);
        }, 100);
    });
}

Note:

Find a way to simplify this section. I think there might be a way to append a clone of a line without recreating it everytime.

Code:

force.nodes(friends).links(friendlinks).start();
var link = svg.selectAll("line.link").data(friendlinks).enter().append("line").attr("class", "link").style("stroke", "#eee").style("stroke-width", 1);
var node = svg.selectAll("circle.node").data(friends).enter().append("circle").attr("class", "node").attr("r", function (d) {
        return r(d.value);
\$\endgroup\$
0
1
\$\begingroup\$

You can also reduce the memory load and increase effeciency by converting your objects into arrays and accessing them with indexes.

Instead of:

var data = [
   { 
        source : {
           x: 101,
           y: 242
       }
       target : {
           x : 353,
           y : 456
       }
       x : 555,
       y : 654
   },
   ...
]

use

var data = [
  [101,242,353,356,555,654],
  ...
]

This does decrease readability but if you want to make things clearer you can use variables to represent the indexes, something like:

var i_source_x = 0,
    i_source_y = 1,
    i_target_x = 2,
    i_target_y = 3,
    i_x = 4,
    i_y = 5;

data[0][i_source_x] === 101 // true
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.