0
\$\begingroup\$

As far as I know there is no standard method yet of maintaining keyword-value pairs. I'm certain most implementations would come to a screeching halt given my number crunching requirements. The blogged benchmarking I've seen of the different methods range from dismal loops to object[keyword] dominance, but they're for static data.

My dynamic data HashCompactor() algorithm has been gathering dust at SourceForge since 2006, but when I recently raced it against the built-in methods, I'm always neck and neck with o[k], sometimes even beating it. I designed HashCompactor to be fast, and it looks like it's even faster than I imagined. Tool, weapon, whatever you want to call it: here it is; have fun. There's a busking tip jar if anyone cares.

I've hosted the HashCompactorLite() version of my algorithm at JSFiddle.

Here's a simple implementation where a list of image file extensions is compared to a url. In this case each keyword's data in exts is an array of length 1. If ext === 'html', then .item() will return null after being unable to find 'h' among ['j','g','t','p','f']. Of that initial list of 15, this possible worst case scenario only concerns itself with 5 of them.

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

In my WebLogHog implementation of HashCompactor, I'm analyzing website Log Format files. In this example, the nested .sort() functionality begins with this.referrers being a HashCompactor object before returning as a sorted Array. The optional second parameter to HashCompactor's .sort() routine preprocesses the data.

// compress duplicates and sort by most common; report total count for each
time = performance.now();
this.referrers = this.referrers.sort(function(a,b) {
      let _a = a.count, _b = b.count;
      if (_a > _b) return -1;
      if (_b > _a) return 1;
      return 0;
  }, function(keyword,data,arrayToFill) {
      let hc = new HashCompactor(),
          count = data.length;
      for (let i=0; i < count; i++) {
        hc.add(data[i]);
      }
      data = []; // used by .forEach() below
      hc.sort(function(a,b) {
          let _a = a.count, _b = b.count;
          if (_a > _b) return -1;
          if (_b > _a) return 1;
          return 0;
        }, function(keyword2,data2,arrayToFill2) {
            // keyword2, data2, arrayToFill2 for readability, but scope protects them
            arrayToFill2.push({
                keyword: keyword2,
                count: data2.length
            });
      }).forEach(function(e,i,l) {
          // data [] from above
          data.push(e.keyword + " (" + e.count + ")");
      });
      arrayToFill.push({
          keyword: keyword,
          data: data,
          count: count
      });
  });
time = performance.now() - time;
console.log(" sort referrers: " + time);

I first started talking about my algorithm back in the early 1990s, but geopolitical concerns have made bringing it to fruition among civilians that much more difficult. Here's the gist of the routine.

HashCompactorLite(optional HashCompactorLite object OR Array of Strings) creates (a copy of) a HashCompactorLite object, or if an array is provided, .add() each item as a keyword.

.add(keyword,optional datum) returns an array of data. Multiple calls to the same keyword pushes the datum onto the array. Undefined datum works well for calculating word counts or simple comparisons against a list. The keyword can be either a String, a Number converted to a String (to take advantage of 1 being the most common number), or an array of String objects (such as names of modules).
.count(optional show data count) return number of keywords or total data items if parameter is true, features object[keyword] doesn't offer.
.item(keyword) returns the keyword's data array, otherwise null.
.set(keyword,data,optional combine data) sets the keyword's data array, either overriding what may have existed, or combining to any existing data if true.
.forEach(callback,optional thisp) iterates through each keyword calling the callback function with the parameters (keyword,data) in the this context provided.
.sort(comparison function,optional preprocessor function,optional partial keyword, optional thisp) returns an array of keywords sorted after preprocessing HashCompactor data into an array for comparisons using the preprocessor parameteters (keyword,data,arrayToFill). If the partial keyword is 'a', for example, only the keywords beginning with 'a' will be returned.
.copy(HashCompactorLite object OR Array of keywords) deletes this HashCompactorLite and replaces it with a copy, or if an array of keywords is provided, .add() each one.
.clear() deletes internal objects created by HashCompactor
.deleteKeyword(keyword) Removes keyword from HashCompactor. See .add() for keyword requirements.

[Edit] I've been turned onto the Map() feature that flew in under my radar and internalized the character searches using it, but it didn't seem to speed up the WebLogHog stress test.

I'm still dedicated to the read-once keyword searching, especially since I'm envisioning the six-foot-long keywords that is DNA. Having designed a real time MIDI-to-music staff notation spelling algorithm back in the early 1990s, I'm into reading data bit by bit. I'm just not up to speed with the world of software engineering.

