Efficient object initialization

Question

I am creating a mock Twitter project which loads user data from a somewhat large text file containing ~3.6 million lines formatted like this:

The first string token is the userId and the second is the followId.

The first half of this helper method takes in the current user's ID, checks to see if it exists and creates a new user if necessary. After that, the followId is added to this new or existing user's following list of type ArrayList<Integer>.

With ~3.6 million lines to read, this doesn't take long (9868 ms).

Now the second half creates or finds the followed user (followId) and adds the userId to their followers list, but this additional code extends the amount of time to read the file exponentially (172744 ms).

I tried using the same TwitterUser object throughout the method. All of the adding methods (follow, addFollower) are simple ArrayList.add() methods. Is there anything I can do to make this method more efficient?

Please note: While this is school-related, I'm not asking for an answer to my solution. My professor permitted this slow object initialization, but I'd like to understand how I can make it faster.

private Map<Integer, TwitterUser> twitterUsers = new HashMap<Integer, TwitterUser>();

private void AddUser(int userId, int followId){
    TwitterUser user = getUser(userId);
    if (user == null){
        user = new TwitterUser(userId);
        user.follow(followId);
        twitterUsers.putIfAbsent(userId, user);
    } else{
        user.follow(followId);
    }
    //adding the code below, slows the whole process enormously
    user = getUser(followId);
    if (user == null){                     
        user = new TwitterUser(followId);
        user.addFollower(userId); 
        twitterUsers.putIfAbsent(followId, user);
    } else{
        user.addFollower(userId);
    }
}

private TwitterUser getUser(int id){
    if (twitterUsers.isEmpty()) return null;
    return twitterUsers.get(id);
}

You don't have to check if twitterUsers.isEmpty() in #getUser, Map#get returns null if the specified key is not found. This won't substantially reduce runtime but it is redundant. Could you also post the TwitterUser#follow and TwitterUser#addFollower code? — Jonny Henly
– Jonny Henly, Commented Apr 23, 2016 at 3:46
well if putIfAbsent is a HashMap method and follow is simply: 1.) check if !ArrayList.contains(int) ... 2.) ArrayList.add(int) @JonnyHenly — terbubbs
– terbubbs, Commented Apr 23, 2016 at 3:46
Sorry about that, I didn't realize putIfAbsent was a method of HashMap. Have you considered using another HashMap instead of an ArrayList, since the lookup time for an ArrayList is linear? — Jonny Henly
– Jonny Henly, Commented Apr 23, 2016 at 3:48
@JonnyHenly oh jeez, that makes sense. I will certainly look into that! — terbubbs
– terbubbs, Commented Apr 23, 2016 at 3:50

Angelo Oparah · Accepted Answer · 2016-04-23 06:45:05Z

If putIfAbsent(int, User) does what you would expect it to do, that is: checking if it's there before inserting, why do you use it within an if block whose condition already checks if the user is there?

In other words, if fetching a user returned a null value you can safely assume that the user was not there.

Now I'm not too sure about the internal workings of the *putIfAbsent* method (probably it would loop through the set of the keys in the map), but intuitively I would expect a normal put(int, User) to perform better, even more with a map that gets as large as yours as the input file gets scanned through.

Therefore I would suggest to try something like:

user = getUser(followId);
if (user == null){                     
    user = new TwitterUser(followId);
    user.addFollower(userId); 
    twitterUsers.put(followId, user);
 } else{
    user.addFollower(userId);
 }

which would apply to the first half as well.

Collectives™ on Stack Overflow

Efficient object initialization

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related