Most efficient way to select all elements with an array of values

Question

Let's suppose I have a <select> element:

<select id="foobar" name="foobar" multiple="multiple">
    <option value="1">Foobar 1</option>
    <option value="2">Foobar 2</option>
    <option value="3">Foobar 3</option>
</select>

And let's suppose I have an array of values, something like:

var optionValues = [2, 3];

How can I select the <option>s with values 2 and 3 most efficiently?

I'm working with a <select> that has thousands of <option>s, so doing it manually like this won't work:

var optionElements = [];

$("#foobar").children().each(function() {
    if($.inArray($(this).val(), optionValues)) {
        optionElements.push($(this));
    }
}

It's just too slow. Is there a way to hand jQuery a list of values for the elements I need to select? Any ideas?

P.S. In case you're wondering, I am in the middle of optimizing my jQuery PickList widget which currently sucks at handling large lists.

Answer 1

Have you considered creating a big hashtable at plugin bootstrap? Granted values are unique:

var options = {};

$('#foobar').children().each(function(){

    options[this.value] = this;

});

This way looking up is straightforward - options[valueNeeded].

EDIT - searching for optionValues:

var optionValues = [2, 3];

var results = [];

for(i=0; i<optionValues.length;i++){

    results.push[ options[ optionValues[i] ] ];

}

Answer 2

This hasn't been profiled so take it with a grain shaker of salt:

var options = $("some-select").children(),
    toFind = [2, 3],
    values = {},
    selectedValues = [],
    unSelectedValues = [];
// First, make a lookup table of selectable values
// O(1) beats O(n) any day
for (i=0, l=toFind.length; i++; i<l) {
    values[toFind[i]] = true;
}
// Avoid using more complicated constructs like `forEach` where speed is critical
for (i=0, l=options.length; i++; i<l) {
    // Avoid nasty edge cases since we need to support *all* possible values
    // See: http://www.devthought.com/2012/01/18/an-object-is-not-a-hash/
    if (values[options[i]] === true) {
        selectedValues.push(options[i]);
    }
    else {
        unSelectedValues.push(options[i]);
    }
}

There is obviously more we can do (like caching the selected and unselected values so we can avoid rebuilding them every time the user moves a value between them) and if we assume that the data is all unique we could even turn the whole thing into three "hashes" - but whatever we do we should profile it and ensure that it really is as fast as we think it is.

Answer 3

Assuming the values are unique, you can take some shortcuts. For instance, once you have found a value you can stop searching for it by splice()ing it off the search array.

This would be the ultimate optimisation, though, taking you from O(n^2) all the way down to O(n log n): Sorting.

First, loop through the options and build an array. Basically you just want to convert the NodeList to an Array. Then, sort the array with a callback to fetch the option's value. Sort the search array. Now you can loop through the "options" array and look for the current smallest search item.

var optsNodeList = document.getElementById('foobar').options,
    optsArray = [], l = optsNodeList.length, i,
    searchArray = [2,3], matches = [], misses = [];
for( i=0; i<l; i++) optsArray[i] = optsNodeList[i];
optsArray.sort(function(a,b) {return a.value < b.value ? -1 : 1;});
searchArray.sort();
while(searchArray[0] && (i = optsArray.shift())) {
    while( i > searchArray[0]) {
        misses.push(searchArray.shift());
    }
    if( i == searchArray[0]) {
        matches.push(i);
        searchArray.shift();
    }
}

Answer 4

Try this:

var $found = [];
var notFound = [];
var $opt = $('#foobar option');
$.each(optionValues, function(i, v){
    var $this = $opt.filter('[value='+v+']');
    if ($this.length) {
       $elems.push($this)
    } else {
       notFound.push(v);
    } 
})

Answer 5

First of all, I want to thank you all for the awesome responses! I'm considering each one, and I will probably do benchmarks before I make a decision.

In the interim, I actually found an "acceptable" solution based on this answer to another question.

Here's what I came up with (the last block, with the custom filter() implementation, is where the magic happens):

var items = self.sourceList.children(".ui-selected");

var itemIds = [];
items.each(function()
{
    itemIds.push( this.value );
});

self.element.children().filter(function()
{
    return $.inArray(this.value, itemIds) != -1;
}).attr("selected", "selected");

I doubt this is as efficient as any of the stuff you guys posted, but it has decreased the "Add" picklist operation time from about 10 seconds to 300ms on a 1500 item list.

Answer 6

I would give jQuery's filter() method a try, something like:

var matches = filter(function() {
    // Determine if "this" is a match and return true/false appropriately
});

// Do something with the matches
matches.addClass('foobar');

It may not be the fastest solution here, but it is fairly optimized and very very simple without having to keep track of lists and all that jazz. It should be fast enough for your situation.

Answer 7

Try this.

var optionValues = [2, 3],
    elements = [],
    options = document.getElementById('foobar').options;

var i = 0;
do {
    var option = options[i];
    if(optionValues.indexOf(+option.value) != -1) {
        elements.push(option);
    }
} while(i++ < options.length - 1);

Answer 8

Let optionValues by an array of indexes to be selected.

for(var i = 0; i < optionValues.length; i++) {
  document.forms[0].foobar.options[optionValues[i]].selected = true;
}

Answer 9

If you just want to select by value, the following should be suitable. It only loops over the options once and doesn't call any other functions, only one built–in method so it should be quick.

function selectMultiByValue(el, valuesArr) {

  var opts = el.options;
  var re = new RegExp('^(' + valuesArr.join('|') + ')$');

  // Select options
  for (var i=0, iLen=opts.length; i<iLen; i++) {
    opts[i].selected = re.test(opts[i].value);
  } 
}

In some browsers, looping over a collection is slow so it may pay to convert the options collection to an array first. But test before doing that, it may not be worth it.

Note that if the select isn't a multiple select, only the option with the last listed value will be selected.

You may need to fiddle with the regular expression if you want to allow various other characters or cases.