¿Cómo puedo acelerar este ciclo? ¿Hay una clase para reemplazar múltiples términos a la vez?

Question

El bucle:

var pattern = _dict[key]; 
string before; 
do 
{ 
    before = pattern; 
    foreach (var pair in _dict) 
     if (key != pair.Key) 
      pattern = pattern.Replace(string.Concat("{", pair.Key, "}"), string.Concat("(", pair.Value, ")")); 
} while (pattern != before); 
return pattern; 

Simplemente hace una repetida de buscar y reemplazar en un manojo de llaves. El diccionario es solo <string,string>.

Puedo ver 2 mejoras a esto.

1. Cada vez que hacemos pattern.Replace vuelve a buscar desde el comienzo de la cadena. Sería mejor si cuando alcanzara el primer {, simplemente miraría a través de la lista de claves para encontrar una coincidencia (quizás usando una búsqueda binaria), y luego reemplazaría la apropiada.
2. El bit pattern != before es cómo compruebo si se reemplazó algo durante esa iteración. Si la función pattern.Replace devolvió cuántas sustituciones sucedieron, no las necesitaría.

Sin embargo ... Realmente no quiero escribir una gran clase de cosas desagradables para hacer todo eso. Este debe ser un escenario bastante común? ¿Hay alguna solución existente?

---

clase completa

Gracias a Elián Ebbing y ChrisWue.

class FlexDict : IEnumerable<KeyValuePair<string,string>> 
{ 
    private Dictionary<string, string> _dict = new Dictionary<string, string>(); 
    private static readonly Regex _re = new Regex(@"{([_a-z][_a-z0-9-]*)}", RegexOptions.Compiled | RegexOptions.IgnoreCase); 

    public void Add(string key, string pattern) 
    { 
     _dict[key] = pattern; 
    } 

    public string Expand(string pattern) 
    { 
     pattern = _re.Replace(pattern, match => 
      { 
       string key = match.Groups[1].Value; 

       if (_dict.ContainsKey(key)) 
        return "(" + Expand(_dict[key]) + ")"; 

       return match.Value; 
      }); 

     return pattern; 
    } 

    public string this[string key] 
    { 
     get { return Expand(_dict[key]); } 
    } 

    public IEnumerator<KeyValuePair<string, string>> GetEnumerator() 
    { 
     foreach (var p in _dict) 
      yield return new KeyValuePair<string,string>(p.Key, this[p.Key]); 
    } 

    IEnumerator IEnumerable.GetEnumerator() 
    { 
     return GetEnumerator(); 
    } 
} 

Ejemplo de Uso

class Program 
{ 
    static void Main(string[] args) 
    { 
     var flex = new FlexDict 
      { 
       {"h", @"[0-9a-f]"}, 
       {"nonascii", @"[\200-\377]"}, 
       {"unicode", @"\\{h}{1,6}(\r\n|[ \t\r\n\f])?"}, 
       {"escape", @"{unicode}|\\[^\r\n\f0-9a-f]"}, 
       {"nmstart", @"[_a-z]|{nonascii}|{escape}"}, 
       {"nmchar", @"[_a-z0-9-]|{nonascii}|{escape}"}, 
       {"string1", @"""([^\n\r\f\\""]|\\{nl}|{escape})*"""}, 
       {"string2", @"'([^\n\r\f\\']|\\{nl}|{escape})*'"}, 
       {"badstring1", @"""([^\n\r\f\\""]|\\{nl}|{escape})*\\?"}, 
       {"badstring2", @"'([^\n\r\f\\']|\\{nl}|{escape})*\\?"}, 
       {"badcomment1", @"/\*[^*]*\*+([^/*][^*]*\*+)*"}, 
       {"badcomment2", @"/\*[^*]*(\*+[^/*][^*]*)*"}, 
       {"baduri1", @"url\({w}([!#$%&*-\[\]-~]|{nonascii}|{escape})*{w}"}, 
       {"baduri2", @"url\({w}{string}{w}"}, 
       {"baduri3", @"url\({w}{badstring}"}, 
       {"comment", @"/\*[^*]*\*+([^/*][^*]*\*+)*/"}, 
       {"ident", @"-?{nmstart}{nmchar}*"}, 
       {"name", @"{nmchar}+"}, 
       {"num", @"[0-9]+|[0-9]*\.[0-9]+"}, 
       {"string", @"{string1}|{string2}"}, 
       {"badstring", @"{badstring1}|{badstring2}"}, 
       {"badcomment", @"{badcomment1}|{badcomment2}"}, 
       {"baduri", @"{baduri1}|{baduri2}|{baduri3}"}, 
       {"url", @"([!#$%&*-~]|{nonascii}|{escape})*"}, 
       {"s", @"[ \t\r\n\f]+"}, 
       {"w", @"{s}?"}, 
       {"nl", @"\n|\r\n|\r|\f"}, 

       {"A", @"a|\\0{0,4}(41|61)(\r\n|[ \t\r\n\f])?"}, 
       {"C", @"c|\\0{0,4}(43|63)(\r\n|[ \t\r\n\f])?"}, 
       {"D", @"d|\\0{0,4}(44|64)(\r\n|[ \t\r\n\f])?"}, 
       {"E", @"e|\\0{0,4}(45|65)(\r\n|[ \t\r\n\f])?"}, 
       {"G", @"g|\\0{0,4}(47|67)(\r\n|[ \t\r\n\f])?|\\g"}, 
       {"H", @"h|\\0{0,4}(48|68)(\r\n|[ \t\r\n\f])?|\\h"}, 
       {"I", @"i|\\0{0,4}(49|69)(\r\n|[ \t\r\n\f])?|\\i"}, 
       {"K", @"k|\\0{0,4}(4b|6b)(\r\n|[ \t\r\n\f])?|\\k"}, 
       {"L", @"l|\\0{0,4}(4c|6c)(\r\n|[ \t\r\n\f])?|\\l"}, 
       {"M", @"m|\\0{0,4}(4d|6d)(\r\n|[ \t\r\n\f])?|\\m"}, 
       {"N", @"n|\\0{0,4}(4e|6e)(\r\n|[ \t\r\n\f])?|\\n"}, 
       {"O", @"o|\\0{0,4}(4f|6f)(\r\n|[ \t\r\n\f])?|\\o"}, 
       {"P", @"p|\\0{0,4}(50|70)(\r\n|[ \t\r\n\f])?|\\p"}, 
       {"R", @"r|\\0{0,4}(52|72)(\r\n|[ \t\r\n\f])?|\\r"}, 
       {"S", @"s|\\0{0,4}(53|73)(\r\n|[ \t\r\n\f])?|\\s"}, 
       {"T", @"t|\\0{0,4}(54|74)(\r\n|[ \t\r\n\f])?|\\t"}, 
       {"U", @"u|\\0{0,4}(55|75)(\r\n|[ \t\r\n\f])?|\\u"}, 
       {"X", @"x|\\0{0,4}(58|78)(\r\n|[ \t\r\n\f])?|\\x"}, 
       {"Z", @"z|\\0{0,4}(5a|7a)(\r\n|[ \t\r\n\f])?|\\z"}, 
       {"Z", @"z|\\0{0,4}(5a|7a)(\r\n|[ \t\r\n\f])?|\\z"}, 

       {"CDO", @"<!--"}, 
       {"CDC", @"-->"}, 
       {"INCLUDES", @"~="}, 
       {"DASHMATCH", @"\|="}, 
       {"STRING", @"{string}"}, 
       {"BAD_STRING", @"{badstring}"}, 
       {"IDENT", @"{ident}"}, 
       {"HASH", @"#{name}"}, 
       {"IMPORT_SYM", @"@{I}{M}{P}{O}{R}{T}"}, 
       {"PAGE_SYM", @"@{P}{A}{G}{E}"}, 
       {"MEDIA_SYM", @"@{M}{E}{D}{I}{A}"}, 
       {"CHARSET_SYM", @"@charset\b"}, 
       {"IMPORTANT_SYM", @"!({w}|{comment})*{I}{M}{P}{O}{R}{T}{A}{N}{T}"}, 
       {"EMS", @"{num}{E}{M}"}, 
       {"EXS", @"{num}{E}{X}"}, 
       {"LENGTH", @"{num}({P}{X}|{C}{M}|{M}{M}|{I}{N}|{P}{T}|{P}{C})"}, 
       {"ANGLE", @"{num}({D}{E}{G}|{R}{A}{D}|{G}{R}{A}{D})"}, 
       {"TIME", @"{num}({M}{S}|{S})"}, 
       {"PERCENTAGE", @"{num}%"}, 
       {"NUMBER", @"{num}"}, 
       {"URI", @"{U}{R}{L}\({w}{string}{w}\)|{U}{R}{L}\({w}{url}{w}\)"}, 
       {"BAD_URI", @"{baduri}"}, 
       {"FUNCTION", @"{ident}\("}, 
      }; 

     var testStrings = new[] { @"""str""", @"'str'", "5", "5.", "5.0", "a", "alpha", "url(hello)", 
      "url(\"hello\")", "url(\"blah)", @"\g", @"/*comment*/", @"/**/", @"<!--", @"-->", @"~=", 
      "|=", @"#hash", "@import", "@page", "@media", "@charset", "!/*iehack*/important"}; 

     foreach (var pair in flex) 
     { 
      Console.WriteLine("{0}\n\t{1}\n", pair.Key, pair.Value); 
     } 

     var sw = Stopwatch.StartNew(); 
     foreach (var str in testStrings) 
     { 
      Console.WriteLine("{0} matches: ", str); 
      foreach (var pair in flex) 
      { 
       if (Regex.IsMatch(str, "^(" + pair.Value + ")$", RegexOptions.IgnoreCase | RegexOptions.ExplicitCapture)) 
        Console.WriteLine(" {0}", pair.Key); 
      } 
     } 
     Console.WriteLine("\nRan in {0} ms", sw.ElapsedMilliseconds); 
     Console.ReadLine(); 
    } 
} 

Propósito

Para la construcción de las expresiones regulares complejos que pueden extenderse unos de otros. A saber, estoy tratando de implementar the css spec.

Answer 1

creo que sería más rápido si nos fijamos para que se produzcan hechos de {foo} utilizando una expresión regular, y luego usar un MatchEvaluator que sustituye a la {foo} si foo pasa a ser un elemento clave en el diccionario.

que tienen actualmente ningún estudio visual aquí, pero creo que esto es funcionalmente equivalente con el ejemplo de código:

var pattern = _dict[key]; 
bool isChanged = false; 

do 
{ 
    isChanged = false; 

    pattern = Regex.Replace(pattern, "{([^}]+)}", match => { 
     string matchKey = match.Groups[1].Value; 

     if (matchKey != key && _dict.ContainsKey(matchKey)) 
     { 
      isChanged = true; 
      return "(" + _dict[matchKey] + ")"; 
     } 

     return match.Value; 
    }); 
} while (isChanged); 

¿Puedo preguntarle por qué necesita el do/while? ¿El valor de una clave en el diccionario puede contener {placeholders} que deba reemplazarse? ¿Puedes estar seguro de que no te quedas atascado en un bucle infinito donde la clave "A" contiene "Blahblah {B}" y la clave "B" contiene "Blahblah {A}"?

Editar: mejoras adicionales serían:

• Usando una expresión regular precompilado.
• Uso de la recursión en lugar de un bucle (consulte ChrisWue's comentario).
• Usando _dict.TryGetValue(), como en el código Guffa's.

Terminará con un algoritmo O (n) donde n es el tamaño de la salida, por lo que no puede hacer mucho mejor que esto.

Answer 2

¿Podría usar PLINQ en absoluto?

Algo a lo largo de las líneas de:

var keys = dict.KeyCollection.Where(k => k != key); 
bool replacementMade = keys.Any(); 

foreach(var k in keys.AsParallel(),() => {replacement code}) 

Answer 3

se puede implementar el algoritmo siguiente:

1. Buscar { en cadena de origen
2. Copiar todo hasta { a StringBuilder
3. encontrar los correspondientes } (la búsqueda se hace desde la última posición)
4. valor de comparación entre { y } a las llaves en su diccionario
5. • Si coincide con copia a Generador de cadenas ( + Value + )
   • más copie de cadena de origen
6. Si extremo cadena de origen no se alcanza, vaya al paso 1

Answer 4

Usted shou Debería poder usar una expresión regular para encontrar las coincidencias. Luego también puede hacer uso de la búsqueda rápida del diccionario y no solo usarlo como una lista.

var pattern = _dict[key]; 
bool replaced = false; 
do { 
    pattern = Regex.Replace(pattern, @"\{([^\}]+)\}", m => { 
    string k = m.Groups[1].Value; 
    string value; 
    if (k != key && _dict.TryGetValue(k, out value) { 
     replaced = true; 
     return "(" + value + ")"; 
    } else { 
     return "{" + k + "}"; 
    } 
    }); 
} while (replaced); 
return pattern;