Wanneer een stringbuilder te gebruiken?

[HawVer]

Ik ben bezig met het schrijven van een applicatie die svg objecten gaat inlezen. Daarin kunnen lange strings van coordinaten en letters voorkomen. Een goed voorbeeld van een svg object vind ik deze tijger:

http://www.croczilla.com/...r/text_view?obj=tiger.svg

Alleen nu vraag ik me af wat de slimste manier is om die stukken gegevens te converteren naar objecten. Je hebt natuurlijk regular expressions, lekker flexibel maar geen goede performance. Dus ben ik nu bezig met een zelfgeschreven reader die stukken van combinatie letter cijfers inleest. Mijn vraag is daar iets beters voor? Is het wel/niet slim om een stringbuilder (stringbuffer) te gebruiken? Performance is een key issue voor mij.

[Creepy]

Hebben we het hier over Java? Als je een flinke reeks met tekens krijgt waarin je steeds toe wilt voegen dan is het beter om een StringBuilder of StringBuffer te gebruiken. Strings zijn immutable dus als je steeds dezelfde String wilt uitbreiden dan moet er elke keer een nieuwe String aangemaakt worden.

Java:

String buffer = "iets";
buffer = buffer + "nogwat";

Er zul eerst een String worden aangemaakt waar "iets" in staat en vervolgens een nieuwe String waar "ietsnogwat" in staat.

Om die overhead te voorkomen kan je een StringBuffer of StirngBuilder gebruiken. StringBuffer is threadsave, StringBuilder niet. Gebruik dus een StringBuilder als je vanuit 1 thread dat ding gaat gebruiken voor maximale performance.

De link met een regexp ontgaat me. Kan je uitleggen wat je precies wil gaan doen en waarom je denkt dat een StringBuilder je ermee gaat helpen?

[ Voor 9% gewijzigd door Creepy op 14-01-2009 22:28 ]

[BCC]

Wat doet java hier mee dan? :

Java:

buffer += "nogwat";

[Creepy]

Hetzelfde..... Strings zijn immutable (google eens ). Dus voor elke verandering aan een String zal er altijd een nieuwe instantie moeten worden gecreerd waar de wijziging in wordt gezet. Daarna kan de oude String worden geruimt.

[ Voor 13% gewijzigd door Creepy op 14-01-2009 22:39 ]

[jip_86]

Als ik het goed begrijp ga je strings ontleden. Volgens mij heb je dan niet zo veel baat bij het gebruik van StringBuilders. StringBuilders zijn snel als je veel stukken tekst aan een bestaande string wilt toevoegen.

[TeeDee]

Of je voor het parsen van SVG een stringbuilder moet gebruiken weet ik niet. Volgens mij zijn er elegantere en werkbare oplossingen beschikbaar.

Ten 2e kan je eens kijken in:
[JAVA] StringBuilder benchmarks en Alex in "\[C# ASP.NET] Inhoud Array van files tellen"

Eventueel kan je eens kijken in deze resultaten.

[ Voor 15% gewijzigd door TeeDee op 14-01-2009 22:55 ]

[HawVer]

Creepy schreef op woensdag 14 januari 2009 @ 22:26:
Hebben we het hier over Java? Als je een flinke reeks met tekens krijgt waarin je steeds toe wilt voegen dan is het beter om een StringBuilder of StringBuffer te gebruiken. Strings zijn immutable dus als je steeds dezelfde String wilt uitbreiden dan moet er elke keer een nieuwe String aangemaakt worden.

Java:

String buffer = "iets";
buffer = buffer + "nogwat";

Er zul eerst een String worden aangemaakt waar "iets" in staat en vervolgens een nieuwe String waar "ietsnogwat" in staat.

Het gaat om C#, wat voor Java geldt, geldt ook voor C# volgens mij.

Om die overhead te voorkomen kan je een StringBuffer of StirngBuilder gebruiken. StringBuffer is threadsave, StringBuilder niet. Gebruik dus een StringBuilder als je vanuit 1 thread dat ding gaat gebruiken voor maximale performance.

De link met een regexp ontgaat me. Kan je uitleggen wat je precies wil gaan doen en waarom je denkt dat een StringBuilder je ermee gaat helpen?

