3

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

2 ответа 2

4

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

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

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

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

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

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

^(?>(?:(?<a>[a-z])|(?<b>[A-Z])|(?<c>[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<string, string> {
                { "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<Group>().Select(g => string.Format("{0}: {1}", g.Index, string.Join(", ", g.Captures
        .Cast<Capture>().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 по умолчанию такой фигнёй не занимаются, но есть опция для компиляции.

24
  • @ReinRaus Добавил объяснение.
    – Kyubey
    14 мая 2015 в 18:19
  • Проверьте его на тексте lorem ?#%%^ ipsum ^*&
    – ReinRaus
    14 мая 2015 в 18:21
  • Подскажите, как работает Ваше регулярное выражение — основная проблема регулярок. Напишите цикл и будет вам счастье.
    – Zelta
    14 мая 2015 в 18:22
  • @ReinRaus, все верно, не матчится.
    – Zelta
    14 мая 2015 в 18:25
  • @Zelta я прекрасно понимаю, как работает предложенное автором регулярное выражение. Я лишь пытаюсь натолкнуть его на мысль, что он пишет что-то не то.
    – ReinRaus
    14 мая 2015 в 18:50
4

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

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

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 <String, String> regexs = getRegexs();

        for( Entry<String, String> 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 <String, String> getRegexs () {
    HashMap <String, String> result = new HashMap <String, String>();
    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 раз медленнее.

1
  • Обновил свой ответ. :)
    – Kyubey
    26 мая 2015 в 15:58

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.