Помощь в построении регулярного выражения

#java #регулярные_выражения

Как будет выглядеть регулярное выражения для проверки условия
"Строка содержит маленькие латинские буквы, большие латинские буквы и цифры (выполнение
всех трех условий сразу)." Также интересует быстродействие регулярных выражений. Это
быстро? Сильно быстрее, чем посимвольная проверка? Заранее спасибо!
    

Ответы

Ответ 1

Могу предложить такую регулярку:

(?=.*[a-z])(?=.*[A-Z])(?=.*[0-9])


(?= ... ) — это zero-width positive lookahead assertion, то есть проверка, что строка
в впереди удовлетворяет паттерну, при этом проверка не "съедает" символы при проверке,
то есть после проверки возвращается на изначальную позицию. Скорее всего, это не самый
оптимальный подход: вряд ли движок оптимизирует выражение.

При желании можно написать и выражение попроще:

^((?[a-z])|(?[A-Z])|(?[0-9])|.)+(?(a)|(?!))(?(b)|(?!))(?(c)|(?!))$


Или оптимальнее:

^(?>(?:(?[a-z])|(?[A-Z])|(?[0-9])|.)+)(?(a)|(?!))(?(b)|(?!))(?(c)|(?!))$


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



RE: ReinRaus

Фига себе в джаве тормозной стандартный регекс. :)

Перевёл один-в-один в дотнет (плюс оптимизировал вторую регулярку: там был один лишний
захват и, как следствие, баг в реализации от @ReinRaus, возникший при замене именованных
групп на индексные):

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Text.RegularExpressions;

namespace RegexPasswordPerf
{
    class Program
    {
        static void Main (string[] args)
        {
            const int Loops = 30000;
            const string Text = "AaluhfDnaoufbicbIHBDIHBKJXNdCJKfBCNCNX5BCHBAHIBAVIsdniuhuygvD6w489bgtvdihfcbsigdbcsihcgfisyg8AaluhfDnaoufbicbIHBDIHBKJXNdCJKfBCNCNX5BCHBAHIBAVIsdniuhuygvD6w489bgtvdihfcbsigdbcsihcgfisyg8AaluhfDnaoufbicbIHBDIHBKJXNdCJKfBCNCNX5BCHBAHIBAVIsdniuhuygvD6w489bgtvdihfcbsigdbcsihcgfisyg8AaluhfDnaoufbicbIHBDIHBKJXNdCJKfBCNCNX5BCHBAHIBAVIsdniuhuygvD6w489bgtvdihfcbsigdbcsihcgfisyg8AaluhfDnaoufbicbIHBDIHBKJXNdCJKfBCNCNX5BCHBAHIBAVIsdniuhuygvD6w489bgtvdihfcbsigdbcsihcgfisyg8AaluhfDnaoufbicbIHBDIHBKJXNdCJKfBCNCNX5BCHBAHIBAVIsdniuhuygvD6w489bgtvdihfcbsigdbcsihcgfisyg8AaluhfDnaoufbicbIHBDIHBKJXNdCJKfBCNCNX5BCHBAHIBAVIsdniuhuygvD6w489bgtvdihfcbsigdbcsihcgfisyg8AaluhfDnaoufbicbIHBDIHBKJXNdCJKfBCNCNX5BCHBAHIBAVIsdniuhuygvD6w489bgtvdihfcbsigdbcsihcgfisyg8AaluhfDnaoufbicbIHBDIHBKJXNdCJKfBCNCNX5BCHBAHIBAVIsdniuhuygvD6w489bgtvdihfcbsigdbcsihcgfisyg8AaluhfDnaoufbicbIHBDIHBKJXNdCJKfBCNCNX5BCHBAHIBAVIsdniuhuygvD6w489bgtvdihfcbsigdbcsihcgfisyg8AaluhfDnaoufbicbIHBDIHBKJXNdCJKfBCNCNX5BCHBAHIBAVIsdniuhuygvD6w489bgtvdihfcbsigdbcsihcgfisyg8";
            //const string Text = "AaluhfDnaoufbicbIHBDIHBKJXNdCJKfB1";
            var regexes = new Dictionary {
                { "Discord 1", "^(([a-z])|([A-Z])|([0-9])|.)+(?(1)|(?!))(?(2)|(?!))(?(3)|(?!))$" },
                { "Discord 2", "^(?>(?:([a-z])|([A-Z])|([0-9])|.)+)(?(1)|(?!))(?(2)|(?!))(?(3)|(?!))$" },
                { "ReinRaus 1", "^(?=(?>[^a-z]*)[a-z])(?=(?>[^A-Z]*)[A-Z])(?=(?>\\D*)\\d)(?>[a-zA-Z0-9]+)$" },
                { "ReinRaus 2", "^(?:([a-z])|([A-Z])|([0-9]))(?(1)(?>[a-z]*)(?:([A-Z])|([0-9]))(?(4)(?>[a-zA-Z]*)[0-9]‌​(?>[a-zA-Z0-9]*)$|(?(5)(?>[a-z0-9]*)[A-Z](?>[a-zA-Z0-9]*)$|(?!))))(?(2)(?>[A-Z]*)(?:([a-z])|(‌​[0-9]))(?(6)(?>[a-zA-Z]*)[0-9](?>[a-zA-Z0-9]*)$|(?(7)(?>[A-Z0-9]*)[a-z](?>[a-zA-Z0-9]*)$|(?!)‌​)))(?(3)(?>[0-9]*)(?:([A-Z])|([a-z]))(?(8)(?>[0-9A-Z]*)[a-z](?>[a-zA-Z0-9]*)$|(?(9)(?>[0-9a-z‌​]*)[A-Z](?>[a-zA-Z0-9]*)$|(?!))))" },
            };

            foreach (var entry in regexes) {
                var regex = new Regex(entry.Value, RegexOptions.Compiled);
                bool isCorrect = false;

                var sw = new Stopwatch();
                sw.Start();
                for (int i = 0; i < Loops; i++)
                    isCorrect = regex.IsMatch(Text);
                sw.Stop();

                Console.WriteLine("{0}\t{1}\t{2}", entry.Key, sw.ElapsedMilliseconds,
isCorrect);
            }
        }
    }
}


