Bug Tracker

Opened 13 years ago

Closed 13 years ago

#809 closed enhancement (fixed)

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"

Change History (4)

comment:1 Changed 13 years ago by Renato

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

comment:2 Changed 13 years ago by anonymous

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. :)

comment:3 Changed 13 years ago by Renato

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

comment:4 Changed 13 years ago by john

Milestone: 1.1.3
need: Review
Resolution: fixed
Status: newclosed
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!

Note: See TracTickets for help on using tickets.