jQuery.merge speedup

[jquery.neytema@…]

Index: jquery.js
===================================================================
--- jquery.js	(revision 642)
+++ jquery.js	(working copy)
@@ -1740,15 +1740,12 @@

 		// Now check for duplicates between a and b and only
 		// add the unique items
 		for ( var i = 0; i < second.length; i++ ) {
-			var noCollision = true;
-
 			// The collision-checking process
-			for ( var j = 0; j < first.length; j++ )
-				if ( second[i] == first[j] )
-					noCollision = false;
+			for ( var j = 0; j < first.length
+				&& second[i] != first[j]; j++ );
 
 			// If the item is unique, add it
-			if ( noCollision )
+			if ( j == first.length )
 				result.push( second[i] );
 		}

[Dave]

I have an alternate suggested fix that avoids going completely through first each time:

		// Now check for duplicates between a and b
		// and only add the unique items
	   DupCheck:
		for ( var i = 0; i < second.length; i++ ) {
			for ( var j = 0; j < first.length; j++ )
				if ( second[i] == first[j] )
					continue DupCheck;
			// The item is unique, add it
			result.push( second[i] );
		}

[andrea ercol]

merge is used a lot of times for a simple selection, so any milliseconds adds up quickly

I made some tests myself, with a very similar code (BTW, a simple break in the inner loop could be easier), but I could not get noticeably better results than what is now implemented in jQuery

I still have to test the following version, based on mergesort:

function merge( first, second ) {

• be first the longest array

• if( second.length == 0 && first.constructor == Array ) return

mergesort( first.concat() ); sort for consistency with the next

• if( second.constructor == Array && first.constructor == Array ) return mergesort( first.concat( second ) ); mergesort is fast and eliminates duplicates

• return merge( makeArrayFrom( first ), makeArrayFrom( second ) );

}

[Dave]

I am not even sure that merge needs to be used to check for duplicates so often. Isn't the comma the only selector operator that can introduce duplicate elements?

[henrah]

Isn't the comma the only selector operator that can introduce duplicate elements?

No -- say you have a structure like this:

<div>
  <div>
    <a> something </a>
  </div>
</div>

...and a selector like div a. The div selector will select both the inner and outer divs, then the a descendant selector will select the same link element twice, because it descends from both of them. This is just one example; many are less obvious.

[henrah]

If we are interested in a duplicate-removing function which only deals with whole objects and is thus checking for identity, rather than simple value, maybe something like this would be appropriate:

jQuery.elementUid = 1;
jQuery.uniquify = function (list){
    var seen = {}, key = 'jq_uid', result = [], item, i = 0;
    while (item = list[i++]){
      if (! item[key]) item[key] = jQuery.elementUid++;
      else if (seen[item[key]]) continue;
      result.push(item);
      seen[item[key]] = true;
    };
    return result;
};

One potential flaw with this idea is that it leaves new properties on the elements of the array. You could do a second pass over the original list and delete the jq_uid property, but assuming we are dealing with the special case of DOM nodes -- which are unlikely to be used as JS hashes, for instance -- it is probably safe to leave a UID attached to them. This also means that subsequent applications of the uniquify function will skip re-applying the property, which would indicate a (probably trivial) further optimization.

[brandon]

Fixed in REV 731 by Dave