Результат:

Discord 1       3378    True
Discord 2       2518    True
ReinRaus 1      738     True
ReinRaus 2      721     True


Если строку сделать больше похожей на пароль, то есть короче в несколько раз, то
разрыв будет раза в два-три, а не три-четыре:

Discord 1       1247    True
Discord 2       1037    True
ReinRaus 1      650     True
ReinRaus 2      383     True


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

string s = string.Join("\n", m.Groups
    .Cast().Select(g => string.Format("{0}: {1}", g.Index, string.Join(",
", g.Captures
        .Cast().Select(c => c.Value)))));


То можно увидеть это:

0: AaluhfDnaoufbicbIHBDIHBKJXNdCJKfBCNCNX5BCHBAHIBAVIsdniuhuygvD6w489bgtvdihfcbsigdbcsihcgfisyg8AaluhfDnaoufbicbIHBDIHBKJXNdCJKfBCNCNX5BCHBAHIBAVIsdniuhuygvD6w489bgtvdihfcbsigdbcsihcgfisyg8AaluhfDnaoufbicbIHBDIHBKJXNdCJKfBCNCNX5BCHBAHIBAVIsdniuhuygvD6w489bgtvdihfcbsigdbcsihcgfisyg8AaluhfDnaoufbicbIHBDIHBKJXNdCJKfBCNCNX5BCHBAHIBAVIsdniuhuygvD6w489bgtvdihfcbsigdbcsihcgfisyg8AaluhfDnaoufbicbIHBDIHBKJXNdCJKfBCNCNX5BCHBAHIBAVIsdniuhuygvD6w489bgtvdihfcbsigdbcsihcgfisyg8AaluhfDnaoufbicbIHBDIHBKJXNdCJKfBCNCNX5BCHBAHIBAVIsdniuhuygvD6w489bgtvdihfcbsigdbcsihcgfisyg8AaluhfDnaoufbicbIHBDIHBKJXNdCJKfBCNCNX5BCHBAHIBAVIsdniuhuygvD6w489bgtvdihfcbsigdbcsihcgfisyg8AaluhfDnaoufbicbIHBDIHBKJXNdCJKfBCNCNX5BCHBAHIBAVIsdniuhuygvD6w489bgtvdihfcbsigdbcsihcgfisyg8AaluhfDnaoufbicbIHBDIHBKJXNdCJKfBCNCNX5BCHBAHIBAVIsdniuhuygvD6w489bgtvdihfcbsigdbcsihcgfisyg8AaluhfDnaoufbicbIHBDIHBKJXNdCJKfBCNCNX5BCHBAHIBAVIsdniuhuygvD6w489bgtvdihfcbsigdbcsihcgfisyg8AaluhfDnaoufbicbIHBDIHBKJXNdCJKfBCNCNX5BCHBAHIBAVIsdniuhuygvD6w489bgtvdihfcbsigdbcsihcgfisyg8
1021: a, l, u, h, f, n, a, o, u, f, b, i, c, b, d, f, s, d, n, i, u, h, u, y, g,
v, w, b, g, t, v, d, i, h, f, c, b, s, i, g, d, b, c, s, i, h, c, g, f, i, s, y, g,
a, l, u, h, f, n, a, o, u, f, b, i, c, b, d, f, s, d, n, i, u, h, u, y, g, v, w, b,
g, t, v, d, i, h, f, c, b, s, i, g, d, b, c, s, i, h, c, g, f, i, s, y, g, a, l, u,
h, f, n, a, o, u, f, b, i, c, b, d, f, s, d, n, i, u, h, u, y, g, v, w, b, g, t, v,
d, i, h, f, c, b, s, i, g, d, b, c, s, i, h, c, g, f, i, s, y, g, a, l, u, h, f, n,
a, o, u, f, b, i, c, b, d, f, s, d, n, i, u, h, u, y, g, v, w, b, g, t, v, d, i, h,
f, c, b, s, i, g, d, b, c, s, i, h, c, g, f, i, s, y, g, a, l, u, h, f, n, a, o, u,
f, b, i, c, b, d, f, s, d, n, i, u, h, u, y, g, v, w, b, g, t, v, d, i, h, f, c, b,
s, i, g, d, b, c, s, i, h, c, g, f, i, s, y, g, a, l, u, h, f, n, a, o, u, f, b, i,
c, b, d, f, s, d, n, i, u, h, u, y, g, v, w, b, g, t, v, d, i, h, f, c, b, s, i, g,
d, b, c, s, i, h, c, g, f, i, s, y, g, a, l, u, h, f, n, a, o, u, f, b, i, c, b, d,
f, s, d, n, i, u, h, u, y, g, v, w, b, g, t, v, d, i, h, f, c, b, s, i, g, d, b, c,
s, i, h, c, g, f, i, s, y, g, a, l, u, h, f, n, a, o, u, f, b, i, c, b, d, f, s, d,
n, i, u, h, u, y, g, v, w, b, g, t, v, d, i, h, f, c, b, s, i, g, d, b, c, s, i, h,
c, g, f, i, s, y, g, a, l, u, h, f, n, a, o, u, f, b, i, c, b, d, f, s, d, n, i, u,
h, u, y, g, v, w, b, g, t, v, d, i, h, f, c, b, s, i, g, d, b, c, s, i, h, c, g, f,
i, s, y, g, a, l, u, h, f, n, a, o, u, f, b, i, c, b, d, f, s, d, n, i, u, h, u, y,
g, v, w, b, g, t, v, d, i, h, f, c, b, s, i, g, d, b, c, s, i, h, c, g, f, i, s, y,
g, a, l, u, h, f, n, a, o, u, f, b, i, c, b, d, f, s, d, n, i, u, h, u, y, g, v, w,
b, g, t, v, d, i, h, f, c, b, s, i, g, d, b, c, s, i, h, c, g, f, i, s, y, g
990: A, D, I, H, B, D, I, H, B, K, J, X, N, C, J, K, B, C, N, C, N, X, B, C, H, B,
A, H, I, B, A, V, I, D, A, D, I, H, B, D, I, H, B, K, J, X, N, C, J, K, B, C, N, C,
N, X, B, C, H, B, A, H, I, B, A, V, I, D, A, D, I, H, B, D, I, H, B, K, J, X, N, C,
J, K, B, C, N, C, N, X, B, C, H, B, A, H, I, B, A, V, I, D, A, D, I, H, B, D, I, H,
B, K, J, X, N, C, J, K, B, C, N, C, N, X, B, C, H, B, A, H, I, B, A, V, I, D, A, D,
I, H, B, D, I, H, B, K, J, X, N, C, J, K, B, C, N, C, N, X, B, C, H, B, A, H, I, B,
A, V, I, D, A, D, I, H, B, D, I, H, B, K, J, X, N, C, J, K, B, C, N, C, N, X, B, C,
H, B, A, H, I, B, A, V, I, D, A, D, I, H, B, D, I, H, B, K, J, X, N, C, J, K, B, C,
N, C, N, X, B, C, H, B, A, H, I, B, A, V, I, D, A, D, I, H, B, D, I, H, B, K, J, X,
N, C, J, K, B, C, N, C, N, X, B, C, H, B, A, H, I, B, A, V, I, D, A, D, I, H, B, D,
I, H, B, K, J, X, N, C, J, K, B, C, N, C, N, X, B, C, H, B, A, H, I, B, A, V, I, D,
A, D, I, H, B, D, I, H, B, K, J, X, N, C, J, K, B, C, N, C, N, X, B, C, H, B, A, H,
I, B, A, V, I, D, A, D, I, H, B, D, I, H, B, K, J, X, N, C, J, K, B, C, N, C, N, X,
B, C, H, B, A, H, I, B, A, V, I, D
1022: 5, 6, 4, 8, 9, 8, 5, 6, 4, 8, 9, 8, 5, 6, 4, 8, 9, 8, 5, 6, 4, 8, 9, 8, 5,
6, 4, 8, 9, 8, 5, 6, 4, 8, 9, 8, 5, 6, 4, 8, 9, 8, 5, 6, 4, 8, 9, 8, 5, 6, 4, 8, 9,
8, 5, 6, 4, 8, 9, 8, 5, 6, 4, 8, 9, 8


