Оптимизировать регулярное выражение

Question

Я использую следующий код для отбрасывания неподдерживаемых физических интерфейсов / подинтерфейсов от маршрутизаторов, которые подключаются к большой сети ISP (под большими я имею в виду десятки тысяч маршрутизаторов):

private final static Pattern INTERFACES_TO_FILTER = 
   Pattern.compile("unrouted VLAN|GigabitEthernet.+-mpls layer|FastEthernet.+-802\\.1Q vLAN subif"); 

// Simplification
List<String> interfaces;
// lots of irrelevant code to query the routers 

for (String intf : interfaces) {
   if (INTERFACES_TO_FILTER.matcher(intf).find()) {
      // code to prevent the interface from being used
   } 
}

Идея состоит в том,отбрасывание записей, таких как:

• не маршрутизированная VLAN 2000 для GigabitEthernet2 / 11.2000
• GigabitEthernet1 / 2-mpls layer
• FastEthernet6 / 0 / 3.2000-802.1Q vLAN subif

Этот код выполняется достаточно часто (несколько раз в минуту) через огромные наборы интерфейсов (некоторые маршрутизаторы имеют 50 тыс. + Подынтерфейсов), кеш также не очень помогает, потому что новые подынтерфейсы настраиваются / удаляются оченьдовольно часто.План состоит в том, чтобы оптимизировать регулярное выражение, чтобы процедура выполнялась чуть быстрее (считается каждая наносекунда).Ребята, вы можете меня просветить?

Примечание: mpls layer и 802.1Q поддерживаются для других видов интерфейсов, unrouted VLANs нет.

Answer 1

Я отвечаю на свой вопрос для дальнейшего ознакомления, хотя кредиты перешли к @piotrekkr, так как именно он указывал путь.Также мои благодарности @JB и @ratchet.В итоге я использовал matches(), а логика с indexOf и несколькими contains была почти такой же быстрой (для меня новость, я всегда предполагал, что одно регулярное выражение будет быстрее, чем несколько вызовов contains).

Вот решение, которое в несколько раз быстрее (по данным профилировщика, при Matcher методах класса расходуется примерно в 7 раз меньше времени):

^(?:unrouted VLAN.++|GigabitEthernet.+?-mpls layer|FastEthernet.+?-802\\.1Q vLAN subif)$

Answer 2

Существуют некоторые алгоритмы поиска строк, которые позволяют вам попытаться найти в строке длиной n k строк одновременно дешевле, чем очевидная стоимость O (n * k).

Они обычно сравнивают переходхэш против списка существующих хэшей ваших слов.Ярким примером этого может служить алгоритм Рабина-Карпа .На вики-странице даже есть раздел об этом.Существуют и более продвинутые версии этого принципа, но его легко понять.

Не знаю, есть ли уже библиотеки на Java, которые делают это (я так думаю), но вот чтоЯ бы попробовал - хотя 5 строк здесь довольно малы (а разный размер тоже усложняет).Поэтому лучше проверить, не является ли хороший поиск строки KMP не быстрым - я думаю, что это действительно лучшее решение (по умолчанию Java-API использует поиск по наивной строке, поэтому используйте lib)

О ваших регулярных выражениях: откатить реализацию регулярных выражений для критичного к производительности поискового кода?Я сомневаюсь, что это хорошая идея.

PS: Если вы опубликуете набор тестов и комплект тестов для вашей проблемы, есть вероятность, что хорошие люди увидят, как сильно они могут победить любимого - сработало раньше ... человекс природой так легко обмануть :)

Answer 3

Если вы должны использовать регулярное выражение для этого, попробуйте перейти на это:

^(?:unrouted VLAN)|(?:GigabitEthernet.+?-mpls layer)|(?:FastEthernet.+?-802\.1Q vLAN subif)

^ сопоставление двигателя с самого начала строки, а не где-либо в строке

.+? делает + неуклюжим

(?:...) делает () группу без захвата

Answer 4

Если ваша проблема в том, что у вас есть ряд длинных строковых констант, которые вы ищете, я бы порекомендовал использовать аналог Java стандартного инструмента C "lex". JFlex .Я не использовал этот конкретный инструмент, и могут быть доступны другие, но это пример того, какой инструмент я бы искал.