title: UnderscoreJS find-and-replace
body: <p>In my application, I have a very large array of objects on the front-end, and these objects all have some kind of long ID under the heading ["object_id"]. I'm using UnderscoreJS for all my manipulations of this list. This is a prototype for an application that will eventually be handling most of this effort on the backend.</p>
  
  <p>Merging the list is a big part of the application's requirement. See, the list that I work with initially will have many distinct objects with identical object_ids. Initially I was merging them all in one go with a groupBy and a map-reduce, but now the requirements have changed and I'm merging them one at a time (about a second apart, to simulate a stream of input) into a initially empty array.</p>
  
  <p>My naive implementation was something like this:</p>
  
  <pre><code>function(newObject, objects) {
      var obj_id = newObject["object_id"]; //id of object to merge, let's say
      var tempObject = null;
      var objectToMerge = _.find(objects,
          function(obj) {
              return obj_id == obj["object_id"];
          });
      if (objectToMerge) {
          tempObject = merge(objectToMerge, newObject);
          objects = _.reject(objects, /*same function as findWhere*/ );
      } else {
          tempObject = newObject;
      }
      objects.push(tempObject);
      return objects;
  }
  </code></pre>
  
  <p>This is ridiculously more efficient than before, when I was remerging from the mock data "source" array every time a new object was supposed to be pushed, so it's down from what I think was O(N^2) at least to O(N), but N here is so large (for JavaScript, anyway!) I'd like to optimize it. Currently worst case, where the object_id is not redundant, is the entire list is traversed twice. So what I'd like is to do a find-and-replace, an operation which would return a new version of the list, but with the merged object in place of the old one.</p>
  
  <p>I could do a map where the iterator returns a new, merged object iff the object_id is the same, but that doesn't have the short-circuit evaluation that _.find has, which means the difference between having a worst-case runtime and having that be the default runtime, and doesn't easily account for pushing the object if there wasn't a match.</p>
  
  <p>I'd also like to avoid mutating the original array in place. I know objects.push(tempObject) does that very thing, but for data-binding reasons I'm ignoring that and returning the mutated list as though it were new.</p>
  
  <p>It's also unavoidable that I'll have to check the array to see if the new object was merged or whether it was appended. Using closures I could keep track of a flag to see if the merge happened, but I'm trying to be as idiomatically LISPy as possible for my own sanity. Also, past a certain point, most objects will be merged, so extra runtime overheard for adding new items isn't a huge problem, as long as it is only incurred when it has to happen.</p>