speeding merge and inArray

Reported by:	Renato	Owned by:
Priority:	minor	Milestone:	1.1.3
Component:	core	Version:	1.1.1
Keywords:		Cc:
Blocked by:		Blocking:

Description

I know i'm late, 1.1 has just been released :)

Here are faster versions of merge and inArray, using a reverse iterator

	inArray: function( b, a ) {
		for ( var i =  a.length; i--; )
			if ( a[i] == b )
				return i;
		return -1;
	},
	merge: function(first, second) {
		var r = [];

		// Now check for duplicates between the two arrays
		// and only add the unique items
		for ( var i = second.length; i--; )
			// Check for duplicates
			if ( jQuery.inArray( second[i], first ) == -1 )
				// The item is unique, add it
				r.push( second[i] );
                [].push.apply(first,r.reverse());
		return first;
	}

In my tests they are especially good when selecting things like "div div div" or "div .class"

Attachments (0)

Change History (4)

Changed January 16, 2007 04:04PM UTC by Renato comment:1

I realized later the speeding point is not to copy the "first" array at the beginning of merge, rather than the reverse iterator.

Changed January 16, 2007 04:06PM UTC by anonymous comment:2

Ok, this breaks up the function by it's definition. It should retain the order of the elements and the reverse looping makes it... reverse.

l = array.length, total = l;

l--;

i = total-l;

and we got the order reserved.

Further more, if we used yet another variable to keep track of the length of r and did:

r[len++] = second[i];

we could get yet faster.

The looping could be optimized yet a bit if you compare the index against 0 instead of true/false.

would first.concat(r) be faster then push and apply?

I'm in a hurry, so I can't try these out yet. I might yet something more in my stock, I've tried like 20 variations of merge so far. :)

Changed January 16, 2007 04:17PM UTC by Renato comment:3

The order is kept reversing the elements not found in "first" before adding them to it.

concat is not an option as it makes a new array and merge has to add the elements right to the array it receives.

Consider:

//merge without getting the return value
jQuery.merge(first,second);

If you use concat, first will not be affected

Changed March 24, 2007 10:05PM UTC by john comment:4

milestone:	→ 1.1.3
need:	→ Review
resolution:	→ fixed
status:	new → closed
version:	→ 1.1.1

Ok, I've considerably changed how things work internally and merged some new improvements in (rev [1576]), that are quite fast.

Unfortunately, .concat() isn't an option because certain browsers (*cough*) don't know how to handle array-like objects (like NodeLists) - meaning that you have to end up looping through the results anyway. But thanks, everyone, for your help!

Side navigation