Как ускорить поиск на совпадение подстроки?

Question

[Максим]

$('input#searchVariant').on('keyup', function () {
            var query = this.value.toLowerCase();
            var variants = this.parentNode.nextElementSibling;
            var allVariants = variants.querySelectorAll('div.label-point');

            allVariants.forEach(function (item) {
                if (item.getAttribute('name').toLowerCase().indexOf(query) > -1) {
                    item.style.display = '';
                } else {
                    item.style.display = 'none';
                }
            })
        });

Выше приведен пример работающего на данный момент поиска. Из всего списка, мы скрываем те у которых не найдено совпадений. Так вот, сейчас этот список составляет 2700 вариантов и все очень жутко тормозит. Какие могут быть решения данной проблемы?

Answer 1

[hzzzzl]

предлагаю allVariants хранить в переменной в памяти, а не как элементы DOM, ну и всё нужное отрисовывать когда надо через

$('input#searchVariant').on('keyup', function () { 
вычислить строку по которой искать,
найти нужные элементы в массиве/объекте с данными, 
сделать для каждого свой блок 
добавить куда надо на страницу 
}

Comments

[Максим]

самое производительное решение из всех

[hzzzzl]

Максим, между прочим так и работают все реакты и прочие вью, переходи на светлую сторону, если нравится такой подход :)

Answer 2

[Антон Антон]

Как минимум закэшировать
var variants = this.parentNode.nextElementSibling;
var allVariants = variants.querySelectorAll('div.label-point');
Затем убрать .toLowerCase() (возможно где-то закэшировать соответствие приведенного названия и элемента DOM дерева)

Согласно https://proglib.io/p/javascript-performance-mistakes простой for быстрее forEach почти в 8 раз. Еще из серии экономии на спичках замена > на !==

Можно воспользоваться библиотеками для дебоунса (например https://lodash.com/docs/4.17.11#debounce ), чтобы не вызывать обработку на каждое нажатие, а, например, не чаще, чем раз в секунду.

Ну и почитать про профайлер в инструментах разработки, чтобы узнать, какие строки больше всего времени едят. С этого надо начинать.

Еще подумалось, что можно сравнивать предыдущее и новое значение инпута, и если новое более строгое (Абыр -> Абырв), то искать не по всем, а только по найденным на предыдущем этапе. + нужно проверить, будет ли эффект, если не менять видимость, если она не должна меняться. Возможно такое, что пересчет стилей все равно происходит, даже если мы присваиваем стилям то же значение, что и в них хранится.

А вообще отображение без пагинации тысяч элементов как-то странно. Так что прямая дорога дальше в реактивные фреймворки, потому что там это все намного прямее, чем прямая работа с DOM. Мне больше нравится vue.

Answer 3

[Andrey Tsvetkov]

У вас тормозит не поиск, а манипуляции с DOM
Во первых, заменить сравнение > -1 на строгое неравенство.
Во вторых, не использовать манипулирование объектом style, вместо этого добавлять/удалять класс, при этом не нужно добавлять/удалять класс если он уже и так в нужном состоянии. То есть необходимо добавить проверку на наличие/отсутствие класса.
Ну и в третьих, в начале функции, которая вызывается на событие "keyup" я бы воткнул проверку на то, какая кнопка была нажата, существует ряд кнопок, реагировать на которые нет смысла, например, пунктуация и пробелы, уверен вы найдёте ещё парочку =)

<style>.hidden{display:none}</style>
<script>
allVariants.forEach(function (item) {
  if (item.getAttribute('name').toLowerCase().indexOf(query) !== -1) {
    if(item.classList.contains('hidden')){
      item.classList.remove('hidden')
    }
  }
  else {
    if(item.classList.contains('hidden') === false){
       item.classList.add('hidden')
    }
  }
})
</script>

Ну и как упомянули выше, наверное стоит отказаться от forEach, я сам лично не исследовал, но мне кажется создание контекста для вызова функции и её вызов будут медленнее, чем пройтись обычным фором