Konstantin Svist wrote:
lemme take a crack at it..
_boundedStack: {
_max: 500,
_stack: [],
_current: 0, // next position to be written
_overfly: false,
push: function(obj) {
var current = this._current; // minor optimization
this._stack[current] = obj;
This needs to realloc the array, unless js is really clever about those,
you realloc 500 times, which is slow and consumes basically 1000 entries
in memory at max. Not really worth it, if you usually do hit the 500
soonish.
if (current >= this._max) {
this._current = 0;
this._overfly = true;
}
},
length: function() { return this._stack.length; }, // note_1
item: function(idx) { // note_2
if (this._overfly) {
idx += this._current;
if (idx >= this._max) { idx -= this._max; }
}
return this._stack[idx];
}
}
note_1: it'll probably be a little faster to call myStack._stack.length
directly
note_2: caller needs to bound-check. this can be done implicitly: get
the length first, then only ask for elements within that length.
logic check: _current points to next field to write into. when getting
an element by index, _current points to oldest element iff there was an
overflow.
By the way, never skimp on the curly braces {}: for some reason Fx 1.0
favors the code with lots of {}s, by a slight margin (or so my testing
showed).
also, does it have to be an array? what if you just use a linked list of
objects? it may work faster if you keep retrieving the whole list each
time, not just a certain item
_boundedStack: {
first: null,
last: null,
len: 0,
max: 500,
push: function(obj) {
if (null == this.last) { this.last = obj; }
else {
this.last.next = obj;
this.last = obj;
}
this.len++;
if (null == first) { first = obj; }
else if (this.len >= this.max) {
this.first = this.first.next;
this.len--;
}
}
}
obj should be fairly easy to implement, i think..
to get the length of your stack, just grab the len variable
to get the list, get the first element then .next until .next == null
Linked lists are non-local in storage, that may or may not have an
impact on perf. In theory, I bet that doesn't matter at all in an
interpreted language.
It may be a little stressful on GC to have 500 additional objects.
It looks like you're polluting obj with next members, too.
Axel
_______________________________________________
Project_owners mailing list
[email protected]
http://mozdev.org/mailman/listinfo/project_owners
