#444 closed enhancement (fixed)
jQuery.merge speedup
Reported by: | Owned by: | ||
---|---|---|---|
Priority: | major | Milestone: | |
Component: | core | Version: | 1.1a |
Keywords: | Cc: | ||
Blocked by: | Blocking: |
Description
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] ); }
Change History (7)
comment:1 Changed 16 years ago by
Version: | → 1.1 |
---|
comment:2 Changed 16 years ago by
comment:3 Changed 16 years ago by
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 ) );
}
comment:4 Changed 16 years ago by
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?
comment:5 Changed 16 years ago by
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 div
s, 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.
comment:6 Changed 16 years ago by
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.
I have an alternate suggested fix that avoids going completely through first each time: