Below are two partial implementations of LinkedHashMap in
JavaScript, with test code to populate with lots of keys and remove
half the keys at random, then alert() the results. Both implementations
add and maintain an index to provide O(1) lookups.
Each is compared to the speed of the equivalent use of Object
assuming it supports ordering, which is just to use the JavaScript
"delete" operator to remove keys.
The first is a straightforward implementation where insert and
removal use splice() to modify an Array. This is what most
developers would probably implement.
I'd hope not: indexOf on a large Array?
This is approximately 800-1000 times slower than a native Object.
The second leverages native speed better by using two Objects
to store the forward and reverse pointers of a classic linked list.
I'll stipulate that everyone on this list would arrive at this
implementation, but in my opinion a vanishing small number
of JavaScript programmers at large would figure it out.
Even so it's 8-10x slower than native.
I notice that you don't count initialization for the native Object
variant. Apart from fixing that, would the following variant help
(run, but not tested;-)? It keeps the previous/next key in the
key's internal value, to reduce overhead.
Claus
// another partial implementation
(function () {
var sourceDataArr = [];
var keysToRemove = [];
for (var i = 0; i < 30000; i++) {
sourceDataArr[sourceDataArr.length] = "key" + i;
sourceDataArr[sourceDataArr.length] = "value" + i;
if (Math.random(1) > 0.5) {
keysToRemove[keysToRemove.length] = "key" + i;
}
}
var orderedMap = {
init : function (data) {
this.index = {};
for (var i = 0; i < data.length; i++) {
// [prev, value, next]
this.index[data[i]] = [data[i-2],data[i+1],data[i+2]];
i++;
}
this.firstKey = data[0];
this.lastKey = data[data.length-2];
},
get : function (key) {
return this.index[key][1];
},
remove : function (key) {
var which = this.index[key];
if (which[0]) // is there a previous?
this.index[which[0]][2] = which[2];
else // key was first
this.firstKey = which[2];
if (which[2]) // is there a next?
this.index[which[2]][0] = which[0];
else // key was last
this.lastKey = which[0];
delete this.index[key];
}
};
var start = new Date().getTime();
var sourceDataObj = {};
for (var i = 0; i < sourceDataArr.length; i++) {
var key = sourceDataArr[i],
value = sourceDataArr[i+1];
sourceDataObj[key] = value;
i++;
}
for (var i = 0; i < keysToRemove.length; i++) {
delete sourceDataObj[keysToRemove[i]];
}
alert("object: " + (new Date().getTime() - start));
var start = new Date().getTime();
orderedMap.init(sourceDataArr);
for (var i = 0; i < keysToRemove.length; i++) {
orderedMap.remove(keysToRemove[i]);
}
alert("orderedMap: " + (new Date().getTime() - start));
}());
_______________________________________________
es-discuss mailing list
[email protected]
https://mail.mozilla.org/listinfo/es-discuss