\$\endgroup\$
  • 3
    \$\begingroup\$ I'm a bit confused, you say there is no standard method of maintaining key-value pairs but doesn't the ES2015 Map class do just that (or the Set class for your first use case) ? \$\endgroup\$ – Marc Rohloff May 26 '17 at 4:18
  • \$\begingroup\$ I'm no expert in this. Think of me more like an inventor who has just come out of my lab after a very long time, googled what's the fastest way to find keywords, and be shown a benchmark that mine sometimes beats. Unfamiliar with Map and Set, I will have to look into it. \$\endgroup\$ – Kevin Crosby May 26 '17 at 18:47
  • \$\begingroup\$ map iterates over the entire array, so I'm not sure where I'd use it in my algorithm right offhand. Set looks interesting; I'd like to see some examples. It might help if I explain how HashCompactor works. Keywords are stored in a tree structure: all keywords that begin with 'a' link from that node. Looking for a keyword that begins with 'b' would search an entirely different set of branches. Each node contains a list of following characters, so basically tons of single character arrays until I can figure out a way to change that without adding too much complexity. \$\endgroup\$ – Kevin Crosby May 26 '17 at 19:04
  • \$\begingroup\$ WebLogHog makes thousands of searches for keywords. I'd be more than interested to see it try to use a different implementation for keyword-value storage. Keep in mind that one website visitor might generate 100 keyword searches over a timespan such that the number of keywords has changed in between, so static array methods that must build the keyword list with each change don't stand a chance against my code. \$\endgroup\$ – Kevin Crosby May 26 '17 at 19:17
  • 1
    \$\begingroup\$ Note I said Map not map (developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/…) \$\endgroup\$ – Marc Rohloff May 26 '17 at 22:45
1
\$\begingroup\$

[...] when I recently raced it against the built-in methods, I'm always neck and neck with o[k], sometimes even beating it.

As already pointed out, you need a more sophisticated approach to testing runtime performance of runtime-optimized code produced by modern JavaScript engines.

I compared the performance of your datastructure against the built-in Map as well as plain objects {} on the well-known performance testing playground jsperf.com based on the benchmark.js library and got the following results on Firefox 53 / Ubuntu:

Insertion:
  Object         10,333,390 Ops/sec
  Map             1,970,404 Ops/sec
  HashCompactor      85,865 Ops/sec

Lookup:
  Object        171,500,573 Ops/sec
  Map             6,138,718 Ops/sec
  HashCompactor   2,300,471 Ops/sec

Source: https://jsperf.com/hashcompactor-vs-map/1

I used the following insertion function to allow for multiple values per Map key:

function add(map, key, value) {
  var values = map.get(key);
  if (values) values.push(value);
  else map.set(key, [value]);
  return map;
}

The above results show that - for the given exemplary scenarios and tested JavaScript engine - the built-in plain object and Map have superior performance compared to HashCompactor. The differences between object and Map are either explained by more aggressive optimization regarding objects (complete removal of statements without side-effects) or the function call overhead which is huge compared to simple property lookup on microbenchmarks such as this.

This practical measurement can be explained by analyzing the computational complexity of the involved operations:

An object or Map is usually backed by some kind of hash-table with constant time insertions and lookups. Appending values to an array is also a constant time operation.

Now, it is impossible to complete an operation in less than constant time. So all you can improve is the constant. Which is a hopeless endeavor, as you are now competing with self-made prefix-tree lookups against highly optimized built-in hash-tables.

However: If you have more knowledge about the original problem you want to solve, you can come up with a more specialized and thus faster algorithm. One of your comments says that you actually need to perform "thousands of searches for keywords". In this case - if the list of keywords remains mostly constant over some time - you should have a look at the Aho–Corasick algorithm.

\$\endgroup\$
  • \$\begingroup\$ Here's numbers I'm getting from WebLogHog - After the operating system took 6.776 seconds to load 41 files, WebLogHog crunched the 68.9 MB of raw data in 11.97 seconds importing and sorting 277,689 Extended Log File entries from 57,576 IP Addresses (i.e. keywords). \$\endgroup\$ – Kevin Crosby May 26 '17 at 22:39
  • \$\begingroup\$ When I first coded this, none of the available software would sort by bandwidth hogs. \$\endgroup\$ – Kevin Crosby May 27 '17 at 0:20
  • 1
    \$\begingroup\$ When did they add the Map object? I must get out more often. \$\endgroup\$ – Kevin Crosby May 27 '17 at 17:17
  • 1
    \$\begingroup\$ Doesn't object[keyword] risks collisions or is that just object.keyword which has a whole slew of other problems as well? o[k] requires manually counting keywords. HashCompactor keeps count, though manually counts values. Hmm... maybe if I post the need I can find a better solution: stress the examples needed. \$\endgroup\$ – Kevin Crosby May 27 '17 at 23:21
  • 1
    \$\begingroup\$ @KevinCrosby AFAIK you built a trie - which is a valuable datastructure in itself and has no built-in equivalent. So I wouldn't call it superfluous just because it is not the best tool for the specific task at hand. Perhaps don't try to build an all-in-one solution, but split your code into different modules / components which solve different, specialized tasks. Regarding counting - for Map there is map.size and for objects you could try Object.keys(obj).length or manually keep track of the number of properties / keys. There is no collision risk. \$\endgroup\$ – le_m May 28 '17 at 0:00

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.