Fastest way to remove/hide a lot of elements from a list

Question

I have a dropdown that contains around 100,000 rows which make up a list.

<input id="search" type="text" />
<ul>
    <li>item 1</li>
    <li>item 2</li>
        ...
    <li>item 100,000</li>
</ul>

I have a text box which acts as a search, so as you type it matches the input to items in the list, removing what does not match. This is the class I wrote to perform the removing of list elements.

See the fiddle (list has about 2000 items)

// requires jQuery
var Search = (function(){

    var cls = function (name) {
        var self = this;

        self.elem = $('#' + name);
        self.list = $('#' + name).next('ul').children();
        self.elem.bind('keyup', function () { self.change(); }); 
    };

    cls.prototype = {
        change: function () {
            var self = this;
            // gets the closest ul list
            var typed = self.elem.val();

            // only do something if there is something typed
            if (typed !== '') {
                // remove irrelevent items from the list
                self.list.each(function () {
                    var item = $(this).html();
                    if (item.indexOf(typed) === -1)  {
                        $(this).addClass('zero');
                        // tried using a class with visibility hidden
                    } else {
                        $(this).removeClass('zero');
                    }
                });
            } else {
                // check what list items are 'hidden' and unhide them
                self.list.each(function () {
                    if ($(this).hasClass('zero')) {
                        $(this).removeClass('zero');
                    }
                });
            }
        }
    };
    return cls;
}());

I am just adding a class which adds a height: 0, and no margin, padding, etc, but I have also tried using visibility: hidden. I have also tried using the detach method in jQuery but this is about the same in terms of speed.

Are there any JavaScript experts who can see any problems with the code, or offer some optimization techniques?

Answer 1

I've generated a list of 100K items and compared 2 approaches to hiding every second item.

1. Setting display to block/none

for (var i = 0, len=items.length; i < len; i++) {
    items[i].style.display = i % 2 ? 'none' : 'block';
}

Completed in 2 seconds in Chrome, never completed in Firefox.

2. Building HTML as one long string

// texts = ['facikufugo', 'xacabimuzo', ... 100K];
for (var html = '', i = 0; i < texts.length; i+=2) {
    html += '<li>' + texts[i] + '</li>'; // may need escaping
}
ul.innerHTML = html;

Completed in 2 seconds in Chrome, 6 seconds in Firefox.

---

The exact duration is hard to measure because of async rendering, console.time doesn't give the exact number.

There's absolutely no way to make this fast enough given 100 000 items. Even trying to select that many elements using jQuery results in 'Maximum call stack size exceeded' error in Chrome. Maybe you'll need to rethink your approach and have only a small number of <li> elements in the document at any given time.

Answer 2

A couple notes:

1. display: none does everything you're trying to do with your existing CSS class; it hides and completely removes the element from the layout. So instead of adding the zero class you would set display to none, and instead of removing it you would set display to block.

2. As far as optimization goes, one thing you could do is iterate the list items and store all the strings in an array as part of the initialization for your function. Then when you're iterating self.list, fetch the string from your cached array with the current index instead of calling $(this).html(). That would most likely be faster because it eliminates a DOM lookup.

Answer 3

Simply displaying or hiding an entire list of 100,000 elements can take a second or two - that is probably the main bottleneck. But probably in most cases you will want to display much less than the full list, right? In which case you could do something like this. (fiddle)

var texts = [], maxResults = 3000;
// (then fill texts with the desired items)

document.getElementById('search').onkeyup = function() {
    var results = [],
        typed = document.getElementById('search').value;
    if (typed) {
        for (var p, t = texts.slice(), i = maxResults; i && (p = t.pop());) {
            if (p.indexOf(typed) > -1) {
                results.push(p);
                i--;
            }
        }
    }
    else results = texts.slice(0, maxResults);
    document.getElementById('results').innerHTML = 
        '<ul><li>' + results.join('</li><li>') + '</li></ul>';
}

An alternative with similar effects would be only to update the list when at least 2 or 3 characters have been typed. But then you have to decide what to do when the user backspaces, which could once again result in a massive list having to be displayed.

Answer 4

I gave this a try using a WebWorker. The WebWorker helped out, I think, mostly by creating a time-window for additional text-input to be entered. Then, when a search result is recieved and it doesn't match the latest text-input, the search result is ignored. That prevents the DOM manipulation, which is what slows everything down.

For testing, I'm working with ~75k items. It's kinda spotty on FF, but works pretty well in Chrome and Safari. Even works on the iPhone, although some queries, like 'i' which returns ~50k items, can take ~10 seconds to render (but cached can be down to ~550ms). (I have to admit, my method for measuring these times is in need of improvement.)

