examples - regex performance c#
System.OutOfMemoryException al generar permutaciones (4)
Aquí hay una solución simple que es computacional y eficiente en memoria.
- En lugar de generar la lista completa de permutaciones y luego buscar coincidencias, usar un iterador nos permite procesar las posibles coincidencias de permutación a medida que se generan.
- Con un poco de retroceso, solo se generan las permutaciones que tienen la oportunidad de coincidir con su expresión regular.
Todo lo que necesita es una expresión regular adicional que acepte candidatos parciales. Debería aceptar cadenas que podrían convertirse en una coincidencia si se agregan caracteres. (Sería bueno tener algo como hitEnd () en Java, que hace exactamente esto. Esto eliminaría la necesidad de esa expresión regular. Desafortunadamente, no creo que haya un equivalente en .Net)
En mi ejemplo, quiero encontrar permutaciones de la cadena "123456789" que coincidan con la expresión regular "32145.67". Utilizo la expresión regular (subóptima) "^ 3 $ | ^ 32 $ | ^ 321" para descartar permutaciones que no comienzan con 321. (Por supuesto, aquí habría sido posible generar las permutaciones para "456789" y prepend "123" a los resultados, pero esto es solo para ilustrar el concepto.)
La eficiencia de esta solución dependerá principalmente de cuántas coincidencias no válidas puede descartar al principio de la generación de permutaciones.
Breve explicación de cómo funciona la generación de permutación . Intentemos generar todas las permutaciones de la cadena "abc". Se puede ver fácilmente que:
permutations("abc") = {"a" + permutations("bc"),
"b" + permutations("ac"),
"c" + permutations("ab")}
En otras palabras, tomamos cada carácter de la cadena de entrada, lo agregamos a un acumulador y calculamos todas las permutaciones de la cadena de entrada con el carácter eliminado. Una vez que alcanzamos una hoja, una permutación de la cadena de entrada, el acumulador tendrá el tamaño de la cadena de entrada.
Esto se puede escribir sucintamente en pseudocódigo recursivo como:
permutation(input, acc)
if input empty
return acc
foreach(character in input)
left <- remove char from input
permutation(left, acc+char)
Ahora bien, esta no es la forma más eficiente de generar permutaciones. (vea el algoritmo de Heap) Pero al menos nos permite no explorar toda la estructura de árbol y descartar las permutaciones solo con mirar su prefijo.
Dado que el "rendimiento de rendimiento" no funciona tan bien en las funciones recursivas, simplemente reescribí la solución de manera iterativa (Nota: la complejidad del espacio es peor que con el DFS recursivo anterior).
public IEnumerable<string> getPermutation(string input, string regexp)
{
Stack<string> left = new Stack<string>();
Stack<string> acc = new Stack<string>();
left.Push(input);
acc.Push("");
// generate all permutations that match regexp
while (left.Count > 0)
{
string c = left.Pop();
string r = acc.Pop();
if(r.Length==input.Length)
{
yield return r;
}
else
{
for(int i=0;i<c.Length;i++)
{
string p = r + c[i];
if (Regex.IsMatch(p,regexp)) // continue if we have a potential match
{
left.Push(c.Substring(0, i) + c.Substring(i + 1));
acc.Push(p);
}
}
}
}
}
foreach(var a in getPermutation("123456789", "^3$|^32$|^321"))
{
if(Regex.IsMatch(a, "32145.67"))
{
// found match
}
}
Estoy obteniendo System.OutOfMemoryException cuando intento generar permutaciones de 6 letras. Las permutaciones de 5 letras todavía funcionan.
Aquí está el código que estoy usando para generar TODAS las permutaciones:
private static List<string> getPermutations(int n,string source)
{
IEnumerable<string> q = source.Select(x => x.ToString());
for (int i = 0; i < n - 1; i++)
{
q = q.SelectMany(x => source, (x, y) => x + y);
}
return q.ToList(); // THIS IS WHERE THE ERROR HAPPENS
}
después de lo cual estoy usando este fragmento de código para filtrarlos según la expresión regular:
private static List<string> filterListByRegex(List<string> list, string regex)
{
List<string> newList = list.ToList();
for (int i = newList.Count - 1; i >= 0; i--)
{
Match match = Regex.Match(""+newList[i], regex, RegexOptions.IgnoreCase);
if (!match.Success)
{
newList.RemoveAt(i);
}
}
return newList;
}
por lo tanto, ya que realmente no necesito TODAS esas permutaciones, ¿hay una manera de regex filtrar mientras se generan permutaciones, o debo usar un código más eficiente para generar permutaciones?
Aquí hay una foto para demostrar mejor lo que estoy tratando de lograr:
La cadena del alfabeto vertical es la que le digo al código que se debe usar.
En primer lugar, me gustaría mencionar que lo que estamos discutiendo aquí no es permutaciones reales, sino las llamadas n-tuples o permutations with repetition : Wikipedia .
En segundo lugar, con respecto a System.OutOfMemoryException when generating permutations , creo que todos estamos de acuerdo en que el resultado no debe almacenarse en una lista, sino que debe proporcionarse como enumerable, lo que permitirá aplicar el filtrado y el consumo (eventualmente almacenar) solo los que estén interesados.
En ese sentido, la solución LINQ proporcionada por @juharr está funcionando muy bien. Así que mis objetivos son minimizar las asignaciones de memoria intermediarias, incluidas las concatenaciones de cadenas y también terminar con una solución más general y más rápida.
Para hacer eso, necesito tomar una decisión de diseño difícil. La firma de la función general de la que estoy hablando se verá así
public static IEnumerable<T[]> RepeatingPermutations<T>(this T[] set, int N)
y la pregunta es cuál debe ser la matriz producida. Si seguimos las recomendaciones, deben ser instancias de una matriz separada. Sin embargo, recuerde que quiero minimizar las asignaciones, he decidido romper esas reglas y generar una sola instancia de matriz, transfiriendo la responsabilidad de no modificarla y clonarla si es necesario para el llamante. Por ejemplo, esto le permite a la persona que llama realizar un filtrado sin costo. O implementar la función OP en la parte superior de esta manera
public static IEnumerable<string> RepeatingPermutations(this string set, int N)
{
return set.ToCharArray().RepeatingPermutations(N).Select(p => new string(p));
}
Unas palabras sobre el algoritmo. En lugar de ver el problema de forma recursiva como otros respondedores, quiero implementar efectivamente el equivalente de algo como esto
from e1 in set
from e2 in set
...
from eN in set
select new [] { e1, e2, .., eN }
Curiosamente, recientemente respondí a una question relacionada con combinaciones y me di cuenta de que los algoritmos son muy parecidos.
Con todo lo que se dice, aquí está la función:
public static IEnumerable<T[]> RepeatingPermutations<T>(this T[] set, int N)
{
var result = new T[N];
var indices = new int[N];
for (int pos = 0, index = 0; ;)
{
for (; pos < N; pos++, index = 0)
{
indices[pos] = index;
result[pos] = set[index];
}
yield return result;
do
{
if (pos == 0) yield break;
index = indices[--pos] + 1;
}
while (index >= set.Length);
}
}
He hecho algunas pruebas simplemente llamando a las diferentes funciones con N = 2,3, .. 6 y simplemente iterando y contando. Aquí están los resultados en mi máquina:
A : N=2 Count= 676 Time=00:00:00.0000467 Memory= 29K
B1: N=2 Count= 676 Time=00:00:00.0000263 Memory= 16K
B2: N=2 Count= 676 Time=00:00:00.0000189 Memory= 8K
A : N=3 Count= 17,576 Time=00:00:00.0010107 Memory= 657K
B1: N=3 Count= 17,576 Time=00:00:00.0003673 Memory= 344K
B2: N=3 Count= 17,576 Time=00:00:00.0001415 Memory= 8K
A : N=4 Count= 456,976 Time=00:00:00.0184445 Memory= 2,472K
B1: N=4 Count= 456,976 Time=00:00:00.0096189 Memory= 2,520K
B2: N=4 Count= 456,976 Time=00:00:00.0033624 Memory= 8K
A : N=5 Count= 11,881,376 Time=00:00:00.4281349 Memory= 397K
B1: N=5 Count= 11,881,376 Time=00:00:00.2482835 Memory= 4,042K
B2: N=5 Count= 11,881,376 Time=00:00:00.0887759 Memory= 8K
A : N=6 Count= 308,915,776 Time=00:00:11.2697326 Memory= 1,688K
B1: N=6 Count= 308,915,776 Time=00:00:06.5638404 Memory= 1,024K
B2: N=6 Count= 308,915,776 Time=00:00:02.2674431 Memory= 8K
dónde
A - Función LINQ de @juharr
B1 - mi función con cuerda
B2 - mi función con char []
Como podemos ver, en cuanto a la memoria ambas funciones de cadena son comparables. En cuanto al rendimiento, la función LINQ es solo ~ 2 veces más lenta, lo que es un buen resultado.
Como se esperaba en tal escenario, la función de no asignación supera significativamente a los dos.
ACTUALIZACIÓN: Tal como se solicita en los comentarios, aquí está el uso de muestra de las funciones anteriores (tenga en cuenta que son métodos de extensión y deben colocarse en una clase estática de su elección):
var charSet = Enumerable.Range(''A'', ''Z'' - ''A'' + 1).Select(c => (char)c).ToArray();
var charPermutations = charSet.RepeatingPermutations(3);
var stringSet = new string(charset);
var stringPermutations = stringSet.RepeatingPermutations(3);
Sin embargo, recuerde la elección de diseño que hice, así que si expande las charPermutations dentro del depurador, verá uno y los mismos valores (la última permutación). Consumir todo el resultado de la llamada anterior para char[] debería ser así
var charPermutationList = charSet.RepeatingPermutations(3)
.Select(p => (char[])p.Clone()).ToList();
En realidad, una buena adición a los dos métodos presentados sería el siguiente método de extensión:
public static IEnumerable<T[]> Clone<T>(this IEnumerable<T[]> source)
{
return source.Select(item => (T[])item.Clone());
}
por lo que la llamada de consumo sería simple
var charPermutationList = charSet.RepeatingPermutations(3).Clone().ToList();
Lo mejor que puede hacer aquí es usar la inicialización perezosa para evitar tener todas las permutaciones en la memoria al mismo tiempo.
private static IEnumerable<string> getPermutations(int n,string source)
{
IEnumerable<string> q = source.Select(x => x.ToString());
for (int i = 0; i < n - 1; i++)
{
q = q.SelectMany(x => source, (x, y) => x + y);
}
return q;
}
private static List<string> filterListByRegex(IEnumerable<string> list, string regex)
{
List<string> newList = new List();
foreach(var item in list)
{
Match match = Regex.Match(item, regex, RegexOptions.IgnoreCase);
if (match.Success)
{
newList.Add(item);
}
}
return newList;
}
Puede que esta no sea la forma más eficiente de hacerlo, pero al menos debería hacer que superen los problemas de memoria.
Se está quedando sin memoria al almacenar todas esas permutaciones en un punto.
Suponiendo una longitud de 5 caracteres, hay 7,893,600 permutaciones diferentes.
Suponiendo una longitud de 6 caracteres, hay 165,765,600 permutaciones diferentes.
Teniendo en cuenta que cada carácter de una cadena vale 2 bytes de memoria, necesitaría 1,989,187,200 bytes (solo alrededor de 2 Gigabytes) para almacenar todas las permutaciones. Eso no es exactamente deseable.
Entonces, ¿cómo arreglamos esto?
Nunca he codificado en c #, pero aquí hay una decisión de diseño práctica: realizar un procesamiento individual cuando se crea la permutación. De esa manera, solo necesitas almacenar las permutaciones que necesitas. Aquí hay algunos pseudocódigo:
List<string> storedPermutations;
string s = createPermutation();
bool shouldAdd = shouldAddPermutation(s);
if (bool)
{
storedPermutations.add(s);
}
Podría decirse que no es el mejor (ni es probable que sea un pseudo-código), pero la lógica aquí es decidir si agregar la permutación a la lista en el momento en que se crea, en lugar de agregar todo a una lista, y luego tratar de procesarla. lista completa Si todavía te quedas sin memoria, entonces todavía hay muchas permutaciones.