Looking for matching names among two text files

Question

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?

Answer 1

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();
  });
}

Answer 2

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.