A couple of things I did in trying to improve the performnce:

• Worked with <ul>s instead of <li>s, per Alexey's answer
• Worked with an array of strings instead of the <li>s, per seand's answer
• The <ul>s use absolute positioning
• The full list is never deleted, it's moved off screen
• The <ul>s for the last 7 searches are kept attached to the DOM and moved off-screen
• The removal of a <ul> (when it's not in the last 7) is done 1 second after it's no longer needed

Here is an excerpt of the code:

// keep a record of the last 7 searches
recents.setMaxLen(7);

$inTx.on('keyup.search-ftr chnage.search-ftr', function() {

    var tx = $inTx.val(),
        recent;

    // skip if same query
    if (tx === lastQuery) {
        return;
    }

    // full list is never removed from the DOM, just moved off screen
    // so, for the empty search move the full list back on screen
    if (tx === '') {
        ++curSearchId;
        // $curList is whatever search results are showing
        $curList.css('left', -9999);
        $ulWtihAll.css('left', 10);
        // $count shows is text of current # showing
        $count.text(fullCount);
        lastQuery = tx;
        $diffSearch.text('search: ');
        $diffRender.text('render: ');
        return;
    }

    // have a non-empty search, so move full list off screen if needed
    if (lastQuery === '') {
        $ulWtihAll.css('left', -9999);
    }

    lastQuery = tx;
    // the `<ul>` elements for last 7 searches are cached 
    // `recents` is a map (assoc array) capped at length 7
    recent = recents.getAndRenew(tx);
    if (recent) {
        useRecent(recent);
        return;
    }
    // start a search - in web worker if have it
    $ind.css('visibility', 'visible');
    searchStartMs = +new Date(); 
    searchFunc({searchStr: tx, createStr: true, id: ++curSearchId});
});

function searchCallback(e) {

    // ignore if not the results for most recent search
    if (e.data.id !== curSearchId) {
        return;
    }
    lastResultId = e.data.id;
    renderStartMs = +new Date();

    // update the counter
    $count.text(e.data.count);
    $diffSearch.text('search: ' + (+new Date() - searchStartMs));
    $ind.css('visibility', 'hidden');

    // DOM adding / removal is the slowest part (esp removal) so
    // move the current (now old) search result off screen instead
    // of removing it
    $curList.css('left', -9999);
    // create the new `<ul>` and add it to the DOM
    $curList = $('<ul>' + (e.data.result || '') + '</ul>').css(onCSS);
    $holder.append($curList);

    // add the latest <ul> to the recents capped map
    // if something was kicked out of the map, the .add() 
    // method will return it
    var removed = recents.add(e.data.searchStr, {
        $elm: $curList,
        count: e.data.count
    });
    // if am item was kicked out of the `recents` map, 
    // schedule it for removal from DOM
    if (removed) {
        setTimeout(function() {
            removed.$elm.remove();
        }, 1000);
    }
    // update the height of the div that holds the <ul>s
    // (can't seem to get this to work right in FF)
    setTimeout(function() {
        $holder.css('height', 100 + $curList.height());
        $diffRender.text('render: ' + (+new Date() - renderStartMs));
    }, 0);
}

// the search matches one of the cached <ul>s
function useRecent(recent) {

    // move the current list off screen, know it won't
    // be removed from the recent set bc not adding 
    // anything new to the recent set
    $curList.css('left', -9999);
    $count.text(recent.count);
    $curList = recent.$elm;
    $curList.css('left', 10);
    $diffSearch.text('search: (cached)');

    renderStartMs = +new Date();
    setTimeout(function() {
        $holder.css('height', 100 + $curList.height());
        $diffRender.text('render: ' + (+new Date() - renderStartMs));
    }, 0);
}

function workerSearch(params) {
    worker.postMessage(params);
}

function localSearch(params) {
    var res = findMatches(params.searchStr, true);
    searchCallback({
        data: {
            id: curSearchId,
            result: res.resultStr,
            count: res.count
        }
    });
}

A demo: http://jsfiddle.net/bWtpy/38/

The full code is a bit demonic, but I wanted to give it a shot.

Answer 5

You should try to optimize your algoritmic approach to searching, in addition to the JavaScript performance described in Alexey's comment. Your problem is (in most cases) not algoritmically equivalent to hiding every second list item, thus we can make use of an optimized data structure for the problem to take advantage of this. You are searching with "indexOf", which is relatively slow for such a large dataset. Build a suffix array to locate the substrings in your set (see this or this), then hide these elements.