Это удобно, но не лучшим образом сказывается на производительности — особенно если
соревноваться с регулярками, которые все совпадения не сохраняют. Для полного удовлетворения
любопытства надо будет найти плюсовые или шарповые регексы, которые построены ради
скорости, а не удобства. Если память не изменяет, регулярки из boost по умолчанию такой
фигнёй не занимаются, но есть опция для компиляции.


Ответ 2

Вернусь к давно забытой теме, потому что где-то в дебрях чата я выкладывал весьма
неплохую регулярку по данному вопросу.
Разъяснять по какому принципу построены регулярные выражения не буду - просто приведу
сравнение производительности.  

Код бенчмарка очень прост:  

import java.util.HashMap;
import java.util.Map.Entry;
//import java.util.regex.Pattern;
import jregex.Pattern;

public class test {

    public static void main(String[] args) {
        int loops = 30000;
        long startTime, endTime, diffTime;
        String key, value;
        Pattern regex;
        boolean isCorrect = false;
        String text = "AaluhfDnaoufbicbIHBDIHBKJXNdCJKfBCNCNX5BCHBAHIBAVIsdniuhuygvD6w489bgtvdihfcbsigdbcsihcgfisyg8AaluhfDnaoufbicbIHBDIHBKJXNdCJKfBCNCNX5BCHBAHIBAVIsdniuhuygvD6w489bgtvdihfcbsigdbcsihcgfisyg8AaluhfDnaoufbicbIHBDIHBKJXNdCJKfBCNCNX5BCHBAHIBAVIsdniuhuygvD6w489bgtvdihfcbsigdbcsihcgfisyg8AaluhfDnaoufbicbIHBDIHBKJXNdCJKfBCNCNX5BCHBAHIBAVIsdniuhuygvD6w489bgtvdihfcbsigdbcsihcgfisyg8AaluhfDnaoufbicbIHBDIHBKJXNdCJKfBCNCNX5BCHBAHIBAVIsdniuhuygvD6w489bgtvdihfcbsigdbcsihcgfisyg8AaluhfDnaoufbicbIHBDIHBKJXNdCJKfBCNCNX5BCHBAHIBAVIsdniuhuygvD6w489bgtvdihfcbsigdbcsihcgfisyg8AaluhfDnaoufbicbIHBDIHBKJXNdCJKfBCNCNX5BCHBAHIBAVIsdniuhuygvD6w489bgtvdihfcbsigdbcsihcgfisyg8AaluhfDnaoufbicbIHBDIHBKJXNdCJKfBCNCNX5BCHBAHIBAVIsdniuhuygvD6w489bgtvdihfcbsigdbcsihcgfisyg8AaluhfDnaoufbicbIHBDIHBKJXNdCJKfBCNCNX5BCHBAHIBAVIsdniuhuygvD6w489bgtvdihfcbsigdbcsihcgfisyg8AaluhfDnaoufbicbIHBDIHBKJXNdCJKfBCNCNX5BCHBAHIBAVIsdniuhuygvD6w489bgtvdihfcbsigdbcsihcgfisyg8AaluhfDnaoufbicbIHBDIHBKJXNdCJKfBCNCNX5BCHBAHIBAVIsdniuhuygvD6w489bgtvdihfcbsigdbcsihcgfisyg8";

        HashMap  regexs = getRegexs();

        for( Entry entry : regexs.entrySet() ) {
            key = entry.getKey();
            value = entry.getValue();
            regex = new Pattern( value );
            //regex = Pattern.compile( value );
            startTime = System.currentTimeMillis();
            for( int i=0; i < loops; i++ ) {
                isCorrect = regex.matcher( text ).matches();
            }
            endTime = System.currentTimeMillis();
            diffTime = endTime - startTime;
            System.out.println( key + "\t"+ diffTime + "\t" + isCorrect );
        }
    }
}


Можно увидеть, что я использовал сторонний модуль jregex.Pattern. Он старый, не развивается
с 2002 года, но он более соответствует PCRE и дает производительность в 5 раз выше,
чем java.util.regex, ну просто мне очень хотелось поддержку условных выражений (?(N)then|else).
Этот модуль не поддерживает сверхжадную квантификацию, поэтому пришлось заменить ее
на атомарные группировки.
Все приведенные ответы требуют наличие условий, поэтому применение данного модуля
было вынужденной необходимостью, но у него к сожалению видимо жестко проседает производительность
на создании точек возврата, поэтому регулярные выражения @Discord заметно медленнее
моих :( Печалька :( Честным был бы замер скорости выражений в PHP или Perl, но в Java
поддержка PCRE только из-под палки :(  

public static HashMap  getRegexs () {
    HashMap  result = new HashMap ();
    result.put( "Discord 1", "^(([a-z])|([A-Z])|([0-9])|.)+(?(1)|(?!))(?(2)|(?!))(?(3)|(?!))$");
    result.put( "Discord 2", "^(?>(([a-z])|([A-Z])|([0-9])|.)+)(?(1)|(?!))(?(2)|(?!))(?(3)|(?!))$" );
    result.put( "ReinRaus 1", "^(?=(?>[^a-z]*)[a-z])(?=(?>[^A-Z]*)[A-Z])(?=(?>\\D*)\\d)(?>[a-zA-Z0-9]+)$");
    result.put( "ReinRaus 2", "^(?:([a-z])|([A-Z])|([0-9]))(?(1)(?>[a-z]*)(?:([A-Z])|([0-9]))(?(4)(?>[a-zA-Z]*)[0-9]‌​(?>[a-zA-Z0-9]*)$|(?(5)(?>[a-z0-9]*)[A-Z](?>[a-zA-Z0-9]*)$|(?!))))(?(2)(?>[A-Z]*)(?:([a-z])|(‌​[0-9]))(?(6)(?>[a-zA-Z]*)[0-9](?>[a-zA-Z0-9]*)$|(?(7)(?>[A-Z0-9]*)[a-z](?>[a-zA-Z0-9]*)$|(?!)‌​)))(?(3)(?>[0-9]*)(?:([A-Z])|([a-z]))(?(8)(?>[0-9A-Z]*)[a-z](?>[a-zA-Z0-9]*)$|(?(9)(?>[0-9a-z‌​]*)[A-Z](?>[a-zA-Z0-9]*)$|(?!))))" );
    return result;
}


Результат:  

Discord 1   5096    true
Discord 2   4718    true
ReinRaus 1  72  true
ReinRaus 2  62  true


Если нужен именно встроенный движок регулярных выражений, то единственным вариантом
будет ReinRaus 1. У меня на jregex при цикле 3000000 повторений это выражение дает
в среднем время 5500ms, а на java.util.regex в среднем 38000ms, что в 7 раз медленнее.