Hi,
> > Anyone know of a fast way to remove dups in an array?
>
> The Perl way to do this is to convert the array entries into hash keys
> and then extract the keys back into an array. This is faster than
> searching the array and it should work with javascript.
The speed of such solutions very much depends on the input data.
You have a complexity of O(n+m) where n and m are the numbers of entries and
of unique entries. If the array is sorted, the complexity of my suggested
method is also O(n).
If the array is not sorted you can use a function like this:
function arrayUniq(a) {
if( a.length > 1 ) {
var n = Math.floor(a.length/2)
var a1 = arrayUniq(a.slice(0,n));
var a2 = arrayUniq(a.slice(n));
var rval = [];
var last;
while( a1.length > 0 && a2.length > 0) {
if( a1[0] == last ) a1.pop();
if( a2[0] == last ) a2.pop();
if( a1[0] < a2[0] ) rval.push(last = a1.pop());
else rval.push(last = a2.pop());
}
return rval.concat(a1,a2);
} else return a;
}
It doesn't keep the order of the elements, but does sort|uniq in one step. It
has the same complexity as Mergesort, which is O(n*n). Thus in this case your
method might be faster, but it also looses the order of the input elements.
If that is necessary i only know the brute force solution:
function arrayUniq(a) {
var k = [];
var rval = [];
if( ! k.contains ) k.contains = function(e) {
for( var i = 0; i < this.length; i++ ) if(this[i] == e) return
true;
return false;
};
for( var i = 0; i < a.length; i++ ) if( !k.contains(a[i]) ) {
rval.push(a[i]);
k.push(a[i]);
}
return rval;
}
Christof
_______________________________________________
jQuery mailing list
[email protected]
http://jquery.com/discuss/