Ik zit al een stap verder te denken dan ik in mijn eerste post vertel. Ik moet op een efficiente manier letter getal combinaties verwerken. Dus bijvoorbeeld M 800 500 300 resulteert in een move to object met drie integers, maar er kunnen ook andere letters voorkomen. Om dan snel uit te zoeken welke objecten zich in die string bevinden kan ik regular expressies gebruiken. Maar omdat de strings vrij groot kunnen zijn is dat niet efficient. Dus dacht ik, ik maak een class aan die letter voor letter inleest en dan ter plekke er integers van maakt. Maar duizende keren chars converteren naar een string en van de string naar een integer daarvoor kan ik misschien beter een stringbuilder gebruiken?

[MLM]

Als het echt om veel data gaat, dan moet je misschien aan een lexxer gaan denken. Maar, zo'n SVG als die jij linkt is echt maar een paar KB, dan hoef je je echt geen zorgen over performance te gaan maken.

Bouw eerste eens een naieve oplossing, en haal dat door een profiler, zodat je weet of er een bottleneck is, en zo ja, waar.

(ik zie net pas dat het XML is, wrom gebruik je niet een XML parser?)

[HawVer]

MLM schreef op woensdag 14 januari 2009 @ 23:10:
Als het echt om veel data gaat, dan moet je misschien aan een lexxer gaan denken. Maar, zo'n SVG als die jij linkt is echt maar een paar KB, dan hoef je je echt geen zorgen over performance te gaan maken.

Bouw eerste eens een naieve oplossing, en haal dat door een profiler, zodat je weet of er een bottleneck is, en zo ja, waar.

(ik zie net pas dat het XML is, wrom gebruik je niet een XML parser?)

Het gaat niet zozeer om de xml maar om de attributen:
<path d="M-116.554 114.263C-116.554 114.263 -115.098 115.48 -115.674 116.071C-116.25 116.661 -162.638 95.922 -174.992 112.469C-174.992 112.469 -168.247 94.447 -116.554 114.263z"/>

Maar die stringbuilder vraag is een vraag die voortkomt uit mijn 'probleem'. En ik vroeg me af wanneer het de moeite loont om een stringbuilder te gebruiken en wanneer niet.

[ValHallASW]

Die krijg je er ook met een willekeurige XML-parser uit. Kijk eens naar een SAX-parser die je gebruikt om de objecten aan te maken - dat is een stuk praktischer dan zelf het wiel opnieuw uitvinden.

[bomberboy]

HawVer schreef op woensdag 14 januari 2009 @ 22:52:
Ik zit al een stap verder te denken dan ik in mijn eerste post vertel. Ik moet op een efficiente manier letter getal combinaties verwerken. Dus bijvoorbeeld M 800 500 300 resulteert in een move to object met drie integers, maar er kunnen ook andere letters voorkomen. Om dan snel uit te zoeken welke objecten zich in die string bevinden kan ik regular expressies gebruiken.

Lees om te beginnen die signature van Creepy eens over regular expressions
Maar als ik het goed begrijp krijg je de datalijn uit die svg als een string binnen en moet je die verwerken?

Maar omdat de strings vrij groot kunnen zijn is dat niet efficient. Dus dacht ik, ik maak een class aan die letter voor letter inleest en dan ter plekke er integers van maakt. Maar duizende keren chars converteren naar een string en van de string naar een integer daarvoor kan ik misschien beter een stringbuilder gebruiken?

En je wil die string die je binnen krijgt karakter per karakter inlezen, terug naar een string converteren en dan naar een Integer? Dat lijkt me eigenlijk niet de meest elegante oplossing.

Een mogelijkheid is een lexer gebruiken die die string met data voor je converteert naar tokens die je dan verwerkt. Want in zekere zin probeer je dat nu te implementeren denk ik, maar vrees ik dat het niet echt onderhoudbaar blijft. Ik ben niet echt thuis in de gebruikte syntax, dus misschien is dit een beetje overkill. Het zal in ieder geval wel nette code opleveren.

En anders vermoed ik dat je wel een soort van charAt() en substring() methoden hebt in C# waarbij je niet telkens nieuwe objecten moet aanmaken en je dus efficiënter door die datastring laten itereren dan telkens nieuwe objecten aan te maken.

Het hangt er vanaf wat je juist met die data moet doen natuurlijk en hoe de syntax ervan gedefinieerd is.


