Come tagliare un java stringbuilder?

Ho un oggetto StringBuilder che deve essere tagliato (cioè tutti gli spazi chars /u0020 e di seguito rimosso da entrambe le estremità).

Non riesco a trovare un metodo di string builder che farebbe questo.

Qui è quello che sto facendo ora:

String trimmedStr = strBuilder.toString().trim();

Questo dà esattamente l’output desiderato, ma richiede due Stringhe allocate invece di uno. C’è un modo più efficiente per tagliare la stringa mentre è ancora in StringBuilder?



7 Replies
  1. 25

    , Non si dovrebbe usare il deleteCharAt approccio.

    Come Boris sottolineato, il deleteCharAt metodo copia dell’array al di sopra di ogni tempo. Il codice Java 5 che fa questo simile a questo:

    public AbstractStringBuilder deleteCharAt(int index) {
        if ((index < 0) || (index >= count))
            throw new StringIndexOutOfBoundsException(index);
        System.arraycopy(value, index+1, value, index, count-index-1);
        count--;
        return this;
    }

    Naturalmente, la speculazione da sola non è sufficiente per scegliere un metodo di ottimizzazione, quindi ho deciso per tempo i 3 approcci in questo thread: l’originale, l’eliminazione di approccio, e la sottostringa approccio.

    Qui è il codice che ho testato per orignal:

    public static String trimOriginal(StringBuilder sb) {
        return sb.toString().trim();
    }

    Elimina approccio:

    public static String trimDelete(StringBuilder sb) {
        while (sb.length() > 0 && Character.isWhitespace(sb.charAt(0))) {
            sb.deleteCharAt(0);
        }
        while (sb.length() > 0 && Character.isWhitespace(sb.charAt(sb.length() - 1))) {
            sb.deleteCharAt(sb.length() - 1);
        }
        return sb.toString();
    }

    E la sottostringa approccio:

    public static String trimSubstring(StringBuilder sb) {
        int first, last;
    
        for (first=0; first<sb.length(); first++)
            if (!Character.isWhitespace(sb.charAt(first)))
                break;
    
        for (last=sb.length(); last>first; last--)
            if (!Character.isWhitespace(sb.charAt(last-1)))
                break;
    
        return sb.substring(first, last);
    }

    Ho eseguito 100 test, ogni volta che la generazione di un milione di caratteri StringBuffer con diecimila finali e gli spazi principali. Il test in sé è molto semplice, ma dà una buona idea di quanto tempo i metodi.

    Qui c’è il codice per tempo i 3 approcci:

    public static void main(String[] args) {
    
        long originalTime = 0;
        long deleteTime = 0;
        long substringTime = 0;
    
        for (int i=0; i<100; i++) {
    
            StringBuilder sb1 = new StringBuilder();
            StringBuilder sb2 = new StringBuilder();
            StringBuilder sb3 = new StringBuilder();
    
            for (int j=0; j<10000; j++) {
                sb1.append(" ");
                sb2.append(" ");
                sb3.append(" ");
            }
            for (int j=0; j<980000; j++) {
                sb1.append("a");
                sb2.append("a");
                sb3.append("a");
            }
            for (int j=0; j<10000; j++) {
                sb1.append(" ");
                sb2.append(" ");
                sb3.append(" ");
            }
    
            long timer1 = System.currentTimeMillis();
            trimOriginal(sb1);
            originalTime += System.currentTimeMillis() - timer1;
    
            long timer2 = System.currentTimeMillis();
            trimDelete(sb2);
            deleteTime += System.currentTimeMillis() - timer2;
    
            long timer3 = System.currentTimeMillis();
            trimSubstring(sb3);
            substringTime += System.currentTimeMillis() - timer3;
        }
    
        System.out.println("original:  " + originalTime + " ms");
        System.out.println("delete:    " + deleteTime + " ms");
        System.out.println("substring: " + substringTime + " ms");
    }

    Ho ottenuto il seguente output:

    original:  176 ms
    delete:    179242 ms
    substring: 154 ms

    Come si vede, la sottostringa approccio fornisce una leggera ottimizzazione sopra l’originale “a doppia Corda” approccio. Tuttavia, l’eliminazione di approccio è estremamente lento e dovrebbe essere evitato.

    Quindi, per rispondere alla tua domanda: si sta bene il taglio dei StringBuilder il modo in cui hai proposto nella domanda. Molto leggera ottimizzazione che il metodo substring offre probabilmente non giustifica l’eccesso di codice.

    • Bella elaborazione del mio commento, non ho avuto il tempo di me. Essere attenti, però, con quei micro-parametri di riferimento in Java. La JVM ottimizza l’esecuzione di codice in tanti modi che la semplice micro-parametri di riferimento può essere ingannevole (ad esempio, vedere Anatomia di un imperfetto microbenchmark o questa domanda per i dettagli). Ci sono strumenti come la pinza che aiutano un po ‘ a fare.
    • Collegate questione, c’è anche una risposta che i link di alcuni articoli]( ibm.com/developerworks/java/library/j-benchmark1.html) e tool ho usato prima (ma non ha trovato per il mio primo commento). Anche una buona lettura.
    • Ehi Boris, grazie mille per le info. Sto leggendo l’articolo di oggi, e la trovo davvero utile finora.
    • C’è un leggero vantaggio di velocità substring, ma penso che il più grande miglioramento è in memoria, dato che la stringa non deve essere copiato due volte come il metodo originale. +1
    • Guardatevi le insidie in microbenchmarking. Che cosa succede se si modifica l’ordine delle prove, in modo che la stringa di versione viene testato prima? Scommetto che si ottiene il risultato opposto. (Qui, disponiamo di un ampio unit test per i metodi la nostra applicazione utilizza, e a seconda di quale viene eseguito per primo viene eseguito più lentamente rispetto agli altri. Probabilmente a causa di Hotspot calci in.)
    • Io preferisco l’eliminazione di approccio. Per le piccole stringhe differenza oraria sarà di piccole dimensioni più importante non creare rifiuti.
    • L’utilizzo della delete(int, int) metodo per gli spazi principali. Basta calcolare la posizione di partenza. Quindi, utilizzare il setLength metodo.

  2. 2

    Non devi preoccuparti di due stringhe. Si tratta di un microoptimization.

    Se davvero hanno rilevato la presenza di un collo di bottiglia, si può avere un quasi-costante di tempo-taglio – solo a scorrere i primi N caratteri, fino a quando non sono Character.isWhitespace(c)

    • La ragione per cui sto preoccuparsi di esso è perché sto su Android e io sono il parsing di un file XML, in modo che questa operazione verrà ripetuta per migliaia di etichette. Questo significa che sarò l’allocazione di circa 6000 Corde, invece di 3000, che è davvero un bel miglioramento.
    • Più importante di questa ottimizzazione è di non utilizzare StringBuilder costruttore di default, dare una capacità sufficiente per iniziare. Nell’implementazione corrente di default capacità è di 16 caratteri, e come se non bastasse, il buffer viene sostituita da una più grande. Soprattutto per testi lunghi, questo gli farà guadagnare molto di più di qualsiasi altra cosa (perché il buffer ottenere riallocare più volte per ogni linea di ingresso).
    • un buon punto. Uso già un 500 char capacità di StringBuilder un costruttore che è appropriato per la mia applicazione
  3. 2

    Ho usato Zaven dell’approccio di analisi e StringBuilder è eliminare(inizio, fine) metodo che esegue molto meglio di deleteCharAt(indice) approccio, ma leggermente peggio del substring() approccio. Questo metodo utilizza anche la copia dell’array, ma copia dell’array è chiamato molte meno volte (solo due volte nel peggiore dei casi). Inoltre, questo evita di creare più istanze intermedi Stringhe nel caso trim() viene chiamato più volte sullo stesso oggetto StringBuilder.

    public class Main {
    
        public static String trimOriginal(StringBuilder sb) {
            return sb.toString().trim();
        }
    
        public static String trimDeleteRange(StringBuilder sb) {
            int first, last;
    
            for (first = 0; first < sb.length(); first++)
                if (!Character.isWhitespace(sb.charAt(first)))
                    break;
    
            for (last = sb.length(); last > first; last--)
                if (!Character.isWhitespace(sb.charAt(last - 1)))
                    break;
    
            if (first == last) {
                sb.delete(0, sb.length());
            } else {
               if (last < sb.length()) {
                  sb.delete(last, sb.length());
               }
               if (first > 0) {
                  sb.delete(0, first);
               }
            }
            return sb.toString();
        }
    
    
        public static String trimSubstring(StringBuilder sb) {
            int first, last;
    
            for (first = 0; first < sb.length(); first++)
                if (!Character.isWhitespace(sb.charAt(first)))
                    break;
    
            for (last = sb.length(); last > first; last--)
                if (!Character.isWhitespace(sb.charAt(last - 1)))
                    break;
    
            return sb.substring(first, last);
        }
    
        public static void main(String[] args) {
            runAnalysis(1000);
            runAnalysis(10000);
            runAnalysis(100000);
            runAnalysis(200000);
            runAnalysis(500000);
            runAnalysis(1000000);
        }
    
        private static void runAnalysis(int stringLength) {
            System.out.println("Main:runAnalysis(string-length=" + stringLength + ")");
    
            long originalTime = 0;
            long deleteTime = 0;
            long substringTime = 0;
    
            for (int i = 0; i < 200; i++) {
    
                StringBuilder temp = new StringBuilder();
                char[] options = {' ', ' ', ' ', ' ', 'a', 'b', 'c', 'd'};
                for (int j = 0; j < stringLength; j++) {
                    temp.append(options[(int) ((Math.random() * 1000)) % options.length]);
                }
                String testStr = temp.toString();
    
                StringBuilder sb1 = new StringBuilder(testStr);
                StringBuilder sb2 = new StringBuilder(testStr);
                StringBuilder sb3 = new StringBuilder(testStr);
    
                long timer1 = System.currentTimeMillis();
                trimOriginal(sb1);
                originalTime += System.currentTimeMillis() - timer1;
    
                long timer2 = System.currentTimeMillis();
                trimDeleteRange(sb2);
                deleteTime += System.currentTimeMillis() - timer2;
    
                long timer3 = System.currentTimeMillis();
                trimSubstring(sb3);
                substringTime += System.currentTimeMillis() - timer3;
            }
    
            System.out.println("  original:     " + originalTime + " ms");
            System.out.println("  delete-range: " + deleteTime + " ms");
            System.out.println("  substring:    " + substringTime + " ms");
        }
    
    }

    Di uscita:

    Main:runAnalysis(string-length=1000)
      original:     0 ms
      delete-range: 4 ms
      substring:    0 ms
    Main:runAnalysis(string-length=10000)
      original:     4 ms
      delete-range: 9 ms
      substring:    4 ms
    Main:runAnalysis(string-length=100000)
      original:     22 ms
      delete-range: 33 ms
      substring:    43 ms
    Main:runAnalysis(string-length=200000)
      original:     57 ms
      delete-range: 93 ms
      substring:    110 ms
    Main:runAnalysis(string-length=500000)
      original:     266 ms
      delete-range: 220 ms
      substring:    191 ms
    Main:runAnalysis(string-length=1000000)
      original:     479 ms
      delete-range: 467 ms
      substring:    426 ms
    • Sarebbe interessante vedere questo benchmark su iterazioni, piuttosto che la lunghezza della stringa. Mi chiedo quanta differenza ci sarebbe.
    • Dovrebbe essere facile da modificare il codice per aggiungere il supporto per iterazioni troppo. Penso che i risultati rimangono gli stessi con substring risultati migliori, ma il guadagno in base al metodo di eliminazione sarebbe venuto da un risparmio di oltre un minor numero di oggetti per gc, che non è stato misurato nel punto di riferimento attuale codice.
    • perché hai detto questo – “StringBuilder delete(inizio, fine) metodo che esegue molto meglio di deleteCharAt(indice) approccio” ?
  4. 1

    solo uno di voi ha preso in considerazione che quando si converte la Stringa builder per una “stringa” e poi “trim” che si crea un oggetto immutabile due volte che ha alla procedura di garbage collection,
    così la dotazione complessiva è:

    1. Oggetto Stringbuilder
    2. immutabile stringa di SB oggetto
      1 immutabile oggetto della stringa che è stato tagliato.

    Così, mentre si può “apparire” che il trim è più veloce, nel mondo reale e con una memoria inserita schema infatti sarà peggio.

  5. 1

    Ho avuto esattamente la tua domanda in un primo momento, tuttavia, dopo 5 minuti del secondo pensiero, ho capito che in realtà non avete bisogno di tagliare il StringBuffer! Si solo bisogno di tagliare la corda si accoda in StringBuffer.

    Se si vuole tagliare un iniziale StringBuffer, si può fare questo:

    StringBuffer sb = new StringBuffer(initialStr.trim());

    Se si vuole tagliare StringBuffer on-the-fly, è possibile farlo durante append:

    Sb.append(addOnStr.trim());
  6. 0

    Si ottengono due stringhe, ma mi aspetto i dati per essere assegnato soltanto una volta. Dato che le Stringhe in Java sono immutabili, mi sarei aspettato che il trim attuazione per darvi un oggetto che condivide gli stessi dati di carattere, ma con diversa di inizio e fine degli indici. Almeno questo è quello che substr metodo. Così, tutto ciò che si tenta di ottimizzare questo sicuramente avrà l’effetto opposto, poiché si aggiunge overhead che non è necessario.

    Solo il passaggio attraverso il trim() il metodo con il debugger.

    • Restituisce un nuovo oggetto string che consente di copiare i caratteri via arraycopy: dal codice sorgente: return new String(inizio, fine – inizio + 1, valore);
    • Dove vedi arraycopy? Questa è la Stringa costruttore utilizzato da tagliare in JDK 1.6.0, il buffer viene riutilizzato senza copiare: String(int offset, int count, valore char[]) { questo.valore = valore; questo.offset=; questo.count = count; }
  7. 0

    Ho fatto un po ‘ di codice. Funziona e i casi di test sono lì per voi a vedere. Fatemi sapere se questo va bene.

    Principale codice

    public static StringBuilder trimStringBuilderSpaces(StringBuilder sb) {
    
        int len = sb.length();
    
        if (len > 0) {
    
                int start = 0;
                int end = 1;
                char space = ' ';
                int i = 0;
    
                //Remove spaces at start
                for (i = 0; i < len; i++) {
                    if (sb.charAt(i) != space) {
                        break;
                    }
                }
    
                end = i;
                //System.out.println("s = " + start + ", e = " + end);
                sb.delete(start, end);
    
                //Remove the ending spaces
                len = sb.length();
    
                if (len > 1) {
    
                    for (i = len - 1; i > 0; i--) {
                        if (sb.charAt(i) != space) {
                            i = i + 1;
                            break;
                        }
                    }
    
                    start = i;
                    end = len;//or len + any positive number !
    
                    //System.out.println("s = " + start + ", e = " + end);
                    sb.delete(start, end);
    
                }
    
        }
    
        return sb;
    }

    Il codice completo con test

    package source;
    
    import java.io.PrintWriter;
    import java.io.StringWriter;
    import java.util.ArrayList;
    
    public class StringBuilderTrim {
    
        public static void main(String[] args) {
            testCode();
        }
    
        public static void testCode() {
    
            StringBuilder s1 = new StringBuilder("");
            StringBuilder s2 = new StringBuilder(" ");
            StringBuilder s3 = new StringBuilder("  ");
            StringBuilder s4 = new StringBuilder(" 123");
            StringBuilder s5 = new StringBuilder("  123");
            StringBuilder s6 = new StringBuilder("1");
            StringBuilder s7 = new StringBuilder("123 ");
            StringBuilder s8 = new StringBuilder("123  ");
            StringBuilder s9 = new StringBuilder(" 123 ");
            StringBuilder s10 = new StringBuilder("  123  ");
    
            /*
             * Using a rough form of TDD here. Initially, one one test input
             * "test case" was added and rest were commented. Write no code for the
             * method being tested. So, the test will fail. Write just enough code
             * to make it pass. Then, enable the next test. Repeat !!!
             */
            ArrayList<StringBuilder> ins = new ArrayList<StringBuilder>();
            ins.add(s1);
            ins.add(s2);
            ins.add(s3);
            ins.add(s4);
            ins.add(s5);
            ins.add(s6);
            ins.add(s7);
            ins.add(s8);
            ins.add(s9);
            ins.add(s10);
    
            //Run test
            for (StringBuilder sb : ins) {
                System.out
                        .println("\n\n---------------------------------------------");
                String expected = sb.toString().trim();
                String result = trimStringBuilderSpaces(sb).toString();
                System.out.println("In [" + sb + "]" + ", Expected [" + expected
                        + "]" + ", Out [" + result + "]");
                if (result.equals(expected)) {
                    System.out.println("Success!");
                } else {
                    System.out.println("FAILED!");
                }
                System.out.println("---------------------------------------------");
            }
    
        }
    
        public static StringBuilder trimStringBuilderSpaces(StringBuilder inputSb) {
    
            StringBuilder sb = new StringBuilder(inputSb);
            int len = sb.length();
    
            if (len > 0) {
    
                try {
    
                    int start = 0;
                    int end = 1;
                    char space = ' ';
                    int i = 0;
    
                    //Remove spaces at start
                    for (i = 0; i < len; i++) {
                        if (sb.charAt(i) != space) {
                            break;
                        }
                    }
    
                    end = i;
                    //System.out.println("s = " + start + ", e = " + end);
                    sb.delete(start, end);
    
                    //Remove the ending spaces
                    len = sb.length();
    
                    if (len > 1) {
    
                        for (i = len - 1; i > 0; i--) {
                            if (sb.charAt(i) != space) {
                                i = i + 1;
                                break;
                            }
                        }
    
                        start = i;
                        end = len;//or len + any positive number !
    
                        //System.out.println("s = " + start + ", e = " + end);
                        sb.delete(start, end);
    
                    }
    
                } catch (Exception ex) {
    
                    StringWriter sw = new StringWriter();
                    PrintWriter pw = new PrintWriter(sw);
                    ex.printStackTrace(pw);
                    sw.toString(); //stack trace as a string
    
                    sb = new StringBuilder("\nNo Out due to error:\n" + "\n" + sw);
                    return sb;
                }
    
            }
    
            return sb;
        }
    }

Lascia un commento