ReverseString, una domanda dell'intervista C#

Question

Avevo una domanda di intervista che mi chiedeva il mio "feedback" su un pezzo di codice scritto da un programmatore junior. Hanno lasciato intendere che potrebbe esserci un problema e hanno detto che sarà usato pesantemente su stringhe di grandi dimensioni.

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

Non riuscivo a riconoscerlo. Non ho visto nessun problema. Con il senno di poi avrei potuto dire che l'utente dovrebbe ridimensionare ma sembra che C# non abbia un ridimensionamento (io sono un ragazzo C++).

Ho finito per scrivere cose come utilizzare un iteratore se possibile, [x] nei contenitori non potrebbe essere accesso casuale, quindi potrebbe essere lento. e cose varie Ma ho sicuramente detto che non ho mai dovuto ottimizzare il codice C#, quindi il mio pensiero potrebbe non aver fallito nell'intervista.

Volevo sapere, qual è il problema con questo codice, lo vedete voi ragazzi?

operativa -Editazione-

ho cambiato questo in un wiki perché ci possono essere diverse risposte giuste. Anche io sono così felice di aver detto esplicitamente di non aver mai dovuto ottimizzare un programma C# e menzionato le altre cose. Ops. Ho sempre pensato che C# non avesse problemi di prestazioni con questo tipo di cose. oops.

Answer 1

Alcuni commenti sulle risposte date finora:

• ognuno di loro (!) Finora non riuscirà a coppie di surrogati e personaggi, che conciliano. Oh, le gioie di Unicode. Invertire una stringa non equivale a invertire una sequenza di caratteri.
• Mi piace Marc's optimisation per input null, vuoti e di carattere singolo. In particolare, non solo ottiene rapidamente la risposta giusta, ma gestisce anche null (nessuna delle altre risposte)
• Originariamente pensavo che ToCharArray seguito da Array.Reverse sarebbe il più veloce, ma crea una "spazzatura" " copia.
• La soluzione StringBuilder crea una singola stringa (non un array di caratteri) e la manipola finché non si chiama ToString. Non è necessaria alcuna copia aggiuntiva ... ma c'è molto più lavoro nel mantenimento delle lunghezze ecc.

Qual è la soluzione più efficiente? Beh, dovrei fare un benchmark per avere qualche idea - ma anche così non dirò tutta la storia. Stai usando questo in una situazione con alta pressione di memoria, dove la spazzatura in più è un vero dolore? Quanto è veloce la tua memoria rispetto alla tua CPU, ecc.?

Come sempre, la leggibilità è di solito re - e non ottiene molto meglio della risposta di Marc su quel fronte. In particolare, c'è non c'è una stanza per un errore off-by-one, mentre io dovrei in realtà riflettere sulla convalida delle altre risposte. Non mi piace pensare. Mi fa male il cervello, quindi cerco di non farlo molto spesso. L'utilizzo dello Array.Reverse integrato mi suona molto meglio. (Ok, non riesce ancora a surrogati, ecc, ma hey ...)

Answer 2

Poiché le stringhe sono immutabili, ciascuna istruzione += creerà una nuova stringa copiando la stringa nell'ultimo passaggio, insieme al singolo carattere per formare una nuova stringa. In effetti, questo sarà un algoritmo O (n.) invece di O (n).

Un modo più veloce sarebbe (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

più importante? Questo farà impazzire le prestazioni - deve creare lotti di stringhe (uno per carattere). Il modo più semplice è qualcosa di simile:

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

Il problema è che le concatenazioni di stringhe sono costosi da fare come le stringhe sono immutabili in C#. L'esempio fornito creerà una nuova stringa di un carattere più lungo ogni iterazione che è molto inefficiente. Per evitare questo è necessario utilizzare la classe StringBuilder invece in questo 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(); 
} 