edit:
oops, blijkbaar beetje laat met deel van mijn opmerking.
Vanwaar al die aandacht voor een StringBuilder? Als ik het goed begrijp wil je toch net een String verwerken en niet opbouwen? dan moet je toch geen nieuwe Strings gaan opbouwen? Eerder substrings/chars parsen/evaluaren/vergelijken?

[ Voor 7% gewijzigd door bomberboy op 14-01-2009 23:44 . Reden: toevoeging ]

[Nick The Heazk]

HawVer schreef op woensdag 14 januari 2009 @ 22:10:
Alleen nu vraag ik me af wat de slimste manier is om die stukken gegevens te converteren naar objecten.

Aangezien je data aangeleverd wordt in XML, is de meest logische aanpak alvast het gebruik van een XML parser. In het onwaarschijnlijke geval dat zo'n parser onvoldoende performant is voor jou doeleinden, kun je zelf iets fabriceren.

Je hebt natuurlijk regular expressions, lekker flexibel maar geen goede performance.

Ik vraag me af of je dat getest hebt. Een goede regex implementatie heeft een lineaire tijdscomplexiteit in de lengte van de invoerstring. Het zou me verbazen dat reguliere expressies niet het gewenste performantieniveau halen. Ik denk al snel aan andere oorzaken. Lees je je strings een voor een in? Of lees je eerst het ganse bestand in en gooi je er dan een reguliere expressie over? Misschien is het handig om wat code te plaatsen.

Dus ben ik nu bezig met een zelfgeschreven reader die stukken van combinatie letter cijfers inleest. Mijn vraag is daar iets beters voor?

Een XML parser gecombineerd met reguliere expressies zou perfect moeten werken.

Is het wel/niet slim om een stringbuilder (stringbuffer) te gebruiken? Performance is een key issue voor mij.

Zoals al eerder werd aangehaald is een StringBuilder (enkel) nuttig indien je een string aan het opbouwen bent (hence the name). Het probleem is namelijk dat in bepaalde talen (zoals Java) Strings immutable objecten zijn. Een uitdrukking als string1 += string2, zorgt er dan voor dat er een nieuw object wordt aangemaakt (inclusief dure call om geheugen te alloceren) die de concatenatie bevat van string1 en string2. Dit herhaaldelijk doen is niet performant. Daarom dat een StringBuilder klasse wordt voorzien. Deze is zodanig geïmplementeerd dat de concatenatie van de string in de builder en een andere string op een efficiënte wijze uitgevoerd kan worden.

[Woy]

Nick The Heazk schreef op woensdag 14 januari 2009 @ 23:48:
Ik vraag me af of je dat getest hebt. Een goede regex implementatie heeft een lineaire tijdscomplexiteit in de lengte van de invoerstring. Het zou me verbazen dat reguliere expressies niet het gewenste performantieniveau halen. Ik denk al snel aan andere oorzaken. Lees je je strings een voor een in? Of lees je eerst het ganse bestand in en gooi je er dan een reguliere expressie over? Misschien is het handig om wat code te plaatsen.

Natuurlijk heeft een regex geen "slechte" performance, maar gewoon een string parsen met een loopje o.i.d. is wel sneller ( Mits natuurlijk goed geimplementeerd, maar dat geld ook voor de Regex ) zeker bij zulke eenvoudige data.

Een XML parser gecombineerd met reguliere expressies zou perfect moeten werken.

Ik zou gewoon een XML parser en simpele string parsing gebruiken. Het gaat hier niet om complexe data, dus dat is eenvoudig in een loopje/met string.split te doen. ( Als ik het zo snel even zie, kan je gewoon op de letters splitten om de losse commands te krijgen, en daarna op spaties om de losse parameters te krijgen )

[Hydra]

Ik snap de link met een stringbuilder niet. Het lijkt me dat je hier nummers moet parsen uit een string, geen strings op moet bouwen?

Wat betreft een regex: een regex heeft als voordeel dat het meteen een filter is voor slechte data. Als een string de juiste regex matched zal het altijd een te parsen nummer zijn bijvoorbeeld.

[ Voor 42% gewijzigd door Hydra op 15-01-2009 18:05 ]

[pkuppens]

