ReverseString, una C-interview-question

Question

Tuve una pregunta de la entrevista que me preguntó por mi "retroalimentación" en una pieza de código que un programador junior escribió. Insinuaron que podría haber un problema y dijeron que se usará mucho en cadenas grandes.

public string ReverseString(string sz) 
{ 
    string result = string.Empty; 
    for(int i = sz.Length-1; i>=0; i--) 
    { 
     result += sz[i] 
    } 
    return result; 
} 

No lo pude localizar. No vi ningún problema en absoluto. En retrospectiva, podría haber dicho que el usuario debería cambiar el tamaño, pero parece que C# no tiene un tamaño (soy un chico de C++).

Terminé escribiendo cosas como usar un iterador si es posible, [x] en contenedores no podría ser de acceso aleatorio, por lo que puede ser lento. y cosas diferentes. Pero definitivamente dije que nunca tuve que optimizar el código C# para que mi pensamiento no me fallara en la entrevista.

Quería saber cuál es el problema con este código, ¿lo ven?

operación -Editar-

me cambiaron esto en un wiki porque no puede haber varias respuestas correctas. También estoy muy contento de haber dicho explícitamente que nunca tuve que optimizar un programa de C# y mencioné otras cosas. Oops. Siempre pensé que C# no tenía ningún problema de rendimiento con este tipo de cosas. Uy.

Answer 1

algunos comentarios sobre las respuestas dadas hasta ahora:

• todos y cada uno de ellos (!) Hasta el momento se producirá un error en pares suplentes y caracteres de combinación. Oh las alegrías de Unicode. Invertir una cadena no es lo mismo que invertir una secuencia de caracteres.
• Me gusta Marc's optimisation para entradas nulas, vacías y de un solo carácter. En particular, no solo obtiene la respuesta correcta rápidamente, sino que también maneja nulo (que ninguna de las otras respuestas)
• Originalmente pensé que ToCharArray seguido de Array.Reverse sería el más rápido, pero crea una "basura" " dupdo.
• La solución StringBuilder crea una sola cadena (no matriz de caracteres) y la manipula hasta que llame al ToString. No hay copia adicional involucrada ... pero hay mucho más trabajo manteniendo longitudes, etc.

¿Cuál es la solución más eficiente? Bueno, tendré que compararlo para tener alguna idea, pero aun así eso no contará toda la historia. ¿Estás usando esto en una situación con alta presión de memoria, donde la basura extra es un verdadero dolor? ¿Qué tan rápido es su memoria frente a su CPU, etc.?

Como siempre, la legibilidad es generalmente rey, y no hay nada mejor que la respuesta de Marc en ese frente. En particular, hay sin espacio para un error de uno por uno, mientras que realmente tendría que pensar un poco en validar las otras respuestas. No me gusta pensar Me duele el cerebro, así que trato de no hacerlo muy a menudo. Usar el Array.Reverse incorporado suena mucho mejor para mí. (Bueno, por lo que todavía falla en sustitutos etc, pero bueno ...)

Answer 2

Dado que las cadenas son inmutables, cada instrucción += creará una nueva cadena copiando la cadena en el último paso, junto con el carácter individual para formar una nueva cadena. Efectivamente, este será un algoritmo O (n) en lugar de O (n).

Una forma más rápida sería (O (n)):

// pseudocode: 
static string ReverseString(string input) { 
    char[] buf = new char[input.Length]; 
    for(int i = 0; i < buf.Length; ++i) 
     buf[i] = input[input.Length - i - 1]; 
    return new string(buf); 
} 

Answer 3

que es más importante? Eso succionará el rendimiento: tiene que crear lotes de cadenas (una por carácter). La forma más sencilla es algo así como:

public static string Reverse(string sz) // ideal for an extension method 
{ 
    if (string.IsNullOrEmpty(sz) || sz.Length == 1) return sz; 
    char[] chars = sz.ToCharArray(); 
    Array.Reverse(chars); 
    return new string(chars); 
} 

Answer 4

El problema es que las concatenaciones de cadenas son caros de hacer lo que las cadenas son inmutables en C#. El ejemplo dado creará una nueva cadena con un carácter más largo en cada iteración, que es muy ineficiente. Para evitar esto, usted debe utilizar la clase StringBuilder lugar de este modo:

public string ReverseString(string sz) 
{ 
    var builder = new StringBuilder(sz.Length); 
    for(int i = sz.Length-1; i>=0; i--) 
    { 
     builder.Append(sz[i]); 
    } 
    return builder.ToString(); 
} 

El StringBuilder está escrito específicamente para situaciones como esta, ya que le da la capacidad para concatenar cadenas sin el inconveniente de asignación de memoria excesiva.

Notarás que he proporcionado el StringBuilder con una capacidad inicial que no siempre ves. Como sabe la longitud del resultado para empezar, esto elimina las asignaciones de memoria innecesarias.

Lo que normalmente sucede es que asigna una cantidad de memoria a StringBuilder (por defecto 16 caracteres). Una vez que el contenido intenta exceder esa capacidad, dobla (creo) su propia capacidad y continúa. Esto es mucho mejor que asignar memoria cada vez que sucedería con las cadenas normales, pero si puedes evitar esto también será mejor.

Answer 5

Una mejor forma de abordarlo sería utilizar un StringBuilder, ya que no es inmutable, no obtendrá el comportamiento de generación de objeto terrible que obtendría anteriormente. En .net todas las cadenas son inmutables, lo que significa que el operador + = creará un nuevo objeto cada vez que se golpee.StringBuilder utiliza un búfer interno, por lo que la inversión podría realizarse en el búfer sin asignaciones de objetos adicionales.

Answer 6

Debe usar la clase StringBuilder para crear la cadena resultante. Una cadena es inmutable, así que cuando anexas una cadena en cada interacción del ciclo, se debe crear una nueva cadena, que no es muy eficiente.

Answer 7

Usted puede hacer esto en .NET 3.5 en su lugar:

public static string Reverse(this string s) 
    { 
     return new String((s.ToCharArray().Reverse()).ToArray()); 
    } 

Answer 8

prefiero algo como esto:

using System; 
using System.Text; 
namespace SpringTest3 
{ 
    static class Extentions 
    { 
     static private StringBuilder ReverseStringImpl(string s, int pos, StringBuilder sb) 
     { 
      return (s.Length <= --pos || pos < 0) ? sb : ReverseStringImpl(s, pos, sb.Append(s[pos])); 
     } 

     static public string Reverse(this string s) 
     { 
      return ReverseStringImpl(s, s.Length, new StringBuilder()).ToString(); 
     } 
    } 

    class Program 
    { 
     static void Main(string[] args) 
     { 
      Console.WriteLine("abc".Reverse()); 
     } 
    } 
} 

Answer 9

x es la cadena para invertir.

 Stack<char> stack = new Stack<char>(x); 

     string s = new string(stack.ToArray()); 

Answer 10

Este método reduce el número de iteraciones a la mitad. En lugar de comenzar desde el final, comienza desde el principio y cambia los personajes hasta que llega al centro. Tuve que convertir la cadena en una matriz char porque el indexador en una cadena no tiene setter.

public string Reverse(String value) 
    { 
     if (String.IsNullOrEmpty(value)) throw new ArgumentNullException("value"); 

     char[] array = value.ToCharArray(); 

     for (int i = 0; i < value.Length/2; i++) 
     { 
      char temp = array[i]; 
      array[i] = array[(array.Length - 1) - i]; 
      array[(array.Length - 1) - i] = temp; 
     } 

     return new string(array); 
    } 

Answer 11

Necromancing.
Como servicio público, esta es la forma en que realmente CORRECTAMENTE invertir una cadena
(invirtiendo una cadena es NO igual a revertir una secuencia de caracteres)

public static class Test 
{ 

    private static System.Collections.Generic.List<string> GraphemeClusters(string s) 
    { 
     System.Collections.Generic.List<string> ls = new System.Collections.Generic.List<string>(); 

     System.Globalization.TextElementEnumerator enumerator = System.Globalization.StringInfo.GetTextElementEnumerator(s); 
     while (enumerator.MoveNext()) 
     { 
      ls.Add((string)enumerator.Current); 
     } 

     return ls; 
    } 


