Click here to Skip to main content
14,032,634 members
Click here to Skip to main content
Add your own
alternative version

Stats

6.8K views
4 bookmarked
Posted 19 Nov 2013
Licenced MIT

Would JavaScript Benefit from a Dictionary Object

, 19 Nov 2013
Rate this:
Please Sign up or sign in to vote.
Would JavaScript benefit from a Dictionary Object

Introduction

In my last project, I was tasked with creating a browser client application that would read 10s of thousands of rows of data, then group and aggregate the data for display in grids and for charting. The target technologies were HTML 5, CSS 3 and EMCS 5 (modern browser in Jun 2013). Because older browser compatibility was not a concern, the external libraries were limited to D3 (no JQuery).

I needed to build a data model. I had built one before in C# and relied on custom dictionary objects to quickly access the data, groups, and aggregates. I had not worked in JavaScript in years so I started searching for a dictionary. I found JavaScript still did not have a true native dictionary. I found a few sample implementations but nothing that really met my expectation. So I built one.

As I mentioned, I had not worked in JavaScript for years. The advancements (or maybe just the web availability of information) were quite impressive. All my previous work was with class based languages so the prototype based language took some time to get used to (and I still have a long way to go).

This project, like most, was due before it started so I learned as I went making many of the newbie mistakes that would be expected when transitioning from a class based to a prototype based language. The dictionary created was functional but after a time, I realized some improvements I could make by making it less newbish. The project ran out of funding before I had time to rework the dictionary. Oh, and my position lost funding at the same time (amazing how that can happen). So I decided to recreate the dictionary using what I had learned and determine if the dictionary was actually a performance improvement over an array.