Hydra schreef op donderdag 15 januari 2009 @ 18:03:
Ik snap de link met een stringbuilder niet. Het lijkt me dat je hier nummers moet parsen uit een string, geen strings op moet bouwen?

Wat betreft een regex: een regex heeft als voordeel dat het meteen een filter is voor slechte data. Als een string de juiste regex matched zal het altijd een te parsen nummer zijn bijvoorbeeld.

De XML parser is al een deel van de oplossing, maar is ook weer niet helemaal nodig of voldoende.
Waarschijnlijk geeft deze de attributen wel als {key,value}, maar die zijn {"d","langestring als value"}
en je probleem verschuift naar de value parsen.

Ik denk dat een regex de beste oplossing is, omdat het daarmee duidelijk is wat je achterliggende probleem is, namelijk het goed begrijpen en implementeren van een parser voor je syntax en grammatica.

Het implementeert ook makkelijk, je throwt alles wat je parser niet begrijpt, en je weet waar je verder naar moet kijken.

Verder denk ik dat de implementatie van regex-en slimmer zijn dan wat je zelf implementeert, er zit al bijna 40 jaar implementatie ervaring in verwerkt.

Edit: O ja, het heeft niks met stringbuilders te maken.

[ Voor 2% gewijzigd door pkuppens op 15-01-2009 18:47 . Reden: Kleine omissie ]

[Janoz]

Ik snap niet waarom hier een regexp voor nodig is. XML parsing zul je uiteraard een standaard xml implementatie moeten nemen, bij voorkeur een sax parser (de hele dom heb je helemaal niet nodig). De syntax van de vulling van het attribuut is zo simpel als het maar kant. Zelfs degene die voor het eerst een stackbased parser wil maken zal hier geen enkele moeite mee hebben. Een regexp is pure overkill en toch echt inefficienter.

[DarthDavy]

