3 Replies - 293 Views - Last Post: 13 May 2017 - 08:16 PM

#1 Skews.Me  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 13-May 17

Building a better (keyword-value pair) mousetrap

Posted 13 May 2017 - 01:21 PM

Back in the early 1990s when I was just starting to learn C, I had this idea for a keyword-value pair algorithm that uses a tree structure to store the keywords, but it wouldn't be until the early 2000s that I'd realize the code while learning Javascript, and getting it accepted by SourceForge in 2006. At the time, I had HashCompactor analyzing website Log Format files by IP Address bandwidth usage, a feature I couldn't find elsewhere. Recently I rewrote the code, adding more bells and whistles, and then I found a benchmarking platform to discover my dynamic indexing is almost as fast and sometimes even faster than the leading but limited object[keyword] lookup method.

Here's a simple example of HashCompactor's use where it compares a filename extension to one of the known extension types.

var exts = new HashCompactor(['jpeg', 'jpg', 'jif', 'jfif', 'gif', 'tif', 'tiff', 'png', 'pdf', 'jp2', 'jpx', 'j2k', 'j2c', 'fpx', 'pcd']);
var ext = extFromURL(url);
if (!! exts.item(ext)) {
  displayImage(url);
}


I've created a couple of scripts testing a scaled down version of my algorithm at JSFiddle which also links to the benchmarking.


I know HashCompactor provides solutions for common tasks. Here's an example (give or take some strange DreamInCode formatting bugs) where I fill a HashCompactor object with data and then sort it by a property required of that data, all encapsulated into a simple procedure.

  // Calculate grade point averages and then sort from highest to lowest
  var hashCompactor = new HashCompactor(), data = [], previousName = "",
      grades = [{ name:'Lorem Alpha',subject:'math',grade:3.0 },{ name:'Ipsum Bravo',subject:'english',grade:3.5 },
                { name:'Ipsum Bravo',subject:'math',grade:3.0 },{ name:'Sit Delta',subject:'english',grade:3.7 },
                { name:'Dolor Charlie',subject:'math',grade:2.8 },{ name:'Lorem Alpha',subject:'english',grade:3.0 },
                { name:'Sit Delta',subject:'math',grade:4.0 },{ name:'Amet Epsilon',subject:'english',grade:1.7 },
                { name:'Amet Epsilon',subject:'math',grade:3.5 },{ name:'Dolor Charlie',subject:'english',grade:2.6 }];
  
  // Fill the hashCompactor with data
  grades.forEach(function(e,i,l) {
      if (e.name != previousName) {
        data = hashCompactor.add(e.name, e);
        previousName = e.name;
      } else {
        data.push(e);
      }
  });
  // Sort hashComapactor
  hashCompactor.sort(function(a,B)/> {
      var _a = a.gpa, _b = b.gpa;
      if (_a > _B)/> {
        return -1;
      }
      if (_a < _B)/> {
        return 1;
      }
      return 0;
    }, function(keyword,data,arrayToFill) { // optional preprocessor
      var gpa = 0.0;
      data.forEach(function(e,i,l) { gpa += e.grade; });
      gpa /= data.length;
      arrayToFill.push({
          name: keyword,
          gpa: gpa.toPrecision(3)
      });
    }).forEach(function(e,i,l) {
      if (i > 0) {
       //document.write(', ');
      }
      console.log(e.name + ' - gpa: ' + e.gpa);
      //document.write(e.name + ' - gpa: ' + e.gpa);
  });
  //document.write("<br/><br/>");


It's like I built a hot rod in my virtual garage using some new-fangled engine type that wants to be raced, and I'm now looking for drivers.

Is This A Good Question/Topic? 0
  • +

Replies To: Building a better (keyword-value pair) mousetrap

#2 Skews.Me  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 13-May 17

Re: Building a better (keyword-value pair) mousetrap

Posted 13 May 2017 - 02:02 PM

Someone from the back row is asking, "What kind of tires do you have on that hot rod of yours?"

The HashCompactor .add(keyword,datum) optional second argument allows .add("the") for simple word counts. Keyword may be either a string, a number which will convert to a string (which can take advantage of 1 being the most common number), or an array of strings (as one might find among module names).

The HashCompactor constructor can receive another HashCompactor object or an array of keyword strings to add individually. Remind me to add an optional parameter to the constructor so I can match .add()'s capabilities.

To the coder in the back row, "Still driving on storebought."
Was This Post Helpful? 0
  • +
  • -

#3 Skews.Me  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 13-May 17

Re: Building a better (keyword-value pair) mousetrap

Posted 13 May 2017 - 02:19 PM

Here's some benchmark results for HashCompactor versus object[keyword]. Apparently object.keyword is much faster than both, but requires munging the keyword if it begins with a number. HashCompactor is also more versatile as it includes a .count() property while both o[k] and o.k would require counting them by hand. HashCompactor also maintains a steady state.

Number of objects 32,767  Number of searches 32,767
HashCompactor.item(keyword) Average 0.003214972380749695
HashCompactor.item(keyword) Average 0.002366252632221174
HashCompactor.item(keyword) Average 0.0016382335886708165
HashCompactor.item(keyword) Average 0.0016428113650937871
HashCompactor.item(keyword) Average 0.0025873592333765885
HashCompactor.item(keyword) Average 0.0016620380260648343
HashCompactor.item(keyword) Average 0.001636860255748558
HashCompactor.item(keyword) Average 0.003652760399180343
HashCompactor.item(keyword) Average 0.002162846766561725
HashCompactor.item(keyword) Average 0.0016579180272860677

object[keyword] Average 0.001410718100527912
object[keyword] Average 0.0009884945219281558
object[keyword] Average 0.0016626483962546175
object[keyword] Average 0.0009663686025558123
object[keyword] Average 0.000984527115694455
object[keyword] Average 0.0009584337900924073
object[keyword] Average 0.0009573656422565606
object[keyword] Average 0.0014760277108069862
object[keyword] Average 0.0009477523117781564
object[keyword] Average 0.001691030610064889

Was This Post Helpful? 0
  • +
  • -

#4 Skews.Me  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 13-May 17

Re: Building a better (keyword-value pair) mousetrap

Posted 13 May 2017 - 08:16 PM

	// Accepts a string, a number that it converts to a string, or an array of strings
  add: function(keyword /* ,datum */) { // ASSERT(keyword !== "")
    var child = this,
        keyOp = new HashCompactorKeywordIterator(keyword);
    keyOp.forEach(function(character) {
      child = this._add(child,character);
    },this);
    if (keyOp.isArray) {
      child._isArray = true;
    }
    if (child._data) {
      child._data.push(arguments[1]);
    } else {
      child._data = [arguments[1]];
      child._referenceCount = 1;
      var parent = child._parent;
      if (parent) {
        do {
          parent._referenceCount++;
        } while (parent = parent._parent);
      }
    }
    return child._data;
  },
  _add: function(node,character) {
    var child;
    if (node.children) {
      child = this._findChild(node,character);
      if (child) {
        return child;
      }
      child = {
         character: character,
         _parent: node,
         _referenceCount: 0
      };
      node.currentChildIndex = node.children.push(child)-1;
    } else {
      child = {
         character: character,
         _parent: node,
         _referenceCount: 0
      };
      node.children = [child];
      node.currentChildIndex = 0;
    }
    return child;
  },


Was This Post Helpful? 0
  • +
  • -

Page 1 of 1