Lo StringBuilder è stato scritto appositamente per gli scenari di questo tipo in quanto ti dà la possibilità di concatenare le stringhe, senza l'inconveniente di allocazione di memoria eccessiva.

Si noterà che ho fornito a StringBuilder una capacità iniziale che non si vede spesso. Come si conosce la lunghezza del risultato per iniziare, questo rimuove le allocazioni di memoria inutili.

Ciò che normalmente accade è che assegna una quantità di memoria allo StringBuilder (16 caratteri predefiniti). Una volta che il contenuto tenta di superare quella capacità, raddoppia (credo) la propria capacità e prosegue. Questo è molto meglio dell'assegnazione della memoria ogni volta come accadrebbe con le stringhe normali, ma se si può evitare anche questo è ancora meglio.

Answer 5

Il modo migliore per affrontarlo sarebbe utilizzare StringBuilder, poiché non è immutabile non si otterrà il terribile comportamento di generazione di oggetti che si otterrebbe sopra. In .net tutte le stringhe sono immutabili, il che significa che l'operatore + = creerà un nuovo oggetto ogni volta che viene colpito.StringBuilder utilizza un buffer interno, quindi l'inversione può essere eseguita nel buffer senza allocazioni di oggetti aggiuntivi.

Answer 6

È necessario utilizzare la classe StringBuilder per creare la stringa risultante. Una stringa è immutabile, quindi quando si aggiunge una stringa in ogni interazione del ciclo, è necessario creare una nuova stringa, che non è molto efficiente.

Answer 7

È possibile farlo in .NET 3.5, invece:

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

Answer 8

preferisco qualcosa di simile:

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 è la stringa da invertire.

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

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

Answer 10

Questo metodo riduce il numero di iterazioni a metà. Anziché partire dalla fine, inizia dall'inizio e scambia i caratteri finché non raggiunge il centro. Dovevo convertire la stringa in un array di caratteri perché l'indicizzatore di una stringa non ha 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.
come un servizio pubblico, questo è il modo in realtà CORRETTAMENTE invertire una stringa
(invertendo una stringa è NON pari ad invertire una sequenza di caratteri)

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); 
    } 
} 

See: https://vimeo.com/7403673

A proposito, in Golang, il modo corretto è questo:

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 
} 

E il modo non corretto è questo (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) 
} 

Nota che è necessario conoscere la differenza tra
- un personaggio e un glifo
- un byte (8 bit) e una codepoint/runa (32 bit)
- un codepoint e un GraphemeCluster [32+ bit] (aka Grapheme/Glyph)

Reference:

Il carattere è un termine sovraccarico che può significare molte cose.

Un punto di codice è l'unità atomica di informazioni. Il testo è una sequenza di punti codice . Ogni punto di codice è un numero a cui viene assegnato il significato dallo standard Unicode .

Un grafema è una sequenza di uno o più punti di codice che vengono visualizzati come una singola unità grafica che un lettore riconosce come un singolo elemento del sistema di scrittura. Ad esempio, sia a che ä sono graphemes , ma possono essere costituiti da più punti di codice (ad esempio può essere due punti di codice, uno per il carattere di base a seguito da uno per la diaresi , ma c'è anche un'alternativa, eredità , punto codice singolo che rappresenta questo grafema). Alcuni punti di codice non fanno mai parte di alcun grafema (ad esempio il non-joiner a larghezza zero o gli override direzionali).

Un glifo è un'immagine, solitamente memorizzata in un carattere (che è una raccolta di glifi), utilizzata per rappresentare i grafemi o parti di essi. I caratteri possono comporre glifi multipli in una singola rappresentazione, ad esempio, se quanto sopra ä è un singolo punto di codice, un font può scegliere di renderlo come due glifi separati, spazialmente sovrapposti. Per OTF, le tabelle GSPOS e GPOS del font contengono informazioni di sostituzione e posizionamento per rendere questo lavoro . Un font può contenere più glifi alternativi per lo stesso grapheme .

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; 
    }