Ik zou zoiets al volgt implementeren. Het is wel VB.NET (ben daar nu eenmaal iets vlotter in dan C#, maar omzetten is niet zo moeilijk)

code:

Module Module1

    Sub Main()
        Dim str As String = "M-116.554 114.263C-116.554 114.263 -115.098 115.48 -115.674 116.071C-116.25 116.661 -162.638 95.922 -174.992 112.469C-174.992 112.469 -168.247 94.447 -116.554 114.263z"
        Dim separators() As Char = {" ", "M", "C", "z"}
        Dim strList As List(Of String) = str.Split(separators).ToList
        strList.RemoveAll(AddressOf RemoveEmptyStrings)
        Dim dblList As List(Of Double) = strList.Select(Of Double)(AddressOf TransformToDouble).ToList
    End Sub

    Private Function RemoveEmptyStrings(ByVal str As String) As Boolean
        Return String.IsNullOrEmpty(str)
    End Function

    Private Function TransformToDouble(ByVal str As String) As Double
        Dim dbl As Double
        Double.TryParse(str.Replace(".", ","), dbl)
        Return dbl
    End Function

End Module

Ik heb jouw opgegeven string uit de xml omgevormd naar een lijstje van doubles die erin zitten. Als je de integers wilt, kan je het makkelijk aanpassen.

[rrrandy]

Misschien een stomme vraag hoor, maar zijn er geen bestaande libraries die SVG's in kunnen lezen?

[MrBucket]

DarthDavy schreef op vrijdag 16 januari 2009 @ 15:57:
Ik zou zoiets al volgt implementeren. Het is wel VB.NET (ben daar nu eenmaal iets vlotter in dan C#, maar omzetten is niet zo moeilijk)

code:

Module Module1

    Sub Main()
        Dim str As String = "M-116.554 114.263C-116.554 114.263 -115.098 115.48 -115.674 116.071C-116.25 116.661 -162.638 95.922 -174.992 112.469C-174.992 112.469 -168.247 94.447 -116.554 114.263z"
        Dim separators() As Char = {" ", "M", "C", "z"}
        Dim strList As List(Of String) = str.Split(separators).ToList
        strList.RemoveAll(AddressOf RemoveEmptyStrings)
        Dim dblList As List(Of Double) = strList.Select(Of Double)(AddressOf TransformToDouble).ToList
    End Sub

    Private Function RemoveEmptyStrings(ByVal str As String) As Boolean
        Return String.IsNullOrEmpty(str)
    End Function

    Private Function TransformToDouble(ByVal str As String) As Double
        Dim dbl As Double
        Double.TryParse(str.Replace(".", ","), dbl)
        Return dbl
    End Function

End Module

Ik heb jouw opgegeven string uit de xml omgevormd naar een lijstje van doubles die erin zitten. Als je de integers wilt, kan je het makkelijk aanpassen.

Volgens mij gooi je met

Visual Basic .NET:

Dim strList As List(Of String) = str.Split(separators).ToList

wel alle path instructions weg. Het klopt dat je dan een mooie lijst met doubles overhoudt, maar dan mis je wel de helft van de informatie

[MrBucket]

Ik denk dat je al een heel eind verder bent wanneer je de inhoud van een enkel path's d-attribute kunt vertalen naar een gemixte lijst van doubles (voor de numerieke waardes) en chars (voor de path instructions).

Dit kan met behulp van regexes, maar als je er vanuit gaat dat de aangeleverde SVG-file nooit geen fouten bevat kan het ook een stuk simpeler omdat de path instruction characters geen overlap hebben met die van de numerieke waardes. In C# zou je zoiets krijgen:

C#:

enum CharClass{ Instruction, Numeric, EndOfSequence, Other };

public List Parse(string path)
{
  List tokens = new List();
  
  int currentTokenStart = 0;
  CharClass currentClass = Classify(path[0]);
  CharClass cc;
  
  for(int index = 1; index <= path.Length; index++)
  {
    if(index < path.Length)
      cc = Classify(path[index]) 
    else
      cc = CharClass.EndOfSequence);
      
    if(cc == currentClass)
      continue; //Same class as preceding char, current token is not finished yet.
  
    //Found start of a new token, store previous one.
    string tokenText = path.Substring(currentTokenStart, index - currentTokenStart);
    if(currentClass == CharClass.Instruction)
      tokens.Add(tokenText[0]);  //Instructions are always exactly one character.
    else if(currentClass == CharClass.Numeric)
      tokens.Add(Double.Parse(tokenText, CultureInfo.InvariantCulture));
  
    //Set state for this new token.
    currentTokenStart = index;
    currentClass = cc;
  }
  
  return tokens;
}

public CharClass Classify(char c)
{
  if(Char.IsNumeric(c) || c == '.' || c == '-')
    return CharClass.Numeric;
  else if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'))
    return CharClass.Instruction;
  else
    return CharClass.Other;
}

Code is niet getest en bevat geen checks, maar dit zou het globale idee moeten zijn.

[HawVer]

rrrandy schreef op vrijdag 16 januari 2009 @ 16:40:
Misschien een stomme vraag hoor, maar zijn er geen bestaande libraries die SVG's in kunnen lezen?

Ja, die zijn er voor c#. Die libraries zijn bijna volledig opgebouwd uit regular expressions. Als ik nu een keuze maak voor regular expression ga ik daar zeker weten spijt van krijgen.

[HawVer]

MrBucket schreef op vrijdag 16 januari 2009 @ 17:46:
Ik denk dat je al een heel eind verder bent wanneer je de inhoud van een enkel path's d-attribute kunt vertalen naar een gemixte lijst van doubles (voor de numerieke waardes) en chars (voor de path instructions).

Dit kan met behulp van regexes, maar als je er vanuit gaat dat de aangeleverde SVG-file nooit geen fouten bevat kan het ook een stuk simpeler omdat de path instruction characters geen overlap hebben met die van de numerieke waardes. In C# zou je zoiets krijgen:

Code is niet getest en bevat geen checks, maar dit zou het globale idee moeten zijn.

Ik ga er inderdaad vanuit dat de path geen fouten bevat. Een vergelijkbaar idee had ik ook in mijn hoofd zitten en heb ik nu uitgewerkt. Het is een stackbased parser die eenmalig door de attribuut heen vliegt. Bedankt voor alle reacties.

[ Voor 46% gewijzigd door HawVer op 18-01-2009 12:53 ]

[_Erikje_]

Keihard gejat van een blog van een maatje van mij, maar goed misschien heb je er wat aan.
http://www.linuxonly.nl/docs/17/32_Introduction.html

[HawVer]

Daar heb ik zeker wat aan. Interessant! Dankje