iteration order for Object

[Claus Reinke]

> 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));

}());