    // this 
    private static string ReverseGraphemeClusters(string s) 
    { 
     if(string.IsNullOrEmpty(s) || s.Length == 1) 
      return s; 

     System.Collections.Generic.List<string> ls = GraphemeClusters(s); 
     ls.Reverse(); 

     return string.Join("", ls.ToArray()); 
    } 

    public static void TestMe() 
    { 
     string s = "Les Mise\u0301rables"; 
     // s = "noël"; 
     string r = ReverseGraphemeClusters(s); 

     // This would be wrong: 
     // char[] a = s.ToCharArray(); 
     // System.Array.Reverse(a); 
     // string r = new string(a); 

     System.Console.WriteLine(r); 
    } 
} 

Ver: https://vimeo.com/7403673

Por cierto, en Golang, la forma correcta es la siguiente:

package main 

import (
    "unicode" 
    "regexp" 
) 

func main() { 
    str := "\u0308" + "a\u0308" + "o\u0308" + "u\u0308" 
    println("u\u0308" + "o\u0308" + "a\u0308" + "\u0308" == ReverseGrapheme(str)) 
    println("u\u0308" + "o\u0308" + "a\u0308" + "\u0308" == ReverseGrapheme2(str)) 
} 

func ReverseGrapheme(str string) string { 

    buf := []rune("") 
    checked := false 
    index := 0 
    ret := "" 

    for _, c := range str { 

     if !unicode.Is(unicode.M, c) { 

      if len(buf) > 0 { 
       ret = string(buf) + ret 
      } 

      buf = buf[:0] 
      buf = append(buf, c) 

      if checked == false { 
       checked = true 
      } 

     } else if checked == false { 
      ret = string(append([]rune(""), c)) + ret 
     } else { 
      buf = append(buf, c) 
     } 

     index += 1 
    } 

    return string(buf) + ret 
} 

func ReverseGrapheme2(str string) string { 
    re := regexp.MustCompile("\\PM\\pM*|.") 
    slice := re.FindAllString(str, -1) 
    length := len(slice) 
    ret := "" 

    for i := 0; i < length; i += 1 { 
     ret += slice[length-1-i] 
    } 

    return ret 
} 

Y la manera incorrecta es la siguiente (ToCharArray.Reverse):

func Reverse(s string) string { 
    runes := []rune(s) 
    for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 { 
     runes[i], runes[j] = runes[j], runes[i] 
    } 
    return string(runes) 
} 

Tenga en cuenta que lo que necesita saber la diferencia entre
- un personaje y un glifo
- un byte (8 bits) y una punto de código/runa (32 bit)
- un punto de código y una GraphemeCluster [32+ bit] (también conocido como grafema/Glyph)

Reference:

El carácter es un término sobrecargado que puede significar muchas cosas.

Un punto de código es la unidad de información atómica. El texto es una secuencia de puntos de código. Cada punto de código es un número al que se le da significado por el estándar Unicode .

Un grafema es una secuencia de uno o más puntos de código que se muestran como una sola unidad gráfica que un lector reconoce como un único elemento del sistema de escritura. Por ejemplo, tanto a como ä son grafemas , pero pueden consistir en múltiples puntos de código (por ejemplo, ä pueden ser dos puntos de código, uno para el carácter base a seguido de uno para el dialogo , pero también existe una alternativa, legado , punto de código único que representa este grafema). Algunos puntos de código nunca forman parte de ningún grafema (por ejemplo, el no-empalmador de ancho cero o las anulaciones direccionales).

Un glifo es una imagen, generalmente almacenada en una fuente (que es una colección de glifos), que se usa para representar grafemas o partes de los mismos. Las fuentes pueden componer múltiples glifos en una sola representación, por ejemplo, si lo anterior ä es un único punto de código, una fuente puede elegir representarlo como dos glifos separados, espacialmente superpuestos. Para OTF, las tablas GPOS de la fuente GSUB y contienen información de sustitución y posicionamiento para hacer que funcione. Una fuente también puede contener múltiples glifos alternativos para el mismo grafema .

Answer 12

static string reverseString(string text) 
    { 
     Char[] a = text.ToCharArray(); 
     string b = ""; 
     for (int q = a.Count() - 1; q >= 0; q--) 
     { 
      b = b + a[q].ToString(); 
     } 
     return b; 
    }