1
\$\begingroup\$

I'm trying to enhance the execution speed of my below code. I am using only vanilla JavaScript. I would be willing to bring in additional libraries and plugins as long as they will enhance the overall speed of the code.

The goal is to have the absolute fastest execution time of the below code.

Currently, it executes from start to finish in approx. 320 - 350 ms. I want to make any modifications necessary to make it perform faster than that, particularly with exponentially larger datasets.

Setup

  • I have two .txt files, names and data.
  • names contains a list of last names, one name per line:

    Nader
    Sanford
    Kovacek
    Lynch
    etc...
    
  • data contains a much longer list, of first names, last names, a comma and a value:

    Kailee Huel,2
    Arianna Runolfsson,4
    Marshall Kuhn,3
    Cristina Huel,4
    Garnett Medhurst,3
    etc...
    

Task

Iterate through data.txt using the last names in names.txt. If any of the last names from names.txt have a match in data.txt, increment a counter with the value on that line (after the comma). Some last names are repeated in both names.txt and data.txt. Output the final value of the counter.

<script type="text/javascript">

  var names,
  data;

    // doc rdy
    document.onreadystatechange = function(){
      console.time('execution length');
      if( document.readyState == "complete" ){
        init();
      }
    }

    // setup
    function init(){
      var base      = "data/sample2/",
          namesFile = base+"names.txt",
          dataFile  = base+"data.txt";

      loadFile(namesFile, function(e){
        names = e;
        loadFile(dataFile, function(ev){
          processData(ev);
        });
      });
    }


    function processData(e){
      var counter = 0;
      var namesProcessed = {};

      // for each last name,
      for( var i=0; i<names.length; i++ ){
        // if "data object" contains "this name" AND "this name" does not exist in rmvdNames, add its val to counter
        if( e.hasOwnProperty(names[i]) && ! namesProcessed.hasOwnProperty(names[i]) ){
          counter += e[names[i]];
          namesProcessed[names[i]] = true;
        }
      }
      console.log(counter);
      console.timeEnd('execution length');
    }


    // ajax loading
    function loadFile( filename, callback ){
      var client = new XMLHttpRequest();
      var result;
      client.open('GET', filename);
      client.onreadystatechange = function() {
        if( client.readyState==4 && client.status==200 ){
          result = client.responseText.split("\n");
          // custom handling for the data set..
          if( result[0].search(',') !== -1 ){
            result = arrCSVtoObj(result);
          }

          callback(result);
        }
      }
      client.send();
    }


    // converts an array of CSV to a key:value object
    function arrCSVtoObj(csvArr) {
      var obj = {};

      // for each line in the array,
      for( var i=0; i<csvArr.length; i++ ){
        // split into key:value on comma
        var split = csvArr[i].split(",");
        var key =  getLastName(split[0]);
        var val = parseInt(split[1]);

        // assign the new property to the object
        if( ! obj.hasOwnProperty(key) ){
          if( val > 0 ){
            obj[key] = val;
          }
        }else{
          obj[key] += val;
        }
      }
      return obj;
    }

    function getLastName(e){
      var nameArr = e.split(" ");
      return nameArr[1];
    }

  </script>

I know the biggest time sink in this script are the loops (there are several: looping through object properties, looping through data to parse it, etc). How can I speed these actions up? What measures can I take to improve the above code and optimize absolute speed with large datasets?

\$\endgroup\$
3
  • \$\begingroup\$ Is this an exercise? Real people have multi part family names. \$\endgroup\$ – konijn Jul 14 '14 at 18:30
  • \$\begingroup\$ @konijn: yes it is just an exercise. It'd need to be more robust for cases like you stated. :) \$\endgroup\$ – tdc Jul 14 '14 at 19:29
  • \$\begingroup\$ Normally, in US, programs like this will add all last names to LAST_NAME, or else add all but the very last name to FIRST_NAME in cases like this. \$\endgroup\$ – Nate T Jun 19 at 0:15
2
\$\begingroup\$

