Оптимизируйте регулярное выражение для фильтрации тысяч вариантов выбора HTML.

Фон

Я разработал на основе jQuery виджет shuttle для элементов HTML select, потому что не смог найти тот, который был бы минимально кодифицирован и предлагал бы обычный фильтр выражений, компенсирующий диакритические знаки.

Проблема

Когда в select добавляется несколько тысяч записей, фильтр регулярных выражений замедляется до минимума. Вы можете увидеть проблему следующим образом:

  1. Перейдите по адресу: http://jsfiddle.net/U8Xre/2/.
  2. Щелкните поле ввода на панели результатов.
  3. Введите любое регулярное выражение (например, ^a.*ai).

Код

Я считаю, что виновник скрывается здесь:

var options = $src.empty().scrollTop( 0 ).data( "options" );
var search = $.trim( $input.val() );
var regex = new RegExp( search, 'gi' );
var len = options.length;
var $html = $(document.createElement( 'option' ));
for( var i = 0; i < len; i++ ) {
  var o = options[ i ];
  if( o.text.dediacritics().match( regex ) !== null ) {
    $src.append( $html.clone().text( o.text ).val( o.value ) );
  }
}
$src.css( 'width', $input.width() + 4 );

Где $src - это источник $('#select'), а String.prototype.dediacritics определяется как в скрипке. Приведенный выше код выполняется для каждого нажатия клавиши. Есть еще один соответствующий фрагмент:

// Create a copy of the source options to use when matching the regex.
var $options = [];
$src.find( "option" ).each( function() {
  $options.push( { value: $(this).val(), text: $(this).text() } );
});
$src.data( "options", $options );

Это делает копию параметров из исходного списка, но запускается только один раз. (Это приводит к ошибке дублирования при переключении параметров, но добавление приведенного выше кода в обработчик событий input еще больше замедлит работу фильтра.)

Вопрос

Как сделать так, чтобы код выполнял фильтрацию регулярных выражений в списках до 5000 слов практически в режиме реального времени?

Благодарю вас!


javascript jquery optimization regex diacritics
person Dave Jarvis    schedule 26.11.2012    source источник
comment
Просто никогда не добавляйте тысячи записей в элемент <select>. Все, что выше 7, не удобно для пользователя, а все, что выше 20, требует аргументированного обоснования.   -  person Bergi    schedule 26.11.2012
comment
Это для экрана обслуживания, используемого несколькими людьми. В противном случае им пришлось бы вручную классифицировать элементы непосредственно в базе данных. Я не ищу разные UX-решения: все работает, хоть и медленно.   -  person Dave Jarvis    schedule 26.11.2012
comment
Я предполагаю, что узким местом является не регулярное выражение. Можете ли вы еще немного сузить узкое место?   -  person Cameron    schedule 26.11.2012
comment
Могу я спросить: где вы нашли эту причудливую функцию dediacritics, она где-то поддерживается?   -  person Bergi    schedule 14.12.2012
comment
@Bergi: stackoverflow.com/a/5912746/59087 ;-)   -  person Dave Jarvis    schedule 14.12.2012

Ответы (3)


arrow_upward
1
arrow_downward

Я предполагаю, что более сложной задачей является повторный вызов dediacritics() (с его многочисленными заменами регулярных выражений), чем выполнение поиска (хотя я не выполнял никакого профилирования). Таким образом, вы должны кэшировать эти строки без диакритических знаков и выполнять поиск только по ним. Кстати, test обычно быстрее, чем match.

Кроме того, вам следует избегать как можно большего количества операций DOM - у вас их много при очистке и повторном добавлении всего списка опций по нажатию клавиши.

// once:
var options = [],
    src = $src[0]; // or whatever to get the DOM element
$.each( src.options, function() {
    options.push( { el: this, text: $(this).text().dediacritics(), hidden:false } );
});
// you might put it on the element via .data(), but need not

// onkeypress:
var regex = new RegExp( $.trim($input.val()), 'i' );
var curEl = src.firstChild;
for (var i=0; i<options.length; i++) {
    var option = options[i];
    if (regex.test( option.text )) {
        if (option.hidden)
            src.insertBefore(option.el, curEl);
        curEl = option.el.nextSibling;
        option.hidden = false;
    } else {
        if (!option.hidden) {
            curEl = option.el.nextSibling;
            src.removeChild(option.el);
        }
        option.hidden = true;
    }
}

Демонстрация: это молниеносно ("в реальном времени"), но вы можете почувствовать время, необходимое для создания массив options при вызове dediacritics() 5000 раз.

person Bergi    schedule 26.11.2012
comment
Очень хорошо; возможно, придется немного оптимизировать это для исправления ошибки шаттла. Выглядит супербыстро. - person Dave Jarvis; 26.11.2012
comment
Точно, я пропустил это. Я бы порекомендовал просто еще одно бинарное свойство для хранения списка, в котором в настоящее время находится option, а затем просто continue цикла for. - person Bergi; 26.11.2012
comment
Есть еще одна ошибка: это исключит все остальные элементы, соответствующие регулярному выражению. Если у вас были Toy Box, Toy Story и Toy Zebra, то ^Toy не будет показывать Toy Story в списке. - person Dave Jarvis; 10.12.2012
comment
Спасибо за подсказку. Причиной проблемы был флаг lastIndex в (ненужном) регулярном выражении global, см. stackoverflow.com/q/ 1520800/1048572. Исправлено сейчас. - person Bergi; 10.12.2012
comment
@ridgerunner: удаление флага global (как я сделал) также работает - person Bergi; 10.12.2012
comment
@ Берги - совершенно верно. (забыл о том, как на это влияет флаг g) Я исправляюсь. Спасибо! - person ridgerunner; 11.12.2012

arrow_upward
1
arrow_downward

Я предлагаю вам

  • создать многострочную строку, содержащую список всех имен параметров, каждое в отдельной строке
  • примените регулярное выражение к этой многострочной строке, чтобы отфильтровать ее содержимое, удалив несоответствующие строки
  • обновить html с соответствующими строками в качестве параметров элемента выбора
person Ωmega    schedule 26.11.2012
comment
Я думал в этом направлении. $src.append выглядит довольно неэффективно. Благодарю вас! - person Dave Jarvis; 26.11.2012

arrow_upward
1
arrow_downward

Небольшой комментарий: если вы не используете результат совпадения регулярных выражений, вам следует использовать тест регулярных выражений:

  if( o.text.dediacritics().match( regex ) !== null ) {

используйте тест:

  if( regex.test(o.text.dediacritics()) ) {
person Kernel James    schedule 26.11.2012
comment
Нет, в этом ответе отсутствует важная инициализация, и запуск его как есть приведет к ошибочному поведению. Как и RegExp.exec(), метод RegExp.test() использует свойство lastIndex объекта экземпляра регулярного выражения, чтобы определить, с чего начать поиск в любой строке, а test() НЕ сбрасывает это свойство после успешного совпадения (он сбрасывает его при неудачном совпадении). . Последующие тесты (на других строках) после успешного совпадения будут начинаться с ненулевого места - ОШИБКА! Чтобы работать правильно, этот ответ должен добавить: regex.lastIndex=0; где-то перед: regex.test(). - person ridgerunner; 10.12.2012
comment
Кроме того, как правильно указывает @Bergi, вы можете поочередно создавать регулярное выражение с отключенным глобальным флагом g, что также приводит к сбросу: RegExp.lastIndex каждый раз при его запуске. - person ridgerunner; 11.12.2012