Jérôme De Cuyper

Hace unos días Kirill Osenkov, ingeniero que trabaja en el equipo del IDE Microsoft Visual Studio C#, posteó una pregunta de entrevista que se le hizo interesante:

En un string dado de .NET (en Unicode), considera que existen saltos de línea estándares en la forma \r\n (el equivalente de Environment.NewLine).
Escribe un método que inserte espacio entre dos saltos de líneas consecutivos con el fin de separarlos.

Me llamó mucho la atención, en primer lugar, porque en agosto del 2009 había participado en el proceso de entrevistas para trabajar como intern en Redmond. No recibí ninguna oferta pero este año, lo intentaré otra vez . Y en segundo lugar, porque desde mis entrevistas quedé muy aficionado a este tipo de preguntas técnicas sobre estructuras de datos o recursión entre otros. Dado que había encontrado el post poco tiempo después de su publicación, tuve tiempo de escribir una de las primeras respuestas. Tiene muchos defectos pero también contiene unos elementos interesantes:

string text = "hello \r\n\r\n\r\n world!";
string textResult = "";
char[] caFromText = text.ToCharArray();
for (int i = 0; i < caFromText.Length; ++i)
{
textResult += caFromText[i];
if ((int)caFromText[i] == CARRIAGE_RETURN)
{
// check if not reaching the end of the array
if (i + 3 < caFromText.Length)
{
if ((int)caFromText[i + 1] == NEW_LINE
&amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;&amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp; (int)caFromText[i + 2] == CARRIAGE_RETURN
&amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;&amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp; (int)caFromText[i + 3] == NEW_LINE)
{
// two consecutive breaks where detected
textResult += "\n ";
// jump to the next break
++i;
}
}
}
}

Mi idea fue transformar la cadena en un arreglo de caracteres. Luego, iterar sobre cada caracter buscando una secuencia consecutiva de saltos de líneas. Para evitar salirse del arreglo, utilicé un centinela que valida si ya estamos llegando al final del arreglo. Cuando se cumple la condición, se concatena un espacio a la cadena ‘textResult’ que nos sirve para almacenar el resultado final.

Rik Hemsley recompiló todas las repuestas que se propusieron en una bonita solución de Visual Studio. Además, agregó una serie de test para comprobar la validez de todas las implementaciones:

Me dio gusto ver que mi algoritmo sí pasó todas las pruebas mínimas requeridas para agregar un espacio entre dos saltos de líneas consecutivos. Sin embargo, la velocidad de resolución no era nada buena dado que hace uso de una cadena para concatenar el resultado. Sabía que no era la forma correcta de hacerlo, de hecho lo mencioné en mi comentario, pero no me imaginaba lo malo que podría resultar ser la concatenación. Usando el benchmark de Rik Hemsley pude detectar que mi algoritmo lograba parsear un archivo de 2,106,233 caracteres en aproximadamente 107 minutos o 1 hora y 47 minutos!

Para remediar al problema, cambié la cadena por la clase StringBuilder. Las cadenas en .NET framework son inmutables: cuando concatenamos una cadena, cada vez se crea un nuevo objecto de tipo String en memoria con el valor antiguo más el valor a concatenar. El método Append de la clase StringBuilder permite evitar la creación de una cadena a cada concatenación. A continuación, viene mi versión revisada:

using NUnit.Framework;

namespace KirilQuestion.Implementations
{
[TestFixture]
public class JdecuyperRevisited : InsertSpacesFixture
{
private const char CARRIAGE_RETURN = '\r';
private const char NEW_LINE = '\n';

public override string InsertSpaceBetweenCrLfs(string input)
{
var textResult = "";

var caFromText = input.ToCharArray();

for (var i = 0; i < caFromText.Length; ++i)
{
textResult += caFromText[i];

if (caFromText[i] == CARRIAGE_RETURN)
{
// check if not reaching the end of the array

if (i + 3 < caFromText.Length)
{
if (caFromText[i + 1] == NEW_LINE
&amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;&amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp; caFromText[i + 2] == CARRIAGE_RETURN
&amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;&amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp; caFromText[i + 3] == NEW_LINE)
{
// two consecutive breaks where detected
textResult += "\n ";

// jump to the next break
++i;
}
}
}
}
return input.Replace("\r\n\r\n", "\r\n \r\n");
}
}
}

Esta última versión de mi código procesó el mismo archivo en 58.5738 milisegundos, más de 10.000 veces más rápido que mi primera versión. Usar la concatenación genera un costo altísimo que más nos vale evitar. Sin embargo, no olviden que no en todas las situaciones se recomienda ocupar un StringBuilder. No usen un StringBuilder cuando las concatenaciones son mínimas ya que seguramente harán un pequeño pedazo de código mucho más complejo de leer además de crear un objeto adicional en memoria. Aunque para pequeñas concatenaciones StringBuilder es más eficiente, nunca lo es de forma significativa.

Si descargan el benchmark, podrán ver que la solución más rápida es la de Jordan Terrell y hace uso de una expresión regular muy potente:

string output = Regex.Replace(input, @"(\r\n)(?=\r\n)", "$1 ");

La expresión regular permite parsear el archivo en menos de 18 milisegundos! Aún 3 veces más rápido que mi última solución. Para entender la expresión regular, vamos a trabajar con un ejemplo un poco más sencillo donde remplacé ‘\r\n’ por ‘_’. Nuestro texto de entrada será:

string input = "hello world __";

Aplicamos primero una expresión regular sencilla:

string outWithoutGroups = Regex.Replace(input, @"__", "_ _");

El resultado se ve bastante bien ya que aparece un espacio entre los dos _:

hello world _ _

Sin embargo, si cambiamos un poco el texto de entrada las cosas se complican:

string input = "hello world______";

La salida es ahora la siguiente:

hello world _ __ __ _

¿Que estará pasando? Después de las palabras “hello world” aparecen 6 carateres que vamos a nombrar 1, 2, 3, 4, 5 y 6 (son los 6 underscores). Cada vez que la expresión realiza un match, i.e. encuentra dos caracteres _ consecutivos, los reemplaza por _ _. El primer match procesa los caracteres 1 y 2. Luego se sigue con el 3 y el 4 y finalmente con el 5 y el 6. El problema es que con esta expresión, no se procesaron los caracteres 3 y 5. Y es por eso que no aparecen espacios entre el 2 y el 3 y entre el 4 y el 5.

Kirill Osenkov realizó una imagen que explica claramente lo que no está procesando nuestra expresión regular:

Para remediar ese problema, Jordan Terrell utilizó un constructor llamado lookahead assertion que fue introducido en su tiempo por Perl 5. La aserción se representa mediante ‘?=’ y permite hacer un match de un _ seguido de otro, sin embargo el segundo _ no es parte del match y será evaluado nuevamente por su cuenta. Lo cual permite generar la salida correcta:

hello world _ _ _ _ _ _

¿Alguien ha sido confrontado con preguntas de este tipo?