The first thing that really jumped out at me is your loadFile method is using synchronous http requests (looks accidental as you're using a callback anyway, see msdn for why this should be avoided etc).

Instead of client.open('GET', filename); you probably want client.open('GET', filename, true);

Making async requests will allow the first notable improvement I would make is to make init loading async. I'm going to use the native promises -- feel free to adapt

// setup
function init() {
  var base = "data/sample2/",
    namesFile = base + "names.txt",
    dataFile = base + "data.txt";

  Promise.all([loadFile(namesFile), loadFile(dataFile)])
  .then(function(values) {
    var names = values[0];
    processData(values[1]);
  });
}

// ajax loading
function loadFile(filename) {
  return new Promise(function(resolve, error) {
    var client = new XMLHttpRequest();
    client.open('GET', filename, true);
    client.onreadystatechange = function() {
      if (client.readyState == 4 && client.status == 200) {
        var result = client.responseText.split("\n");
        // custom handling for the data set..
        if (result[0].search(',') !== -1) {
          result = arrCSVtoObj(result);
        }
        resolve(result);
      }
    };
    client.send();
  });
}
\$\endgroup\$
2
\$\begingroup\$

I ran the script ten times on this names.txt (3580 lines, 29.6 KiB) and this data.txt (500k lines, 8.3 MiB). names.txt contains about 300 duplicated names, and about 2000 unused last names. About 70% of the last names in data.txt do not have a corresponding entry in names.txt.

Your code ran in 832.7 ms on average over ten trials.

I made the following changes in arrCSVtoObj:

  • Don't check obj.hasOwnProperty when incrementing. Saved 71.1 ms.
  • Match against a precompiled regexp. Saved 320.9 ms.

This gave me a final speed of 440.7 ms, making for savings of 47%! I also tried filtering out duplicates beforehand, but for this case, it actually slowed it down to 486.9 ms.

(Edit: As @megawac asked, here's a jsperf. I also included one with smaller test cases; you'll notice that the relative difference in speed is much less.)

Here's the final function. You may notice that I explicitly specified the base in the parseInt; this is just in case the data file contains something like John Doe,011, where the 011 would parse to 9.

function arrCSVtoObj(csvArr) {
    var obj = {};
    var delims = / (.+),(.+)/;

    for (var i = 0; i < csvArr.length; i++) {
        // our match may fail (empty line); just silently ignore.
        var split = csvArr[i].match(delims);
        if (!split) continue;

        var key = split[1];
        var val = parseInt(split[2], 10);

        obj[key] = val + (obj[key] || 0);
    }
    return obj;
}

Combine this with @megawac's answer and you should notice huge savings.

\$\endgroup\$
7
  • \$\begingroup\$ How were you benchmarking. Could you create a jsperf? Is the last name valueOf or toString (etc) a valid last name? \$\endgroup\$ – megawac Jul 13 '14 at 21:41
  • \$\begingroup\$ Also skimming, it would be obj[key] = val + obj[key] || val; . However if val can be negative this might be trouble. Maybe if (typeof object[key] == "number") /* ... */ would be better.... Perhaps (object[key] || 0) + val would work too \$\endgroup\$ – megawac Jul 13 '14 at 21:47
  • \$\begingroup\$ @megawac I actually just forgot operator precedence, haha. Added the parentheses. As for benchmarking, I just added a callback in the processData function and used performance.now() rather than console.time(). I don't see the value in adding that here. I guess I could write a jsperf. \$\endgroup\$ – Schism Jul 13 '14 at 22:35
  • \$\begingroup\$ thanks for the awesome input, both of you! this has definitely sped performance up. What would be a good way to make this code still workable in Safari and IE (which don't support Promises)? \$\endgroup\$ – tdc Jul 14 '14 at 0:15
  • \$\begingroup\$ @user49060 You'll want to tag megawac so he gets a notification. I got one automatically because you commented on my post. \$\endgroup\$ – Schism Jul 14 '14 at 1:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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