Самый быстрый способ сравнить одну строку с группой символов подстановки - PullRequest
Новая
       42

Самый быстрый способ сравнить одну строку с группой символов подстановки

4 голосов
/ 02 апреля 2012

У меня есть словарь, и мой ключ - это строка с подстановочными знаками.Я хочу знать, совпадает ли одна строка с любым ключом в словаре.

Пример: 

String str = "Really Large String";
Dictionary dic = new Dictionary<String, MyClass>();
dic.Add("First+Match*", new MyClass());
dic.Add("*Large*", new MyClass());

Редактировать: Я хочу сделать что-то вроде: 

foreach(var s in dic.Keys){
  if(str.Match(s))
    //Do Something
}

Ответы [ 3 ]

2 голосов
/ 02 апреля 2012

Почему бы и нет, 

var dic = Dictionary<Regex, MyClass>()
dic.Add(new Regex("..."), new MyClass)
....

foreach(var match in dic.Keys.Where(k => k.IsMatch(str)))
{
    var myClass = dic[match];
    ....
}

Теперь вопрос, зачем вообще использовать словарь, почему бы не расширять MyClass для сопоставления с самой строкой, возможно, с Predicate, называемым Match.

var matchers = new HashSet<MyClass>();
matchers.Add(new MyClass("some regex?");
....

foreach(var match in matchers.Where(Match(str)))
{
    ....
}

РЕДАКТИРОВАТЬ

Если вы хотите только первый матч, вы можете использовать FirstOrDefault вместо Where. 

var firstMatch = matchers.FirstOrDefault(Match(str))
if (firstMatch != null)
{
    ....
}

Однако это сделает порядок списка значимым.

РЕДАКТИРОВАТЬ 2

Частичная реализация MyClass для включения предиката Match может быть... 

partial class MyClass
{
    private readonly RegEx matcher;

    public MyClass(string regEx)
    {
        matcher = new RegEx(regEx);
    }

    public bool Match(string value)
    {
        return matcher.IsMatch(value);
    }
}
2 голосов
/ 02 апреля 2012

Вы можете использовать RegEx, просто преобразовав строку с подстановочными знаками в шаблон регулярного выражения (я предполагаю, что вы хотите использовать довольно старые стандартные"*" и "?" Подстановочные знаки): 

public static string ToRegEx(string pattern)
{
    return Regex.Escape(pattern).Replace("\\*", ".*").Replace("\\?", ".");
}
0 голосов
/ 02 апреля 2012

Это объяснение будет немного длиннее, чем мне хотелось бы, но в таком случае может быть очень полезно полностью понять, что происходит под капотом.Поскольку конкретный подход выглядит эффективным в вашем исходном коде, это не значит, что процессор видит его так же.Когда вы беспокоитесь о скорости выполнения побайтовых байтов, вы должны понимать, что происходит на уровне, на котором эта операция будет фактически выполняться.Все, что выше этого уровня, является просто семантикой и, в конечном счете, прославленными макросами, которые не дадут вам точной картины того, что вы на самом деле создаете.

Процессоры Intel / AMD имеют набор инструкций повторного сканирования, которые позволяютВы должны установить указатель, поместить байт в регистр, установить количество байтов для сканирования, и внутренний процессор отключается и запускает сканирование как одну внутреннюю инструкцию, сканируя байт на байт, пока не будет найдено совпадение или несоответствие(или счетчик заканчивается).Когда счетчик заканчивается, это может быть грязный процесс, чтобы настроить ваши указатели и обработать «критерии не выполнены; у меня закончился счетчик!»состояние;это не повлияет на ваш код напрямую, но может повлиять на время выполнения, если вы выполняете много отдельных поисков в цикле.По этой причине никогда не бывает плохой идеей минимизировать количество выполняемых поисковых запросов.Это не очень важный фактор, но он может учитывать.

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

Проблема здесьв том, что у вас нет большого прямого контроля над этими вещами.Какой бы язык вы ни использовали, он, скорее всего, будет использовать самый медленный из возможных подходов с применением грубой силы: взять байт, посмотреть на него, взять следующий байт, зевать, зевать, зевать.Если так делает ваш язык (большинство так делают), то не будет большой разницы между любыми двумя вариантами выбора методологии кодирования: они уже все застряли в фундаменте производительности.Если бы вы оказались в ситуации, когда вы могли бы вставить блок кода сборки, вы получили бы огромную выгоду.Но большинству людей запрещено делать это, потому что в 1985 году это считалось незаконным.Конечно, нужно учитывать 32- и 64-битные проблемы, но их можно учитывать.В любом случае, суть в том, что если вы можете точно узнать, что делает ваш конкретный язык, то примите это во внимание.Если он использует метод сравнения строк, то битва уже проиграна, и большая часть того, что вы делаете для настройки своего кода, вероятно, не будет иметь большого эффекта.

...