C # lub Java: dołączanie ciągów znaków z StringBuilder?

104

Wiem, że możemy dołączyć ciągi znaków za pomocą StringBuilder. Czy istnieje sposób, w jaki możemy dołączyć ciągi znaków z wyprzedzeniem (tj. Dodać ciągi przed ciągiem), używając StringBuilder, abyśmy mogli zachować korzyści wydajnościowe, które StringBuilderoferuje?

spalony
źródło
Nie rozumiem twojego pytania
Maurice Perry
5
Dołącz. Słowo jest poprzedzone. Przypuszczam, że dołączanie napisu z wyprzedzeniem musi być czymś w rodzaju dodawania go na obu końcach jednocześnie?
Joel Mueller

Odpowiedzi:

29

Wstawianie ciągu znaków z wyprzedzeniem zwykle wymaga skopiowania wszystkiego za punktem wstawiania z powrotem do części tablicy zapasowej, więc nie będzie to tak szybkie, jak dołączanie do końca.

Ale możesz to zrobić w ten sposób w Javie (w C # to to samo, ale metoda nazywa się Insert):

aStringBuilder.insert(0, "newText");
Joachim Sauer
źródło
11

Jeśli potrzebujesz wysokiej wydajności z dużą ilością przedrostków, musisz napisać własną wersję StringBuilder(lub użyć cudzej). Ze standardem StringBuilder(choć technicznie można by to zaimplementować inaczej) wstawianie wymaga kopiowania danych po punkcie wstawienia. Wstawienie n fragmentu tekstu może zająć O (n ^ 2) czasu.

Naiwnym podejściem byłoby dodanie przesunięcia do char[]bufora podkładowego, a także długości. Jeśli nie ma wystarczającej ilości miejsca na przedrostek, przenieś dane w górę o więcej, niż jest to bezwzględnie konieczne. To może sprowadzić wydajność z powrotem do O (n log n) (myślę). Bardziej wyrafinowanym podejściem jest zapewnienie cykliczności bufora. W ten sposób wolne miejsce na obu końcach tablicy staje się ciągłe.

Tom Hawtin - haczyk
źródło
5

Możesz wypróbować metodę rozszerzenia:

/// <summary>
/// kind of a dopey little one-off for StringBuffer, but 
/// an example where you can get crazy with extension methods
/// </summary>
public static void Prepend(this StringBuilder sb, string s)
{
    sb.Insert(0, s);
}

StringBuilder sb = new StringBuilder("World!");
sb.Prepend("Hello "); // Hello World!
Mark Maxham
źródło
5

Możesz zbudować ciąg w odwrotnej kolejności, a następnie odwrócić wynik. Ponosisz koszt O (n) zamiast O (n ^ 2) w najgorszym przypadku.

jasny
źródło
2
Działa to tylko wtedy, gdy dodajesz pojedyncze znaki. W przeciwnym razie musiałbyś odwrócić każdy dołączony ciąg, który pochłonąłby większość, jeśli nie wszystkie, oszczędności w zależności od rozmiaru i liczby ciągów.
Sled
4

Nie używałem tego, ale Ropes For Java brzmi intrygująco. Nazwa projektu to gra słów, do poważnej pracy użyj liny zamiast sznurka . Obejmuje spadek wydajności dla operacji poprzedzających i innych. Warto rzucić okiem, jeśli masz zamiar dużo to robić.

Lina jest wydajnym zamiennikiem sznurków. Struktura danych, opisana szczegółowo w „Rope: an Alternative to Strings”, zapewnia asymptotycznie lepszą wydajność niż zarówno String, jak i StringBuffer dla typowych modyfikacji ciągów, takich jak dodawanie, dołączanie, usuwanie i wstawianie. Podobnie jak łańcuchy, liny są niezmienne i dlatego dobrze nadają się do stosowania w programowaniu wielowątkowym.

Sam Barnum
źródło
4

Oto, co możesz zrobić, jeśli chcesz wstawić na początku za pomocą klasy StringBuilder w Javie:

StringBuilder str = new StringBuilder();
str.Insert(0, "text");
s_hewitt
źródło
3

Jeśli dobrze cię rozumiem, metoda insert wygląda na to, że zrobi to, co chcesz. Po prostu wstaw ciąg z przesunięciem 0.

Shawn
źródło
2

Spróbuj użyć Wstaw ()

StringBuilder MyStringBuilder = new StringBuilder("World!");
MyStringBuilder.Insert(0,"Hello "); // Hello World!
boj
źródło
2

Sądząc po innych komentarzach, nie ma standardowego szybkiego sposobu na zrobienie tego. Używanie StringBuildera .Insert(0, "text")jest w przybliżeniu tylko 1-3 razy szybsze niż używanie boleśnie powolnej konkatenacji ciągów (na podstawie> 10000 konkatenacji), więc poniżej znajduje się klasa, która może poprzedzać potencjalnie tysiące razy szybciej!

Podaję jakieś inne podstawowe funkcje, takie jak append(), subString()i length()itd. Obie Dokleja i wstawia się zmieniać od około dwukrotnie szybciej do 3x wolniej niż StringBuilder dopisuje. Podobnie jak StringBuilder, bufor w tej klasie zostanie automatycznie zwiększony, gdy tekst przepełni stary rozmiar buforu.

Kod był dość często testowany, ale nie mogę zagwarantować, że jest wolny od błędów.

class Prepender
{
    private char[] c;
    private int growMultiplier;
    public int bufferSize;      // Make public for bug testing
    public int left;            // Make public for bug testing
    public int right;           // Make public for bug testing
    public Prepender(int initialBuffer = 1000, int growMultiplier = 10)
    {
        c = new char[initialBuffer];
        //for (int n = 0; n < initialBuffer; n++) cc[n] = '.';  // For debugging purposes (used fixed width font for testing)
        left = initialBuffer / 2;
        right = initialBuffer / 2;
        bufferSize = initialBuffer;
        this.growMultiplier = growMultiplier;
    }
    public void clear()
    {
        left = bufferSize / 2;
        right = bufferSize / 2;
    }
    public int length()
    {
        return right - left;
    }

    private void increaseBuffer()
    {
        int nudge = -bufferSize / 2;
        bufferSize *= growMultiplier;
        nudge += bufferSize / 2;
        char[] tmp = new char[bufferSize];
        for (int n = left; n < right; n++) tmp[n + nudge] = c[n];
        left += nudge;
        right += nudge;
        c = new char[bufferSize];
        //for (int n = 0; n < buffer; n++) cc[n]='.';   // For debugging purposes (used fixed width font for testing)
        for (int n = left; n < right; n++) c[n] = tmp[n];
    }

    public void append(string s)
    {
        // If necessary, increase buffer size by growMultiplier
        while (right + s.Length > bufferSize) increaseBuffer();

        // Append user input to buffer
        int len = s.Length;
        for (int n = 0; n < len; n++)
        {
            c[right] = s[n];
            right++;
        }
    }
    public void prepend(string s)
    {
        // If necessary, increase buffer size by growMultiplier
        while (left - s.Length < 0) increaseBuffer();               

        // Prepend user input to buffer
        int len = s.Length - 1;
        for (int n = len; n > -1; n--)
        {
            left--;
            c[left] = s[n];
        }
    }
    public void truncate(int start, int finish)
    {
        if (start < 0) throw new Exception("Truncation error: Start < 0");
        if (left + finish > right) throw new Exception("Truncation error: Finish > string length");
        if (finish < start) throw new Exception("Truncation error: Finish < start");

        //MessageBox.Show(left + " " + right);

        right = left + finish;
        left = left + start;
    }
    public string subString(int start, int finish)
    {
        if (start < 0) throw new Exception("Substring error: Start < 0");
        if (left + finish > right) throw new Exception("Substring error: Finish > string length");
        if (finish < start) throw new Exception("Substring error: Finish < start");
        return toString(start,finish);
    }

    public override string ToString()
    {
        return new string(c, left, right - left);
        //return new string(cc, 0, buffer);     // For debugging purposes (used fixed width font for testing)
    }
    private string toString(int start, int finish)
    {
        return new string(c, left+start, finish-start );
        //return new string(cc, 0, buffer);     // For debugging purposes (used fixed width font for testing)
    }
}
Dan W
źródło
1

Możesz samodzielnie stworzyć rozszerzenie dla StringBuilder za pomocą prostej klasy:

namespace Application.Code.Helpers
{
    public static class StringBuilderExtensions
    {
        #region Methods

        public static void Prepend(this StringBuilder sb, string value)
        {
            sb.Insert(0, value);
        }

        public static void PrependLine(this StringBuilder sb, string value)
        {
            sb.Insert(0, value + Environment.NewLine);
        }

        #endregion
    }
}

Następnie po prostu dodaj:

using Application.Code.Helpers;

Na szczycie dowolnej klasy, w której chcesz użyć StringBuilder, i za każdym razem, gdy używasz funkcji intelli-sense ze zmienną StringBuilder, pojawią się metody Prepend i PrependLine. Pamiętaj tylko, że kiedy używasz dołączania na początku, będziesz musiał dodawać na początku w odwrotnej kolejności niż w przypadku dołączania.

ScubaSteve
źródło
0

To powinno działać:

aStringBuilder = "newText" + aStringBuilder; 
gok-nine
źródło
W .NET działa to doskonale z wartościami typu string, ale nie działa z wartościami typu StringBuilder. Odpowiedź od @ScubaSteve działa dobrze.
Contango