/*
* Dictionary Factory Object
* Holds common object functions. similar to V-Table
* this.New() used to create new dictionary objects
* Uses Object.defineProperties so won't work on older browsers.
* Browser Compatibility 
* (https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Object/defineProperties)
*      Firefox (Gecko) 4.0 (2), Chrome 5, IE 9, Opera 11.60, Safari 5
*/
function Dict() {
 
    /*
    * Create a new Dictionary
    */
    this.New = function () {
        return new dict();
    };
 
    /*
    * Return argument f if it is a function otherwise return undefined
    */
    function ensureF(f) {
        if (isFunct(f)) {
            return f;
        }
    }
 
    function isFunct(f) {
        return (typeof f == "function");
    }
 
    /*
    * Add a "_" as first character just to be sure valid property name
    */
    function makeKey(k) {
        return "_" + k;
    };
 
    /*
    * Key Value Pair object - held in array
    */
    function newkvp(key, value) {
        return {
            key: key,
            value: value,
            toString: function () { return this.key; },
            valueOf: function () { return this.key; }
        };
    };
 
    /*
    * Return the current set of keys. 
    */
    function keys(a) {
        // remove the leading "-" character from the keys
        return a.map(function (e) { return e.key.substr(1); });
        // Alternative: Requires Opera 12 vs. 11.60
        // -- Must pass the internal object instead of the array
        // -- Still need to remove the leading "-" to return user key values
        //    Object.keys(o).map(function (e) { return e.key.substr(1); });
    };
 
    /*
    * Return the current set of values. 
    */
    function values(a) {
        return a.map(function(e) { return e.value; } );
    };
 
    /*
    * Return the current set of key value pairs. 
    */
    function kvPs(a) {
        // remove the leading "-" character from the keys
        return a.map(function (e) { return newkvp(e.key.substr(1), e.value); });
    }
 
    /*
    * Returns true if key exists in the dictionary.
    * k - Key to check (with the leading "_" character) 
    */
    function exists(k, o) {
        return o.hasOwnProperty(k);
    }
 
    /*
    * Array Map implementation
    */
    function map(a, f) {
        if (!isFunct(f)) { return; }
        return a.map(function (e, i) { return f(e.value, i); });
    }
 
    /*
    * Array Every implementation
    */
    function every(a, f) {
        if (!isFunct(f)) { return; }
        return a.every(function (e, i) { return f(e.value, i) });
    }
 
    /*
    * Returns subset of "values" where function "f" returns true for the "value"
    */
    function filter(a, f) {
        if (!isFunct(f)) {return; }
        var ret = a.filter(function (e, i) { return f(e.value, i); });
        // if anything returned by array.filter, then get the "values" from the key value pairs
        if (ret && ret.length > 0) {
            ret = values(ret);
        }
        return ret;
    }
 
    /*
    * Array Reverse implementation
    */
    function reverse(a, o) {
        a.reverse();
        reindex(a, o, 0);
    }
 
    /**
    * Randomize array element order in-place.
    * Using Fisher-Yates shuffle algorithm.
    */
    function shuffle(a, o) {
        var j, t;
        for (var i = a.length - 1; i > 0; i--) {
            j = Math.floor(Math.random() * (i + 1));
            t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
        reindex(a, o, 0);
        return a;
    }
    /*
    * Array Some implementation
    */
    function some(a, f) {
        if (!isFunct(f)) { return; }
        return a.some(function (e, i) { return f(e.value, i) });
    }
 
    /*
    * Sort the dictionary. Sorts the array and reindexes the object.
    * a - dictionary array
    * o - dictionary object
    * sf - dictionary default sort function (can be undefined)
    * f - sort method sort function argument (can be undefined)
    */
    function sort(a, o, sf, f) {
        var sf1 = f || sf; // sort function  method used if not undefined
        // if there is a customer sort function, use it
        if (isFunct(sf1)) {
            a.sort(function (e1, e2) { return sf1(e1.value, e2.value); });
        }
        else {
            // sort by key values
            a.sort();
        }
        // reindex - adds O(n) to perf
        reindex(a, o, 0);
        // return sorted values (not entire array)
        // adds O(n) to perf
        return values(a);
    };
 
    /*
    * forEach iteration of "values"
    *   uses "for" loop to allow exiting iteration when function returns true 
    */
    function forEach(a, f) {
        if (!isFunct(f)) { return; }
        // use for loop to allow exiting early and not iterating all items
        for(var i = 0; i < a.length; i++) {
            if (f(a[i].value, i)) { break; }
        }
    };
 
    /*
    * forEachR iteration of "values" in reverse order
    *   uses "for" loop to allow exiting iteration when function returns true 
    */
    function forEachR(a, f) {
        if (!isFunct(f)) { return; }
        // use for loop to allow exiting early and not iterating all items
        for (var i = a.length - 1; i > -1; i--) {
            if (f(a[i].value, i)) { break; }
        }
    }
 
    /*
    * Add a new Key Value Pair, or update the value of an existing key value pair
    */
    function add(key, value, a, o, resort, sf) {
        var k = makeKey(key);
        // Update value if key exists
        if (exists(k, o)) {
            a[o[k]].value = value;
        }
        else {
            // Add a new Key value Pair
            var kvp = newkvp(k, value);
            o[kvp.key] = a.length;
            a.push(kvp);
        }
        // resort if requested
        if (resort) { sort(a, o, sf); }
    };
 
    /*
    * Removes an existing key value pair and returns the 
    * "value" If the key does not exists, returns undefined
    */
    function remove(key, a, o) {
        var k = makeKey(key);
        // return undefined if the key does not exist
        if (!exists(k, o)) { return; }
        // get the array index
        var i = o[k];
        // get the key value pair
        var ret = a[i];
        // remove the array element
        a.splice(i, 1);
        // remove the object property
        delete o[k];
        // reindex the object properties from the remove element to end of the array
        reindex(a, o, i);
        // return the removed value
        return ret.value;
    };
 
    /*
    * Returns true if key exists in the dictionary.
    * k - Key to check (without the leading "_" character) 
    */
    function keyExists(k, o) {
        return exists(makeKey(k), o);
    };
 
    /*
    * Returns value assocated with "key". Returns undefined if key not found
    */
    function item(key, a, o) {
        var k = makeKey(key);
        if (exists(k, o)) {
            return a[o[k]].value;
        }
    }
 
    /*
    * changes index values held by object properties to match the array index location
    * Called after sorting or removing
    */
    function reindex(a, o, i){
        for (var j = i; j < a.length; j++) {
            o[a[j].key] = j;
        }
    }
 
    /*
    * The "real dictionary"
    */
    function dict() {
        var _a = [];
        var _o = {};
        var _sortF;
 
        Object.defineProperties(this, {
            "length": { get: function () { return _a.length; }, enumerable: true },
            "keys": { get: function() { return keys(_a); }, enumerable: true },
            "values": { get: function() { return values(_a); }, enumerable: true },
            "keyValuePairs": { get: function() { return kvPs(_a); }, enumerable: true},
            "sortFunction": { get: function() { return _sortF; }, 
            set: function(funct) { _sortF = ensureF(funct); }, enumerable: true }
        });
 
        // Array Methods - Only modification to not 
        // pass the actual array to the callback function
        this.map = function(funct) { return map(_a, funct); };
        this.every = function(funct) { return every(_a, funct); };
        this.filter = function(funct) { return filter(_a, funct); };
        this.reverse = function() { reverse(_a, _o); };
        this.shuffle = function () { return shuffle(_a, _o); };
        this.some = function(funct) { return some(_a, funct); };
        this.sort = function(funct) { return sort(_a, _o, _sortF, funct); };
 
        // Array Methods - Modified aborts when funct returns true.
        this.forEach = function (funct) { forEach(_a, funct) };
 
        // forEach in reverse order
        this.forEachRev = function (funct) { forEachR(_a, funct) };
 
        // Dictionary Methods
        this.addOrUpdate = function(key, value, resort) 
        { return add(key, value, _a, _o, resort, _sortF); };
        this.remove = function(key) { return remove(key, _a, _o); };
        this.exists = function(key) { return keyExists(key, _o); };
        this.item = function(key) { return item(key, _a, _o); };
        this.get = function (index) 
        { if (index > -1 && index < _a.length) { return _a[index].value; } } ,
        this.clear = function() { _a = []; _o = {}; };
 
        return this;
    }
 
 
    return this;
}

One of the epiphanies I had while trying to mentally reconcile class vs. prototype objects is that the prototype is basically a v-table for the created objects. Additionally functions in an enclosure can also act like v-table entries. As the project progressed, I started using Object Factories where a top level object contained common functions for the object type and included a “this.New(args)” method that was used to create the actual objects used in the solution. This is the style I used for the dictionary.

The core of the dictionary is an Array, an Object and a KeyValuePair object. The “addOrUpdate” method takes a key and a value and:

  1. Creates a KeyValuePair
  2. Adds a new property to the object using the key as the property name and the array length as the property value
  3. Add the KeyValuePair to the Array, making the object new property value the index in the array

NOTE: I read the object property names can start with “almost any” Unicode character. The project would be dealing with customer data which can start with “any” Unicode character. To ensure the dictionary did not blowup due to an invalid property name, I prefix an underscore (_) to the key and strip off that underscore when returning keys external to the dictionary.

For the dictionary to be functional, the internal Array and Object must be kept in sync. To ensure this, neither the Array nor the Object are exposed externally. I wanted to avoid accidental changes such as those that can happen when a “If” test has only one equal sign and the left have value is set by mistake.

Example

If(dict.KeyObj["SomeKey"] = "oops") { alert("good luck tracing this down:-)"); } 

This typical error with the dictionary might be very hard to track down when bugs (the symptoms) start showing up in calculation, display, etc. Consequently, the “this” property would not have access to either one. This protectionism is one of the reasons I did not dig more into prototypes. It had crossed my mind to use an internal object with the Array and Object exposed and pass that internal object when using the “call” or “apply” methods and I may look at that later as I’m still not sure I wouldn’t have to expose that internal object which would defeat the purpose of protecting the core Array and Object.

I fixed some of the newbie mistakes I made with the first dictionary object I created.

  • The "Dict()" function contains most of the working code for each dictionary object. The criteria I used to determine whether an enclosed function should be used vs. functionality in the actual dictionary object:
    • More than one line of code
    • Used by other enclosed functions
    • May be subject to change causing growth as I discover bugs/issues
  • Used Array method and property names where it made sense. Coming from C#, I did things that made my dictionary less usable as using "Count" instead of "length" or "ForEach" instead of "forEach". By using Array names, the dictionary can now be used as an Array in most cases. Unfortunately, I was not able to find a way to create a bracket accessor (e.g. val = dict[key]) and that may be a good thing anyway. When thinking about it, I had difficulty being sure that things like val = dict[12] worked correctly. The number 12 could easily have been used as a key so I could not think of a good way of knowing the "intention" of such a call.
  • Fully enclosed the underscore prefix handling. In the project I was working, I had this spread out and repeated in various data model objects. It was ugly!

Now that I had the improved dictionary functioning, did it really help with performance? To answer that question, I created a couple of testing objects. The first testing object used strings as the dictionary values. To keep things simple, the same string was used for both the key and value.

function DictPerf() {
 
    this.testPerf = function (dict, size) {
        var testData = makeTestData(size);
        dict.clear();
        dict.sortFunction = undefined;
        var arr = [];
        var results = [];
 
        results.push("Perf Testing: Count= " + size);
        results.push(loadTestingDict(dict, testData));
        results.push(loadTestingArr(arr, testData));
        results.push(accessTestingDict(dict, testData));
        results.push(accessTestingArr(arr, testData));
        results.push(mapTestingDict(dict, testData));
        results.push(mapTestingArr(arr, testData));
        results.push(forEachTestingDict(dict, testData));
        results.push(forEachTestingArr(arr, testData));
        results.push(reverseTestingDict(dict, testData));
        results.push(reverseTestingArr(arr, testData));
        results.push(sortTestingDict(dict, testData));
        results.push(sortTestingArr(arr, testData));
        results.push(sortTestingDictRevCmp(dict, testData));
        results.push(sortTestingArrRevCmp(arr, testData));
        results.push(sortTestingDictFwdCmp(dict, testData));
        results.push(sortTestingArrFwdCmp(arr, testData));
 
        return results;
    }
 
    function testResult(name, start, end) {
        return {
            Name: name,
            Start: start,
            End: end,
            toString: function () { return this.Name + 
            " milliseconds:" + (this.End - this.Start) }
        };
    }
 
    function loadTestingDict(dict, testData) {
        var name = "Dictionary Load Testing";
        var start = new Date();
        for (var i = 0; i < testData.length; i++) {
            dict.addOrUpdate(testData[i], testData[i]);
        };
        var end = new Date();
        return testResult(name, start, end);
    }
 
    function loadTestingArr(arr, testData) {
        var name = "Array Load Testing";
        var start = new Date();
        for (var i = 0; i < testData.length; i++) {
            arr.push(testData[i]);
        };
        var end = new Date();
        return testResult(name, start, end);
    }
 
    function accessTestingDict(dict, testData) {
        var name = "Dictionary Access Testing";
        var start = new Date();
        var val;
        for (var i = 0; i < testData.length; i++) {
            val = dict.item(testData[i]);
            if (val != testData[i]) {
                throw new Error("Dict: val != testData[i]");
            }
        };
        var end = new Date();
        return testResult(name, start, end);
    }
 
    function accessTestingArr(arr, testData) {
        var name = "Array Access Testing";
        var start = new Date();
        var val;
        for (var i = 0; i < testData.length; i++) {
            val = arr[arr.indexOf(testData[i])];
            if (val != testData[i]) {
                throw new Error("Array: val != testData[i]");
            }
        };
        var end = new Date();
        return testResult(name, start, end);
    }
 
    function forEachTestingDict(dict, testData) {
        var name = "Dict ForEach Testing";
        var start = new Date();
        var data = []
        dict.forEach(function(e) { data.push(e); });
        var end = new Date();
        return testResult(name, start, end);
    }
 
    function forEachTestingArr(arr, testData) {
        var name = "Array ForEach Testing";
        var start = new Date();
        var data = []
        arr.forEach(function(e) { data.push(e); });
        var end = new Date();
        return testResult(name, start, end);
    }
 
    function mapTestingDict(dict, testData) {
        var name = "Dict Map Testing";
        var start = new Date();
        var data = dict.map(function (e) { return e; });
        var end = new Date();
        return testResult(name, start, end);
    }
 
    function mapTestingArr(arr, testData) {
        var name = "Array Map Testing";
        var start = new Date();
        var data = arr.map(function (e) { return e; });
        var end = new Date();
        return testResult(name, start, end);
    }
 
    function reverseTestingDict(dict, testData) {
        var name = "Dict Reverse Testing";
        var start = new Date();
        dict.reverse();
        var end = new Date();
        return testResult(name, start, end);
    }
 
    function reverseTestingArr(arr, testData) {
        var name = "Array Reverse Testing";
        var start = new Date();
        arr.reverse();
        var end = new Date();
        return testResult(name, start, end);
    }
 
    function sortFwd(v1, v2) {
        if (v1 > v2) {
            return 1;
        }
        if (v1 < v2) {
            return -1;
        }
        return 0;
    }
 
    function sortRev(v1, v2) {
        return -1 * sortFwd(v1, v2);
    }
 
    function sortTestingDict(dict, testData) {
        var name = "Dict Sort Testing";
        var start = new Date();
        dict.sort();
        var end = new Date();
        return testResult(name, start, end);
    }
 
    function sortTestingArr(arr, testData) {
        var name = "Array Sort Testing";
        var start = new Date();
        arr.sort();
        var end = new Date();
        return testResult(name, start, end);
    }
 
    function sortTestingDictRevCmp(dict, testData) {
        var name = "Dict Sort Reverse Comparer Testing";
        var start = new Date();
        dict.sort(sortRev);
        var end = new Date();
        return testResult(name, start, end);
    }
 
    function sortTestingArrRevCmp(arr, testData) {
        var name = "Array Sort Reverse Comparer Testing";
        var start = new Date();
        arr.sort(sortRev);
        var end = new Date();
        return testResult(name, start, end);
    }
 
    function sortTestingDictFwdCmp(dict, testData) {
        var name = "Dict Sort Forward Comparer Testing";
        var start = new Date();
        dict.sort(sortFwd);
        var end = new Date();
        return testResult(name, start, end);
    }
 
    function sortTestingArrFwdCmp(arr, testData) {
        var name = "Array Sort Forward Comparer Testing";
        var start = new Date();
        arr.sort(sortFwd);
        var end = new Date();
        return testResult(name, start, end);
    }
 
 
    function makeKvp(k, v) {
        return { key: k, value: v };
    };
 
    function makeTestData(size) {
        var arrData = [], val;
        for(var i = 0; i < size; i++) {
            val = "D" + zeroPad(i, 10);
            arrData.push(val);
        }
        shuffleArray(arrData);
        return arrData;
    }
 
    /**
     * Randomize array element order in-place.
     * Using Fisher-Yates shuffle algorithm.
     */
    function shuffleArray(array) {
        var j, temp;
        for (var i = array.length - 1; i > 0; i--) {
            j = Math.floor(Math.random() * (i + 1));
            temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
        return array;
    }
 
    function zeroPad(num, size) {
        var n = Math.abs(num);
	    var zeros = Math.max(0, size - Math.floor(n).toString().length );
	    var zeroString = Math.pow(10, zeros).toString().substr(1);
	    if( num < 0 ) {
		    zeroString = '-' + zeroString;
	    }
	    return zeroString+n;
    }
 
    return this;
}

After running the tests and assembling the results, I decided to create a second performance testing object that used objects as the values. For the project I was working, data model objects were the dictionary values and there could be a difference in performance between arrays with primitives and arrays with objects.

function DictPerfObj() {
 
    this.testPerf = function (dict, size) {
        var testData = makeTestData(size);
        dict.clear();
        dict.sortFunction = undefined;
        var arr = [];
        var results = [];
 
        results.push("Perf Testing: Count= " + size);
        results.push(loadTestingDict(dict, testData));
        results.push(loadTestingArr(arr, testData));
        results.push(accessTestingDict(dict, testData));
        results.push(accessTestingArr(arr, testData));
        results.push(mapTestingDict(dict, testData));
        results.push(mapTestingArr(arr, testData));
        results.push(forEachTestingDict(dict, testData));
        results.push(forEachTestingArr(arr, testData));
        results.push(reverseTestingDict(dict, testData));
        results.push(reverseTestingArr(arr, testData));
        results.push(sortTestingDict(dict, testData));
        results.push(sortTestingArr(arr, testData));
        results.push(sortTestingDictRevCmp(dict, testData));
        results.push(sortTestingArrRevCmp(arr, testData));
        results.push(sortTestingDictFwdCmp(dict, testData));
        results.push(sortTestingArrFwdCmp(arr, testData));
 
        return results;
    }
 
    function testResult(name, start, end) {
        return {
            Name: name,
            Start: start,
            End: end,
            toString: function () { return this.Name + 
            " milliseconds:" + (this.End - this.Start) }
        };
    }
 
    function loadTestingDict(dict, testData) {
        var name = "Dictionary Load Testing";
        var start = new Date();
        for (var i = 0; i < testData.length; i++) {
            dict.addOrUpdate(testData[i].key, testData[i].value);
        };
        var end = new Date();
        return testResult(name, start, end);
    }
 
    function loadTestingArr(arr, testData) {
        var name = "Array Load Testing";
        var start = new Date();
        for (var i = 0; i < testData.length; i++) {
            arr.push(testData[i]);
        };
        var end = new Date();
        return testResult(name, start, end);
    }
 
    function accessTestingDict(dict, testData) {
        var name = "Dictionary Access Testing";
        var start = new Date();
        var val;
        for (var i = 0; i < testData.length; i++) {
            val = dict.item(testData[i].key);
            if (val != testData[i]) {
                throw new Error("Dict: val != testData[i]");
            }
        };
        var end = new Date();
        return testResult(name, start, end);
    }
 
    function accessTestingArr(arr, testData) {
        var name = "Array Access Testing";
        var start = new Date();
        var val;
        for (var i = 0; i < testData.length; i++) {
            val = arr[arr.indexOf(testData[i])];
            if (val.value != testData[i].value) {
                throw new Error("Array: val != testData[i]");
            }
        };
        var end = new Date();
        return testResult(name, start, end);
    }
 
    function forEachTestingDict(dict, testData) {
        var name = "Dict ForEach Testing";
        var start = new Date();
        var data = []
        dict.forEach(function(e) { data.push(e); });
        var end = new Date();
        return testResult(name, start, end);
    }
 
    function forEachTestingArr(arr, testData) {
        var name = "Array ForEach Testing";
        var start = new Date();
        var data = []
        arr.forEach(function(e) { data.push(e.value); });
        var end = new Date();
        return testResult(name, start, end);
    }
 
    function mapTestingDict(dict, testData) {
        var name = "Dict Map Testing";
        var start = new Date();
        var data = dict.map(function (e) { return e; });
        var end = new Date();
        return testResult(name, start, end);
    }
 
    function mapTestingArr(arr, testData) {
        var name = "Array Map Testing";
        var start = new Date();
        var data = arr.map(function (e) { return e.value; });
        var end = new Date();
        return testResult(name, start, end);
    }
 
    function reverseTestingDict(dict, testData) {
        var name = "Dict Reverse Testing";
        var start = new Date();
        dict.reverse();
        var end = new Date();
        return testResult(name, start, end);
    }
 
    function reverseTestingArr(arr, testData) {
        var name = "Array Reverse Testing";
        var start = new Date();
        arr.reverse();
        var end = new Date();
        return testResult(name, start, end);
    }
 
    function sortFwd(v1, v2) {
        if (v1 > v2) {
            return 1;
        }
        if (v1 < v2) {
            return -1;
        }
        return 0;
    }
 
    function sortFwdArr(v1, v2) {
        if (v1.value > v2.value) {
            return 1;
        }
        if (v1.value < v2.value) {
            return -1;
        }
        return 0;
    }
 
    function sortRevArr(v1, v2) {
        return -1 * sortFwdArr(v1, v2);
    }
 
    function sortRev(v1, v2) {
        return -1 * sortFwd(v1, v2);
    }
 
    function sortTestingDict(dict, testData) {
        var name = "Dict Sort Testing";
        var start = new Date();
        dict.sort();
        var end = new Date();
        return testResult(name, start, end);
    }
 
    function sortTestingArr(arr, testData) {
        var name = "Array Sort Testing";
        var start = new Date();
        arr.sort();
        var end = new Date();
        return testResult(name, start, end);
    }
 
    function sortTestingDictRevCmp(dict, testData) {
        var name = "Dict Sort Reverse Comparer Testing";
        var start = new Date();
        dict.sort(sortRev);
        var end = new Date();
        return testResult(name, start, end);
    }
 
    function sortTestingArrRevCmp(arr, testData) {
        var name = "Array Sort Reverse Comparer Testing";
        var start = new Date();
        arr.sort(sortRevArr);
        var end = new Date();
        return testResult(name, start, end);
    }
 
    function sortTestingDictFwdCmp(dict, testData) {
        var name = "Dict Sort Forward Comparer Testing";
        var start = new Date();
        dict.sort(sortFwd);
        var end = new Date();
        return testResult(name, start, end);
    }
 
    function sortTestingArrFwdCmp(arr, testData) {
        var name = "Array Sort Forward Comparer Testing";
        var start = new Date();
        arr.sort(sortFwdArr);
        var end = new Date();
        return testResult(name, start, end);
    }
 
 
    /*
    * Key Value Pair object - held in array
    */
    function newkvp(key, value) {
        return {
            key: key,
            value: value,
            toString: function () { return this.key; },
            valueOf: function () { return this.key; }
        };
    };
 
    function makeTestData(size) {
        var arrData = [], val;
        for(var i = 0; i < size; i++) {
            val = "D" + zeroPad(i, 10);
            arrData.push(newkvp(val, val));
        }
        shuffleArray(arrData);
        return arrData;
    }
 
    /**
     * Randomize array element order in-place.
     * Using Fisher-Yates shuffle algorithm.
     */
    function shuffleArray(array) {
        var j, temp;
        for (var i = array.length - 1; i > 0; i--) {
            j = Math.floor(Math.random() * (i + 1));
            temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
        return array;
    }
 
    function zeroPad(num, size) {
        var n = Math.abs(num);
	    var zeros = Math.max(0, size - Math.floor(n).toString().length );
	    var zeroString = Math.pow(10, zeros).toString().substr(1);
	    if( num < 0 ) {
		    zeroString = '-' + zeroString;
	    }
	    return zeroString+n;
    }
 
    return this;
}

I ran both sets for performance testing code using 100, 1000, and 10,000 elements. I ran the tests in Firefox, Chrome, and Internet Explorer.

  • 100 Elements: For all intensive purposes, consider every value here between 0 and 2. I ran the tests multiple times in each browser and 0 was the most common, 1 next and sometimes a 2 showed up. I just put values from the last test run in the tables below.
  • 1000 and 10,000 elements: For these, I ran the test 10 times and took an average of the results. I decided I did not need to really run more than that to get a general idea of the performance.
  • For array access testing, I used array[array.indexOf("key")). This would be the way I would find the value given a "key" and not an index.

String Values

		Firefox	Chrome	IE
Process	Elements	Dict	Array	Dict	Array	Dict	Array
Loading	100	1	0	0	0	0	0
Access	100	1	2	0	0	0	1
Map Function	100	0	0	0	0	0	0
ForEach Function	100	0	0	0	0	0	0
Reverse Function	100	0	0	0	0	0	0
Sort	100	0	0	0	0	0	0
Sort Reverse Compare	100	0	0	0	0	0	0
Sort Forward Compare	100	0	0	0	0	0	0
Loading	1000	6.1	0.4	1.5	0	5.5	0.1
Access	1000	2.7	74.2	1.6	26.7	2	41.7
Map Function	1000	0	0.3	0	0	0	0
ForEach Function	1000	0.3	0	0	1.6	0	0.1
Reverse Function	1000	0.8	0.1	0	0	0.9	0
Sort	1000	1.8	0.8	1.5	0	1.2	0.9
Sort Reverse Compare	1000	2.3	1	0	3.1	2.1	1.9
Sort Forward Compare	1000	1.2	0.9	1.6	3.1	1.8	1.5
Loading	10000	25.5	0.9	29.8	0	25.7	0.3
Access	10000	12.8	8313.6	10.9	2436.8	12.8	4985.4
Map Function	10000	1.3	1.1	3.1	0	0.5	0.4
ForEach Function	10000	0.9	0.9	1.6	1.6	0.3	0.5
Reverse Function	10000	6.6	0.2	6.2	1.5	4.4	0
Sort	10000	23.7	16.9	48	21.8	24.8	11.1
Sort Reverse Compare	10000	33.6	16.9	33	13.7	33.2	18.5
Sort Forward Compare	10000	29.6	12.8	22	9.3	33.1	18

Object Values

		Firefox	Chrome	IE
Process	Elements	Dict	Array	Dict	Array	Dict	Array
Loading	100	1	0	0	0	0	0
Access	100	1	2	0	0	0	1
Map Function	100	0	0	0	0	0	0
ForEach Function	100	0	0	0	0	0	0
Reverse Function	100	0	0	0	0	0	0
Sort	100	0	0	0	0	0	0
Sort Reverse Compare	100	0	0	0	0	0	0
Sort Forward Compare	100	0	0	0	0	0	0
Loading	1000	7.4	0.4	9.2	0	5.2	0.1
Access	1000	4.9	54.3	0	6.3	3.7	28.9
Map Function	1000	0.5	0.1	0	0	0.3	0.4
ForEach Function	1000	0.1	0.4	0	0	0	0
Reverse Function	1000	0.4	0.1	3.1	0	0.4	0
Sort	1000	1.8	1.2	6.3	3.2	1.6	1
Sort Reverse Compare	1000	2.2	1.2	4.6	0	2.9	2.2
Sort Forward Compare	1000	1.6	0.8	1.6	3	2.7	1.7
Loading	10000	26.7	1	29.7	0	25.5	0.3
Access	10000	20.4	4870.8	15.7	563.1	18.8	3243.4
Map Function	10000	1.5	1.4	0	6.1	2.8	1.3
ForEach Function	10000	0.6	1.4	0	7.9	0.7	1.5
Reverse Function	10000	6.5	0.5	3.2	0	4.7	0
Sort	10000	23.6	15.4	48.4	43.7	39	15
Sort Reverse Compare	10000	33.9	19.5	25	15.5	33.6	20
Sort Forward Compare	10000	29.8	14.6	23.4	17.2	32.5	18.8

As expected, dictionary load took much longer than array load and dictionary access was much faster than array access by "key" value. One thing I did not expect was such huge difference between browsers with the array Access timing. Chrome is clearly faster, followed by Internet Explorer, then Firefox. Something else that surprised me was that in all three browsers, Array accessing objects was much faster than array accessing strings. I actually expected the opposite to be true.

To answer the original question: "Would JavaScript Benefit from a Dictionary Object" I would have to say definitely yes when there is a need to quickly access individual data points in a large set of data. However as with most tools, it would be used where it should not be used, resulting in slower performance in some cases. Iterating short arrays is typically just as fast, if not faster than dictionary lookups and eliminates the overhead of dictionary and KeyValuePair creation. Keep in mind that my dictionary and testing code is all interpreted JavaScript. If JavaScript itself had a dictionary object, it would run in compiled code, possibly eliminating most of the slower performance in my array like methods and definitely improve the load time.

One thing I did not implement here is JSON round tripping.

License

This article, along with any associated source code and files, is licensed under The MIT License

Share

About the Author

Dan Ricker
Software Developer (Senior)
United States United States
No Biography provided

You may also be interested in...

Comments and Discussions

 
-- There are no messages in this forum --
Permalink | Advertise | Privacy | Cookies | Terms of Use | Mobile
Web04 | 2.8.190419.4 | Last Updated 19 Nov 2013
Article Copyright 2013 by Dan Ricker
Everything else Copyright © CodeProject, 1999-2019
Layout: fixed | fluid