iteration order for Object
Claus Reinke
claus.reinke at talk21.com
Sat Mar 12 02:08:32 PST 2011
> 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));
}());
More information about the es-discuss
mailing list