[VB] Meerdere spaties omzetten naar 1 *

[J.Hollemans]

Een leraar bij ons op school (HRO) had het laatst over dat er veel programmeren
wordt gegeven, maar dat het gedeelte om problemen te analyseren steeds minder wordt gegeven.
Het kwam er op neer dat mensen heel goed in Java een for-lusje kunnen maken, maar wanneer ze
een probleem voorgeschoteld krijgen, weten ze er geen raad mee.

Toevallig liep ik vandaag tegen zo'n probleempje:

[probleem]

Ik heb een functie in Visual Basic nodig die overbodige spaties uit een zin haalt.

Dus voor deze zinnen:

code:

"       Dit is een voorbeeld zinnetje" 
"Dit is een voorbeeld zinnetje      "
"Dit        is        een       voorbeeld      zinnetje" 
"       Dit        is        een       voorbeeld      zinnetje      "

Moet ik allemaal de volgende uitkomst krijgen:

code:

"Dit is een voorbeeld zinnetje"

Spaties moeten dus blijven staan, maar overbodige, leading en trailing spaces moeten er uit.
TAB's en dergelijke (overige white-spaces) hoeven niet "geparsed" te worden.

[/probeem]

Het liefst zie ik dit in één recursieve functie. (hoeft niet persé natuurlijk)

Ik heb een uitwerking, maar die vind ikzelf nogal slordig en die post ik hier bewust niet, om
jullie creatieve geesten niet te verontreinigen

Mijn uitwerking bestaat uit één recursieve functie en 2 "normale" functies.

Omdat ik al een uitwerking heb is er geen haast bij ofzow, maar je moet het zien als
een extra oefening om praktische programmeer problemen op te lossen.

Wie lukt dit ?

[Paul]

Is vrij simpel hoor.

Eerst trim je het geheel, leading en trailing spaties eraf.

Dan in een loopje alle karakters af, ieder karakter dat geen 2e of meer spatie is kopieer je naar een 2e string

Even in pascal, ik ken geen VB

code:

function huiswerk(tekst: string): string;
var spatie_gehad : boolean;
begin
  result := '';
  spatie_gehad := false;
  tekst := trim(tekst);
  for index := 1 to length(tekst) do
    begin
      if (tekst[index] = ' ') then
        begin
          if not spatie_gehad then
            begin
              result := result + tekst[index];
              spatie_gehad := true;
            end;
        end;
      else
        begin
          result := result + tekst[index];
          spatie_gehad := false;
        end;
    end;
end;

[ Voor 0% gewijzigd door Paul op 14-09-2002 23:01 . Reden: Is btw niet eens recursief :) ]

[nxt]

JeroenHollemans schreef op 14 september 2002 @ 22:50:Het liefst zie ik dit in één recursieve functie. (hoeft niet persé natuurlijk)

wat is in dit geval het voordeel van een recursieve functie?
je moet de gehele string 1x doorlopen
en daarmee ben je klaar
dus ik zou zelf net als paul in z'n voorbeeld voor een for-lus gaan

[Alarmnummer]

Uhhh.. dit riekt toch enorm veel naar een 'willen jullie mijn huiswerk ff maken want ik ben er eigelijk te lam voor' Post jouw code hier eerst maar eens even.

[.oisyn]

idd, wat heb je zelf al geprobeerd?

ik heb ook even je titel aangepast, want die gaf niet echt duidelijk aan wat er in de topic te vinden was

[J.Hollemans]

Ik was al bang voor zo'n zielige reactie, maar goed, ik ben al blij genoeg dat er (nog) geen slotje op deze thread zit...

Hier is mijn implementatie:

code:

Public Function removeSpaces(Message As String) As String
    removeSpaces = removeTrailingSpaces(removeSpacesBeforeWords(Message))
End Function

Public Function removeSpacesBeforeWords(Message As String) As String
    Dim firstWord As String
    Dim restString As String

    While (Left(Message, 1) = " ")
        Message = Right(Message, Len(Message) - 1)
    Wend
    
    If (InStr(Message, " ") = 0) Then
        removeSpacesBeforeWords = Message
    Else
        firstWord = Left(Message, InStr(Message, " "))
        restString = Right(Message, Len(Message) - (InStr(Message, " ") - 1))

        removeSpacesBeforeWords = firstWord & removeSpaces(restString)
    End If

End Function

Public Function removeTrailingSpaces(Message As String) As String

    While (Right(Message, 1) = " ")
        Message = Left(Message, Len(Message) - 1)
    Wend

    removeTrailingSpaces = Message

End Function

En ff voor alle duidelijkheid: het is geen huiswerk, het is een zelf verzonnen opdracht om programmeer inzichten te vergroten.

Waarschijnlijk kan dit zelfs met één bestaande functie aanroep, net zoiets als:

PHP:

$string = preg_replace("/s{2,}/", " ", $string);

Maar dat was het doel van deze thread niet...
Het gaat er meer om of mensen de praktische kant van een programmeer probleem inzien of niet.

Ik geloof dat het niet zo'n goed idee was om dit hier te posten vanwege die stomme tweaker-instelling... bah

Voor het geval er nu een slotje aan komt: Stoer hoor

edit:


Paul: bedankt, da's tenminste iets concreets... Gelukkig ken ik wel Pascal

op die manier kan je verschillende programmeer technieken en inzichten met elkaar vergelijken

[.oisyn]

er al eens aan gedacht om een psychiater op te zoeken? Je blijkt namelijk nogal snel op je tenen getrapt te zijn

[J.Hollemans]

er al eens aan gedacht om een psychiater op te zoeken? Je blijkt namelijk nogal snel op je tenen getrapt te zijn

Ik geloof dat dat te danken is aan sommige tweaker-moderators/administrators, maar dat gaat nogal off-topic

[.oisyn]

kom eens met concrete voorbeelden dan

.edit: ik zie dat je 72 posts hebt, en nog geen van je topics is op slot gegaan. Dus ik snap echt niet wat je nou loopt te klagen
En de reactie van Alarmnummer kan ik ook begrijpen. Als je op je naam klikt krijg je een lijst met vooral topics die je zelf geopend hebt (de zogenaamde helpdesk-user). Combineer dat met het feit dat je over school begon en de conclusie is al snel getrokken

Maar goed, er wordt gevraagd of je zelf wat code wil posten, en dan begin je gelijk moord en brand te roepen, dat je topic wel weer snel op slot zou zitten (en waarom? ik zie geen aanleiding tot een slotje), en dat de zogenaamde tweaker-instelling stom en stoer is.

Als je er zo over denkt, waarom kom je hier uberhaupt dan nog? Dan ga je toch lekker een ander forum op zoeken waar het allemaal zo goed en beter zou zijn?

[mbravenboer]

Is er geen StringTokenizer oid beschikbaar?

[J.Hollemans]

.edit: ik zie dat je 72 posts hebt, en nog geen van je topics is op slot gegaan. Dus ik snap echt niet wat je nou loopt te klagen

Ik lees meer posts dan alleen die van mezelf hoor...

Als je op je naam klikt krijg je een lijst met vooral topics die je zelf geopend hebt

Klopt, maar je vergeet misschien dat ik ook zelf antwoorden geef op die threads als ik het eerder heb gevonden dan de lezers
Dus ik ben niet iemand die hopeloos wacht totdat iemend eindelijk iets nuttigs post

waarom kom je hier uberhaupt dan nog?

Dat vraag ik me idd ook af

Maargoed, dit gaat nogal off-topic. Ik wil er wel over discutieren, maar dan niet hier...
En het is trouwens geen offence hoor, maar gewoon mijn mening (en van een aantal anderen) hoe er tegen tweakers aan wordt gekeken.

[kvdveer]

In PHP:

PHP:

$text = preg_replace("/ +/"," ",$text);

Wat zijn regexpen toch makkelijk ;-)

[Soultaker]

Mijn contributie in C:

code:

void cleanup(char *p) 
{
        char *q=p;
        while(*q==' ') ++q;
        while(*q)
        {
                while((*q)&&(*q!=' ')) *p++=*q++;
                while(*q==' ') ++q;
                if(*q) *p++=' ';
        }
        *p='\0';
}

Gelukkig, ik kan 't nog!

[J.Hollemans]

mbravenboer schreef op 14 september 2002 @ 23:34:
Is er geen StringTokenizer oid beschikbaar?

Misschien wel, maar dat is niet mijn bedoeling van deze thread.

Het is mijn bedoeling om meerdere oplossingen van andere personen te vergelijken, om zo een breder
inzicht te krijgen in verschillende programmeer methoden.

edit:


kvdveer snapt het ook niet, Soultaker wel...

Een oplossing met gebruik van pointers in C, zeer interressant.
Bedankt voor je bijdrage !

[Soultaker]

kvdveer schreef op 14 september 2002 @ 23:44:
In PHP:

PHP:

$text = preg_replace("/ +/"," ",$text);

Wat zijn regexpen toch makkelijk ;-)

Zeker, maar dit is echt fout (net als de eerder gepostte regexp) aangezien de leading en trailing whitespace gewoon tot 1 karakter (en niet 0, zoals de bedoeling was) gereduceerd wordt.

Maak daar dus maar een iets interessantere regexp van.

[mbravenboer]

JeroenHollemans: Misschien wel, maar dat is niet mijn bedoeling van deze thread.

Ach, de StringTokenizer is ook een oplossing en in de praktijk misschien wel het eenvoudigst en snelst om te programmeren . Je kan hem dus meenemen in je vergelijking.

Hier nog een oplossing in SDF (context-vrije grammatica) om je vergelijking nog rijker te maken:

code:

module Main

exports
  sorts Line

  context-free syntax
    Token+ -> Line
  
  lexical syntax
    [A-Za-z]+ -> Token
    [\ \t\n]  -> LAYOUT

  lexical restrictions
    Token   -/- [A-Za-z]
    LAYOUT? -/- [\ \t\n]

.

[.oisyn]

JeroenHollemans schreef op 14 september 2002 @ 23:39:
Maargoed, dit gaat nogal off-topic. Ik wil er wel over discutieren, maar dan niet hier...
En het is trouwens geen offence hoor, maar gewoon mijn mening (en van een aantal anderen) hoe er tegen tweakers aan wordt gekeken.

definieer 'tweaker'
nogal generalizerend, denk je ook niet? (kom je toevallig vaak op fok ?)
maar het is idd offtopic, dus stuur me maar een mailtje (zie profile), ik heb wel zin in een discussie

[mbravenboer]

JeroenHollemans: kvdveer snapt het ook niet, Soultaker wel...
Een oplossing met gebruik van pointers in C, zeer interressant.

Merkwaardig. Kennelijk gaat het dus om zo efficient mogelijk code. Waarom meldde je dat dan niet even?

Ik denk trouwens dat alleen maar streven naar een efficiente oplossingen qua executie tijd een beetje onzinnig is. Je moet hotspots in je code gaan optimaliseren, niet al je code. Als dit een hotspot is, dan ga je nadenken over een efficiente implementatie. Als het geen hotspot is, pak je gewoon de methode die jou als programmeer zo weinig mogelijk tijd kosten en vooral ook de meeste inzicht biedt in de correctheid van de oplossing. Ga hierover maar eens met die ontzettend verstandige docent in discussie.

Het probleemoplossend vermogen van een programmeur heeft sowieso vrij weinig te maken met de taal waarin hij werkt (behalve als de taal een probleem is en hij nog steeds niet overgestapt is ). Het noemen van Java en een for-loop vind ik dus vrij onzinnig. Je schrijft in Java trouwens maar zelden een for-loop.

[J.Hollemans]

ik heb wel zin in een discussie

Waarom reacheerde je dan niet om m'n icq berichtje ?

[/offtopic]

mbravenboer: Ik ken dat taaltje niet en ik kan er ook niet echt wijs uit...
Kan je mij misschien het princiepe van een "StringTokenizer" uitleggen ?

vast bedankt !

[Alarmnummer]

JeroenHollemans schreef op 14 september 2002 @ 23:18:
Ik was al bang voor zo'n zielige reactie, maar goed, ik ben al blij genoeg dat er (nog) geen slotje op deze thread zit...

Hmmzz.. als je eens even goed nadenkt dan zul je zelf ook inzien dat je topic toch zo overkomt. Er zijn genoeg mensen die je met allerlei leuke algoritmes willen helpen maar huiswerkvragen die worden echt afgekeurd omdat jij ook werk moet verichten. Aangezien jij niet kwam met code vond ik het vrij verdacht. Dat jij mijn reply dan zielig vind ik persoonlijk weer dan iets minder.

Het gaat er meer om of mensen de praktische kant van een programmeer probleem inzien of niet.

Er worden hier genoeg mensen geholpen, maar het is hier geen helpdesk. Aangezien jij geen eigen inbring gaf in dit topic vond ik mijn reactie zeer terecht.

Ik geloof dat het niet zo'n goed idee was om dit hier te posten vanwege die stomme tweaker-instelling... bah

Voor het geval er nu een slotje aan komt: Stoer hoor

Ik had hem nu persoonlijk op slot gedaan. Je mag blij zijn dat het nog open is.

op die manier kan je verschillende programmeer technieken en inzichten met elkaar vergelijken

Algoritmes zijn vaak irrelevant. Het gaat erom of je een hoger inzicht kan krijgen en een algoritme is alleen een manier om iets voor elkaar te krijgen. Er zijn dikke algoritme boeken uit waarin al een enorme lading dingen zijn uitgewerkt.

[J.Hollemans]

mbravenboer schreef op 14 september 2002 @ 23:57:
[...]

Merkwaardig. Kennelijk gaat het dus om zo efficient mogelijk code. Waarom meldde je dat dan niet even?

Nee nee, dat is het echt niet. Het gaat over verschillende methoden.
Ik heb nu al een functionele oplossing gezien (trim leading en trailing spaces en de rest in een lusje)
een recursieve (mijn eigen) en dan die met pointers.

* J.Hollemans dacht niet eens aan pointers (in eerste instantie), dus vandaar dat ik het zo interressant vond.

En dat van java met een for-lusje is ook alleen maar een voorbeeldje...

edit:


Alarmnummer: jaja, tis al goed...

[.oisyn]

JeroenHollemans schreef op 14 september 2002 @ 23:59:
[...]

Waarom reacheerde je dan niet om m'n icq berichtje ?

als je even de tijd had genomen om mijn icq users details door te nemen kon je bij about lezen dat ik mijn icq zo heb geconfigureerd dat ie geen berichten accepteerd van mensen die niet in mijn contact list staan

Dus stuur maar een mailtje

[mbravenboer]

JeroenHollemans: mbravenboer: Ik ken dat taaltje niet en ik kan er ook niet echt wijs uit...

Het is een syntax definitie formalisme. Context-vrije grammatica dus. Wordt met name gebruikt voor het definieren van programmeertalen.

Kan je mij misschien het princiepe van een "StringTokenizer" uitleggen ?

Gegeven een aantal scheidingstekens levert een StringTokenizer steeds het volgende token in een String.

Hier zie je de toepassing:

code:

import java.util.StringTokenizer;

public class Main {
  public static void main(String[] ps) {
    StringTokenizer tokenizer = new StringTokenizer(" Dit   is een voorbeeld    ", " ");

    StringBuffer result = new StringBuffer();

    while(tokenizer.hasMoreTokens()) {
      result.append(tokenizer.nextToken());

      if(tokenizer.hasMoreTokens()) {
        result.append(' ');
      }
    }

    System.out.println("Result: " + result.toString());

  }
}

[Alarmnummer]

JeroenHollemans schreef op 15 september 2002 @ 00:04:
Alarmnummer: jaja, tis al goed...

Ik ben blij dat je goed vind wat ik allemaal doe. Ik denk dat ik straks goed in slaap kan komen.. dank je..

[Soultaker]

mbravenboer schreef op 14 september 2002 @ 23:57:
Merkwaardig. Kennelijk gaat het dus om zo efficient mogelijk code. Waarom meldde je dat dan niet even?

Het gaat in de eerste plaats om een correcte implementatie en dat was die van kvdveer niet (nofi). In de tweede plaats gaat het altijd om een efficient algoritme.

Als je de complexiteit en efficientie van je algoritme niet beschouwt heeft het helemaal geen zin om over wel algoritme dan ook na te denken. Dan kun je beter een succesconditie opstellen en dan brute-force naar de oplossing zoeken.

Dat betekent in het bijzonder dat als je voor dit probleem meerdere keren over de string heenloopt, je waarschijnlijk onhandig bezig bent. Als het aantal keren dat je d'r overheen loopt afhankelijk is van de lengte van de invoer, ben je zeker verkeerd bezig.

[J.Hollemans]

Alarmnummer schreef op 15 september 2002 @ 00:12:
[...]


Ik ben blij dat je goed vind wat ik allemaal doe. Ik denk dat ik straks goed in slaap kan komen.. dank je..

[mbravenboer]

JeroenHollemans: Ik heb nu al een functionele oplossing gezien

Ik hoop dat je niet functioneel programmeren bedoeld .

Hier een oplossing met een fold in Stratego:

code:

  main =
      <tokenize> ("Dit is   een  test van  een tokenizer", " ")
    ; separate-by(!" ")
    ; foldr(!"", conc-strings)

Dit is vergelijkbaar met een oplossing in een functionele taal als Haskell.

[.oisyn]

kvdveer schreef op 14 september 2002 @ 23:44:
In PHP:

PHP:

$text = preg_replace("/ +/"," ",$text);

Wat zijn regexpen toch makkelijk ;-)

jammer genoeg verwijderd die niet de spaties aan begin en eind

[mbravenboer]

Soultaker: Het gaat in de eerste plaats om een correcte implementatie en dat was die van kvdveer niet (nofi).

Hum, dat had ik nog geeneens gezien .

In de tweede plaats gaat het altijd om een efficient algoritme.

Mwah, daar kunnen we nog aardig over discussieren . Ik vind het overigens ook wat ver gaan om het verwijderen van overtollige spaties al gelijk als een algoritmisch interessant probleem te zien en dus iets om je druk over te maken .

[J.Hollemans]

Soultaker schreef:

Als je de complexiteit en efficientie van je algoritme niet beschouwt heeft het helemaal geen zin om over wel algoritme dan ook na te denken. Dan kun je beter een succesconditie opstellen en dan brute-force naar de oplossing zoeken.

Dat betekent in het bijzonder dat als je voor dit probleem meerdere keren over de string heenloopt, je waarschijnlijk onhandig bezig bent. Als het aantal keren dat je d'r overheen loopt afhankelijk is van de lengte van de invoer, ben je zeker verkeerd bezig.

_Precies_ !

En dat brengt ons op de O-notatie...
Btw: Die code van jou is (in theorie) ook afhankelijk van de lengte van de invoer. (O (n))
Maar ik denk dat je daar in dit geval niet onderuit komt

[Alarmnummer]

Soultaker schreef op 15 september 2002 @ 00:14:
[...]

Het gaat in de eerste plaats om een correcte implementatie en dat was die van kvdveer niet (nofi). In de tweede plaats gaat het altijd om een efficient algoritme.

Dit ben ik niet met je eens. Een algoritme moet onderhoudbaar en inzichtelijk zijn en daarom stel ik optimalisaties meestal niet op prijs. Je zult denk ik een voldoende snelle implementatie van een bepaald stuk functionaliteit moeten maken zonder dat de code slecht te onderhouden is.

[mbravenboer]

Een subtiele verbetering in de grammatica oplossing:

code:

module Main

exports
  sorts Line

  context-free syntax
    Token+ -> Line
  
  lexical syntax
    ~[\ \t\n]+ -> Token
     [\ \t\n]  -> LAYOUT

  lexical restrictions
    Token   -/- ~[\ \t\n]
    LAYOUT? -/-  [\ \t\n]

Tokens mochten eerst alleen uit letters bestaan .

[mbravenboer]

JeroenHollemans: _Precies_ ! En dat brengt ons op de O-notatie...

Ik ben heel goed bekend met de berekening van de looptijd van algoritmen, maar ik ben ook bekend met het fenomeen dat een applicatie meestal meer dan 90% van de tijd in minder dan 10% van de code doorbrengt. Je kan je dan druk gaan maken om de efficientie van alle code, maar je kan je beter beperken tot deze 10%: daar zal je de meeste winst mee behalen aangezien de beschikbare programmeertijd altijd de beperkende factor is. Je moet dus zoals ik al eerder zei de hotspots gaan opzoeken en _die_ optimaliseren. Als dit een hotspot is in je applicatie: prima, maar het is dan waarschijnlijk wel een wat suffe applicatie .

[Soultaker]

Alarmnummer schreef op 15 september 2002 @ 00:20:
Dit ben ik niet met je eens. Een algoritme moet onderhoudbaar en inzichtelijk zijn en daarom stel ik optimalisaties meestal niet op prijs. Je zult denk ik een voldoende snelle implementatie van een bepaald stuk functionaliteit moeten maken zonder dat de code slecht te onderhouden is.

Vind je dan dat je een O(N^2) algoritme moet implementeren wanneer dat duidelijker is dan O(N)? Ik denk van niet en ik hoop dat de ontwikkelaars van de software die ik wil gebruiken dat ook denken.

Ik had het overigens niet over taal-specifieke optimalisaties, maar over het verbeteren van het algoritme. Het algoritme dat ik in C implementeerde zou bijvoorbeeld zonder moeite omgezet kunnen worden naar Java code, zonder dat het complexer wordt.

Natuurlijk hoef je in de praktijk niet moeilijk te doen als makkelijk goed genoeg is, maar dan hoef je er ook niet op GoT over te discussieren, natuurlijk.

mbravenboer schreef op 15 september 2002 @ 00:18:
Ik vind het overigens ook wat ver gaan om het verwijderen van overtollige spaties al gelijk als een algoritmisch interessant probleem te zien en dus iets om je druk over te maken .

Ik kan me voorstellen dat als je een command line utillity maakt om tekst files mee te filteren, het wel uitmaakt of je eerst alle invoer in je geheugen moet laden, opsplitsen, vervolgens weer samenvoegen en dan weer printen, of alle invoer on-the-fly verwerkt.

Verder is dit natuurlijk niet het meest relevante probleem dat je kan verzinnen, maar het ging me om het principe.

[marcusk]

aangezien er nog geen werkende regex oplossing gegeven is:

PHP:

$str = preg_replace("/(^ *)|( *$)|(( )+)/", "\\4", $str);

[Alarmnummer]

Soultaker schreef op 15 september 2002 @ 00:30:
Vind je dan dat je een O(N^2) algoritme moet implementeren wanneer dat duidelijker is dan O(N)? Ik denk van niet en ik hoop dat de ontwikkelaars van de software die ik wil gebruiken dat ook denken.

Nee, de complixiteit van het algoritme onnodig te gaan verhogen zou inderdaad een domme zet zijn. Maar ik doel voornamelijk op micro optimalisaties: taal specifieke optimalisaties waardoor de leesbaarheid van een algoritme volledig naar zijn grootje kan gaan. *was vroeger zo`n (gevaarlijk) figuur*

[J.Hollemans]

idd, het gaat meer om het principe.

En wat betreft die "hot-spots": natuurlijk, dat spreekt voor zich

Vind je dan dat je een O(N^2) algoritme moet implementeren wanneer dat duidelijker is dan O(N)? Ik denk van niet en ik hoop dat de ontwikkelaars van de software die ik wil gebruiken dat ook denken.

LOL... uiteraard

[Stilgar]

Ik zou het in VB zo doen, denk ik:

code:

    Dim s As String
    
    s = "   Dit is    een string  "
    
    Do While (InStr(s, "  ") > 0)
        s = Replace(s, "  ", " ")
    Loop

[Alarmnummer]

Maar aan de andere kant ga ik niet extreem veel moeite doen voor een 10% van de tijd stuk code. Als daar een onnodig gecompliceerd algoritme aanwezig is en het werkt goed dan ga ik het niet aanpassen.

[edit]
tenzij ik jeuk krijg of niets beters heb te doen

[Soultaker]

Alarmnummer schreef op 15 september 2002 @ 00:35:
Nee, de complixiteit van het algoritme onnodig te gaan verhogen zou inderdaad een domme zet zijn. Maar ik doel voornamelijk op micro optimalisaties: taal specifieke optimalisaties waardoor de leesbaarheid van een algoritme volledig naar zijn grootje kan gaan. *was vroeger zo`n (gevaarlijk) figuur*

Dan zijn we het wel eens, geloof ik.

Stilgar schreef op 15 september 2002 @ 00:36:
Ik zou het in VB zo doen, denk ik:

code:

    Dim s As String
    
    s = "   Dit is    een string  "
    
    Do While (InStr(s, "  ") > 0)
        s = Replace(s, "  ", " ")
    Loop

Dat is typisch wat ik bedoel met onnodig inefficiente code.

Voor elke overbodige spatie moet je de string tweemaal doorlopen (een keer tot je 'm gevonden hebt en de tweede keer helemaal). Een kwadratisch algoritme waar een lineair algoritme ook had volstaan.

Als je dit algoritme zou gebruiken om een flink tekstdocument mee te formatteren, kom je er niet mee weg. Ik gok dat je met een bestand van een paar duizend regels (toch niet belachelijk veel) al snel een paar seconden tot een minuut of wat zit te wachten.

Het algoritme is ook niet correct, trouwens, want je doet nu niets met spaties aan 't begin en einde van de string.

[mbravenboer]

Soultaker: Vind je dan dat je een O(N^2) algoritme moet implementeren wanneer dat duidelijker is dan O(N)? Ik denk van niet en ik hoop dat de ontwikkelaars van de software die ik wil gebruiken dat ook denken.

Als je een bestaand en algemeen bekend algoritme kan pakken lijkt het mij duidelijk dat je de meest efficiente pakt. Als je echter zelf een algoritme moet gaan ontwerpen moet je kiezen: of je doet het grondig en onderbouwd de correctheid van je algoritme ook, of je zorgt er voor dat je de correctheid redelijk goed kan overzien zoals bijvoorbeeld in de tokenize oplossingen die ik liet zien. Als dit later tot een hotspot kan leiden, kan je altijd later nog besluiten om dit deel te gaan optimaliseren.

Voorlopig is het nog zo dat we er nog steeds moeite mee hebben om correcte code te schrijven. Ik heb liever dat de programmeur van software die ik gebruik wat meer nadruk ligt op correctheid van zijn code dan op de efficientie. Efficientie is prima, maar dan wel onderbouwd.

Als je een tool als grep of andere tekst-processing tools is het matchen en replacing gedeelte zo belangrijk in de applicatie, dat het nogal duidelijk is dat je daar goed over nadenkt. In denk echter dat je dergelijke 'algoritmes' veel vaker zal toepassen als tamelijk irrelevant onderdeel van een normale applicatie.

[mbravenboer]

Soultaker: Dat is typisch wat ik bedoel met onnodig inefficiente code.

Dit is inderdaad niet bepaald een alternatief waarover ik zou willen discussieren . De StringTokenizer is dan een aardiger punt van discussie, maar een discussie is tamelijk zinloos als je de rol van het algoritme in een applicatie niet weet.

[Stilgar]

Soultaker schreef op 15 september 2002 @ 00:41:


[...]


Dat is typisch wat ik bedoel met onnodig inefficiente code.

Point taken, je hebt uiteraard gelijk

Het algoritme is ook niet correct, trouwens, want je doet nu niets met spaties aan 't begin en einde van de string.

Inderdaad, dr moet nog een trim voor.

[.oisyn]

erg he, die zogenaamde 'tweaker-instelling'... ze zijn allemaal zo onaardig tegen je

[Sponge]

Moet het perse recursief zijn? anders gebruik je toch gewoon Replace$(strstring," ", " ") oid?

[Alarmnummer]

Het gaat om het ontwerp van het algoritme en niet om een kant en klare. En jij gaat iedere spatie vervangen door een andere?

[WimB]

Waarom werk je niet met een Split? Dan krijg je lege elementen als er meerdere spaties achter elkaar komen. En die kan je er gemakkelijk uitfilteren. Zoiets misschien (als ik niets over het hoofd heb gezien):

code:

    Tabel = Split(strTekst, " ")
    For Each Element In Tabel
        If Len(Element) > 0 Then strNieuw = strNieuw & Element & " "
    Next Element

strInvoer is nogal logisch de invoer, het resultaat zit in strNieuw.

Wie doet korter?

[Alarmnummer]

Jij maakt hier gebruik van allerlei constructies, dus als ik dat ook mag doen:
String result = toSingleSpace(s);

die van mij is dus het korste.

[WimB]

Alarmnummer schreef op 15 september 2002 @ 11:31:
Jij maakt hier gebruik van allerlei constructies, dus als ik dat ook mag doen:
String result = toSingleSpace(s);

die van mij is dus het korste.

Ja, maar die van mij werkt echt. En dat in 4 regeltjes. Dat vond ik nu toch wel een prestatie. Probeer maar eens korter

edit:

Ik gebruik dus allemaal echte VB-functies. Geen constructies (alleen de If op één lijn)

[Alarmnummer]

Jij maakt gebruik van een opsplits constructie die aanwezig is. Daarom kun je sowieso al niet spreken over de korste. En daarnaast zijn gesprekken over wie heeft de kortste ook niet bijster interessant Het gaat erom hoe onderhoudbaar en inzichtelijk het is, en 'ten liners' maken is echt uit den boze.

[WimB]

Alarmnummer schreef op 15 september 2002 @ 11:35:
Jij maakt gebruik van een opsplits constructie die aanwezig is. Daarom kun je sowieso al niet spreken over de korste. En daarnaast zijn gesprekken over wie heeft de kortste ook niet bijster interessant Het gaat erom hoe onderhoudbaar en inzichtelijk het is, en 'ten liners' maken is echt uit den boze.

Maar de opsplitsconstructie zit toch standaard in VB?

OK, echt overzichtelijk is mijn code niet. Maar ik wilde gewoon eens weinig regeltjes verkrijgen. Ik moet mij toch met iets bezighouden hé

[Alarmnummer]

Daarnaast is jouw aanpak vrij inefficient: alle characters worden meerdere keren gelezen en geschreven en dat is onnodig.

[J.Hollemans]

Het gaat helemaal niet over "zo kort mogelijk". Lees die thread nou nog eens rustig door.
Het is juist de bedoeling om zelf algoritmen te bedenken en die ook weten toe te passen.

Maar ik zie iig al leuke resultaten. Opvallend is wel dat er een hoop "oplossingen" worden
gegeven die niet blijken te werkten.
Zegt dat iets over de programmeur ? de tester ? de analyst ? de opdrachtgever ?
Waar zou zoiets nou aan kunnen liggen ?

Ik vond het een nogal simpele "opdracht", moet je nagaan als het iets moeilijker wordt...

graag uw reacties

[Alarmnummer]

Maar ik snap niet waarom je zoveel waarde hecht aan algoritmes. Algoritmes zijn een hulpmiddel om iets voor elkaar te krijgen en het is niet waar het om gaat.

[M_de_Hilg]

Uiteraard is de manier waarop je je algoritmen maakt zeer persoonlijk. Dit lijkt mij een nette manier.

code:

    Dim invoer, uitvoer, curcar As String
    Dim second As Boolean
    second = False
    
    invoer = "    Hoi    dit is de    test   "
    
    'Remove spaces at began and end.
    invoer = Trim(invoer)
    
    'Remove double spaces (leave only the first in a row)
    For n = 1 To Len(invoer) Step 1
        curcar = Mid(invoer, n, 1)
        If curcar = " " Then
            If second = False Then
                second = True
                uitvoer = uitvoer & curcar
            End If
        Else
            second = False
            uitvoer = uitvoer & curcar
        End If
    Next n

[Sponge]

Alarmnummer schreef op 15 september 2002 @ 11:08:
Het gaat om het ontwerp van het algoritme en niet om een kant en klare. En jij gaat iedere spatie vervangen door een andere?

vaag

ik had "2 spaties", "1 spatie" als vervanging.

hmm, ff testen: "123 <-2 spaties"

[Twee Dee]

JeroenHollemans schreef op 15 september 2002 @ 11:44:

Maar ik zie iig al leuke resultaten. Opvallend is wel dat er een hoop "oplossingen" worden
gegeven die niet blijken te werkten.
Zegt dat iets over de programmeur ? de tester ? de analyst ? de opdrachtgever ?
Waar zou zoiets nou aan kunnen liggen ?

graag uw reacties

"
Het schrijven van de code kost 20% van de tijd, het debuggen kost de overige 80%.
Ik geloof dat de meeste oplossingen worden gepost zonder dat diegene het al heeft uitgewerkt en op de kleine slordigheidjes is gestuit. In een normale programmeersituatie werkt bijna nooit iets zonder enige bijschavingen.

[Alarmnummer]

41.6C.6D.61.72 schreef op 15 September 2002 @ 12:13:
[...]


vaag

ik had "2 spaties", "1 spatie" als vervanging.

hmm, ff testen: "123 <-2 spaties"

hmmzz.. en wat nu als je 4 spaties achter elkaar krijgt? Dit werkt dus niet

[dusty]

Alarmnummer schreef op 15 september 2002 @ 12:27:
[...]

hmmzz.. en wat nu als je 4 spaties achter elkaar krijgt? Dit werkt dus niet

De "domme" php methode (met het vervangen van 2 spaties met 1 spatie) die toch "goed" werkt:

PHP:

function replace2spaces($invoer) {

$uitvoer=str_replace("  "," ",$invoer);

if ($invoer!=$uitvoer) {
  $uitvoer=replace2spaces($uitvoer);
} 

return trim($uitvoer);
}

De gedachtengang achter deze functie mag iedereen zelf bedenken

De nog dommere methode met een for-lus:

PHP:

functie dommespatieroutine($invoer) {

$uitvoer="";
$lastchar="";
for ($t=0;$t<strlen($invoer);$t++) {
  if (($lastchar!=" ") or ($lastchar!=$invoer[$t])) {
    $lastchar=$invoer[$t];
    $uitvoer.=$lastchar;
  }
}

return trim($uitvoer);
}

[Alarmnummer]

dusty schreef op 15 september 2002 @ 13:25:

[...]

De "domme" php methode (met het vervangen van 2 spaties met 1 spatie) die toch "goed" werkt:

Maar deze is zo traag als stront door een rietje

De nog dommere methode met een for-lus:

PHP:

functie dommespatieroutine($invoer) {
$uitvoer="";
$lastchar="";
for ($t=0;$t<strlen($invoer);$t++) {
  if (($lastchar!=" ") or ($lastchar!=$invoer[$t])) {
    $lastchar=$invoer[$t];
    $uitvoer.=$lastchar;
  }
}

return trim($uitvoer);
}

Leuke routine, alleen die trim op het einde is minder geslaagd. Onderhuids gaat deze nog een keer de string bijlangs.

[ta_chi79]

Hier even wat Delphi code.
Ik maak hier gebruik van de qStrings-library (te vinden op Torry.net)

code:

procedure TForm1.Button1Click(Sender: TObject);
var
  lTemp: string;
begin
  // initialiseren van string
  lTemp := ' Dit        is     een     test        .  ';

  // alle dubbele spaties vervangen door eentje
  Q_ReplaceCharsByOneChar(lTemp, [' '], ' ');

  // de punt achter een zin direct achter het laatste woord
  // NOTE: iedereen schijnt deze te vergeten, maar hoort er toch wel bij
  lTemp := Q_ReplaceText(lTemp, ' .', '.');

  // nu nog even de spaties voor en achteraan
  lTemp := Trim(lTemp);

  // dit is het resultaat met voor de duidelijkheid kwootjes eromheen
  MessageDlg('"' + lTemp + '"', mtInformation, [mbOk], 0);
end;

Met Q_ReplaceCharsByOneChar(lTemp, [' ', #9], ' ') kun je bijvoorbeeld alle spaties en tabs vervangen door 1 spatie.

[kvdveer]

code:

# [ESP]: pointer naar null-terminated inputbuffer
# [ESP+4]: pointer naar outputbuffer

   xor   ECX,  ECX      # ECX gaan we gebruiken... Even leegmaken dus
   pop   EAX            # *void inputbuffer (null-terminated)
   pop   EBX            # *void outputbuffer
   mov   EDX, EBX       # *outputbuffer bewaren voor return

:spatie
   mov   CL,   [EAX]
   cmp   CL,   0x20     # Vergelijken met spatie
   jne   verder         # geen spatie? dan doorgaan
   inc   EAX            # Anders verder met volgend karakter
   jmp   spatie
 
:verder                 # EAX wijst naar een legitiem karakter.
   mov   CL,   [EAX]
   mov   [EBX],CL       # dat karakter kopieren we maar.
   inc   EBX            # output alvast naar volgend karakter
   inc   EAX            # input alvast naar volgend karakter
   
   cmp   CL,   0x00     # Einde van de string?
   je    backtrim       # Ja... dan zijn we bijna klaar.
   
   cmp   CL,   0x20
   je    spatie         # Het was een spatie...

:backtrim
                        # Vanaf hier is de buffer [EDX]
                        # bijna klaar. Alleen kan er eventueel nog
                        # een laatste spatie achter staan.
                        # EBX verwijst naar het karakter na de 
                        # terminating null,
   mov   CL,   [EBX-2]  # dus twee terug zou dan die spatie zijn...
   cmp   CL,   0x20     
   jne   klaar          # zo niet, dan zijn we nu klaar.
   
   mov   [EBX-2], 0x00  # anders terminaten we de string wat eerder...

:klaar
   mov   EAX, EDX       # return *output
   
                        # stack is al schoon. Dat scheelt weer.
   ret

100% untested. Waarschijnlijk is íe ook niet foutloos.

[ Voor 0% gewijzigd door kvdveer op 15-09-2002 14:23 . Reden: layout hersteld... ]

[Soultaker]

kvdveer schreef op 15 september 2002 @ 14:15:
assembly code

Ziet er wel correct uit. Creatief gedaan; lekker compact enzo. Je houdt er wel een vreemde calling convention op na trouwens (Pascal ofzo?) En waarom maak je eigenlijk ECX leeg? Dat is toch nergens voor nodig?

Ik denk trouwens dat die spatie sectie wel wat efficienter te krijgen is met een 'rep cmpb', al moet je dan je registers wat anders kiezen.

Verder erg mooie code, hoor...

[sandergar]

De code van M_de_Hilg lijkt mooi maar er zit toch een gedachte fout in! En wel de volgende VBA declaratie:

code:

    Dim invoer, uitvoer, curcar As String

Deze is namelijk niet gelijk aan:

code:

    Dim invoer As String
    Dim uitvoer As String
    Dim curcar As String

Maar is gelijk aan:

code:

    Dim invoer As Variant
    Dim uitvoer As Variant
    Dim curcar As String

Een fout die door veel mensen (waaronder ik zelf) vaak wordt gemaakt!

Op de MSDN site van Microsoft wordt oa het volgende hierover gezegd:

Avoid using the Variant data type unless you are declaring a variable and you truly do not know what kind of data it might contain at run time. Variants are slow, they take up a lot of memory, and using them when not absolutely necessary can create hard-to-find bugs in your code.

Always declare variables as a group at the beginning of each procedure, and always declare each variable on a separate line. This will prevent you from inadvertently declaring a Variant variable. For example, the following line creates two Variant variables and one String variable, which is not what the developer intended:

Dim strFirstName, strLastName, strCompanyName As String

[Paul]

sandergar schreef op 15 september 2002 @ 16:31:
De code van M_de_Hilg lijkt mooi maar er zit toch een gedachte fout in! En wel de volgende VBA declaratie:

En daarnaast is het exact hetzelfde algoritme als in de eerste reply in de thread, nl die van mij
Mijn declaratie klopt overigens ook niet, ik mis de var index : integer;

[M_de_Hilg]

sandergar schreef op 15 september 2002 @ 16:31:
De code van M_de_Hilg lijkt mooi maar er zit toch een gedachte fout in! En wel de volgende VBA declaratie:

[...]

Maar is gelijk aan:

code:

    Dim invoer As Variant
    Dim uitvoer As Variant
    Dim curcar As String

Een fout die door veel mensen (waaronder ik zelf) vaak wordt gemaakt!

Op de MSDN site van Microsoft wordt oa het volgende hierover gezegd:

[...]

Mooi, weer wat geleerd. Moet wel zeggen dat dit wel een van de meest lompe dingen is die ik dan in een programmeertaal heb gezien.

Sorry dat dit precies hetzelfde algoritme is als in de eerste reply, had dit algoritme niet goed genoeg bekeken . Maar heb gewoon het "schoolvoorbeeld" voor zo'n algoritme opgeschreven.

[Paul]

M_de_Hilg schreef op 15 september 2002 @ 22:00:
Sorry dat dit precies hetzelfde algoritme is als in de eerste reply, had dit algoritme niet goed genoeg bekeken . Maar heb gewoon het "schoolvoorbeeld" voor zo'n algoritme opgeschreven.

Ik ook Voordeel is wel, dat we hem nu al in 2 talen hebben

@ Alarmnummer: Daar staat helaas geen Delphi -> C++ of zo tussen. Engels -> Spaans wordt mijn scriptje

code:

huiswerk(tekst de la función: secuencia): secuencia; 
spatie_gehad del var: boleano; 
comience 
  resultado: = ' ';
  spatie_gehad: = falso;
  tekst: = trim(tekst);
  para el índice: = 1 al length(tekst) 
    comienza 
      si (el tekst[index ] = ' ') entonces 
        comience 
          si no el spatie_gehad después 
            comience 
              el resultado: = resultado + tekst[index ];
              spatie_gehad: = verdad; 
            extremo; 
        extremo; 
        comience 
            resultado: = resultado + tekst[index ];
            spatie_gehad: = falso; 
        extremo; 
    extremo; 
extremo;

Maar ik betwijfel of dat compileert en babelfish struikelt over de else

offtopic:
De link op je site naar Javahova werkt niet, je mist .com Verder is dat forum verhuist, dus je link klopte zowiezo niet (meer)

[Alarmnummer]

Ik denk dat babelfish ook nog wel een aantal extra talen op kan leveren

[TheLunatic]

excuseer mij, maar het kan ook gewoon met:

code:

while Pos('  ', Str)>0 do Delete(Str, Pos('  ', Str), 1);
Str:=Trim(Str);

Delphi dus he

[Janoz]

Alarmnummer schreef op 15 september 2002 @ 13:38:
[...]


Leuke routine, alleen die trim op het einde is minder geslaagd. Onderhuids gaat deze nog een keer de string bijlangs.

spaties aan de voorkant zijn weg te halen door lastchar te initialiseren op " " ipv "" en de laatste spaties is vast ook nog wel weg te halen (waneer lastchar = " " en length > 1 dan laatste teken eraf) .. Dan heb je nog wel een beetje leuke oplossing

[Janoz]

TheLunatic schreef op 16 september 2002 @ 10:52:
excuseer mij, maar het kan ook gewoon met:

code:

while Pos('  ', Str)>0 do Delete(Str, Pos('  ', Str), 1);
Str:=Trim(Str);

Delphi dus he

En deze is dus weer langzamer dan O(n). Een heel stuk zelfs..

[Janoz]

JeroenHollemans schreef op 15 september 2002 @ 11:44:
.....
Maar ik zie iig al leuke resultaten. Opvallend is wel dat er een hoop "oplossingen" worden
gegeven die niet blijken te werkten.
Zegt dat iets over de programmeur ? de tester ? de analyst ? de opdrachtgever ?
Waar zou zoiets nou aan kunnen liggen ?
...

Wat me daarnaast opviel was dat dat vooral de oplossingen waren die gebruik maakten van standaard functies

[Janoz]

JeroenHollemans schreef op 15 September 2002 @ 00:04:
Nee nee, dat is het echt niet. Het gaat over verschillende methoden.
Ik heb nu al een functionele oplossing gezien (trim leading en trailing spaces en de rest in een lusje)
een recursieve (mijn eigen) en dan die met pointers.

* Janoz dacht niet eens aan pointers (in eerste instantie), dus vandaar dat ik het zo interressant vond.

En dat van java met een for-lusje is ook alleen maar een voorbeeldje...
[/edit]

offtopic:
(zo, ben wel ff druk deze draad aan het doorwerken zeg )

hmm .. Ik dacht dat je juist was geintreseerd in algoritmen, niet in de werkelijke implementaties hiervan .. De 'pointer oplossing' ziet er mischien wel anders uit dan de 'lus oplossing', maar in weze is het algoritme zo goed als gelijk.

Als je trouwens echt verschillende oplossingen wilt zien zul je een iets ander probleem moeten verzinnen .. Je hebt in dit geval eigenlijk maar 1 goed algoritme, en dat is een O(N) doorloop algoritme dat alleen de juiste tekens overlaat. Je zult alleen verschil zien in de verschillende manieren van implementatie, maar het ID zal telkens op hetzelfde neerkomen.

[Alarmnummer]

Ik doe dan ook even een poging met een DFA:

code:

String singleSpace(String source){
    StringBuffer sb = new StringBuffer();
    State state = State.BEGIN;
    int index = 0;
    do{ 
        if(index == source.size()){
            state = State.FINISHED; 
        }else{
            char c = source.charAt(index);      
            index++;
            if(state == State.BEGIN){
                if(c != ' '){
                    state = State.NON_SPACE;
                    sb.append(c);
                }
            }else if(state == State.NON_SPACE){
                if(c!= ' '){
                    sb.append(c);
                }else{
                    state = State.SPACE;
                }
            }else if(state == State.SPACE){
                if(c!=' '){
                    state = State.NON_SPACE;
                    sb.append(' ');
                    sb.append(c);
                }
            }   
        }
    }while(state!=State.FINISHED);
    return sb.toString();
}

class State{
    public final static State BEGIN = new State();
    public final static State SPACE = new State();
    public final static State NON_SPACE = new State();
    public final static State FINISHED = new State();

    private State(){}
}

Heeft ook een complexiteit van O(n)

[edit]
Hij is niet helemaal netjes omdat je dus aan het einde ten onrechte in een State.SPACE of State.NON_SPACE terecht kan komen ipv een State.FINISHED.

[ Voor 0% gewijzigd door Alarmnummer op 16-09-2002 12:18 . Reden: == ipv = :z ]

[kvdveer]

Soultaker schreef op 15 september 2002 @ 16:01:
[...]
Ziet er wel correct uit. Creatief gedaan; lekker compact enzo. Je houdt er wel een vreemde calling convention op na trouwens (Pascal ofzo?) En waarom maak je eigenlijk ECX leeg? Dat is toch nergens voor nodig?

Ik denk trouwens dat die spatie sectie wel wat efficienter te krijgen is met een 'rep cmpb', al moet je dan je registers wat anders kiezen.

Verder erg mooie code, hoor...

Ecx hoeft idd niet per se leeg gemaakt te worden, maar het is wel netter.
Van die calling convention klopt geen donder. De eerste POP geeft namelijk het return-adres, die hoor ik daarna terug te gooien.
Ik heb Assembler geleerd van een brakke tutorial, en dit is eigenlijk het eerste van enig nut wat ik heb geschreven. (dat is niet helemaal waar. Ik heb ooit in assembler een proggie KAT geschreven. een variant op cat, die doorpompt van stdin naar stdout. Een soort van piping verlengstuk dus... ;-) )
Wat doet "rep cmpb" exact? Die registerindeling is ook maar willekeurig. Er zal wel een conventie zijn, maar die ken ik niet.

[mbravenboer]

Alarmnummer: Ik doe dan ook even een poging met een DFA:

Ik kon het niet laten: hier een implementatie in Stratego met duidelijke herschrijf-regels voor de transities en het gebruik van een yummie fold . Elke 'move' regel is een transitie in het automaat. De voorwaarden staan bij de regels. Stratego kent geen chars en daarom werk ik op een lijst van integers.

code:

signature
  constructors
    Begin:    State
    Space:    State
    NonSpace: State
    End:      State
    _
overlays
    space = 32
    _
strategies
  _
  main =
      !"   Dit    is een  implementatie   in een   echte taal  "
    ; explode-string
    ; foldr(!(<id>, End()), move)
    ; debug(!"Result ")
    ; ?(<implode-string>, _)
  _
  /* End */
  move: (space, ([], End())) -> ([] , End())
  move: (c    , ([], End())) -> ([c], NonSpace())
      where <not-space> c
  _
  /* NonSpace */
  move: (space, (cs, NonSpace())) -> (cs, Space())
  move: (c    , (cs, NonSpace())) -> ([c | cs], NonSpace())
    where <not-space> c
  _
  /* Space */
  move: (space, (cs, Space())) -> (cs, Space())
  move: (c    , (cs, Space())) -> ([c | [32 | cs]], NonSpace())
    where <not-space> c
  _
  not-space = not(?space)

[ Voor 0% gewijzigd door mbravenboer op 16-09-2002 12:43 . Reden: ff een _ gezet waar een newline hoort. Pokke newlines verwijdering in die code tag :( ]

[Alarmnummer]

Handig dat je in stratego met patronen kan werken. (Zou eigelijk in iedere zichzelf respecterende taal moeten zitten ) Ziet er verder wel gaaf uit.

[mbravenboer]

Het is trouwens een eitje om dit te porten naar Haskell: het is volledig functioneel.

[Soultaker]

Leuk dat Alarmnummer en mbravenboer eraan denken om dit met een state machine op te lossen. Zelf heb ik ook even kort over een functionele oplossing nagedacht en toen dacht ik eigenlijk direct aan een enkele functie die met behulp van pattern matching onderscheid maakt tussen enkele en dubbele spaties, maar dat is nodeloos inefficient, aangezien dan elke letter twee keer bekeken moet worden (pattern matching is niet gratis). Daarbij is deze methode wat leesbaarder, denk ik.

[Alarmnummer]

Soms is de meest efficiente manier niet de leukste, en de computer staat in dienst van ons en niet andersom. Dus fuck efficientie welkom leuke manieren

[Soultaker]

Alarmnummer schreef op 16 september 2002 @ 13:06:
Soms is de meest efficiente manier niet de leukste, en de computer staat in dienst van ons en niet andersom. Dus fuck efficientie welkom leuke manieren

Ik vind het zelf altijd leuk om de meest efficiente manier (op algoritmisch nivo dan) te bedenken. Als ik een algoritme ontwerp waarvan ik het vermoeden heb dat 'ie beter kan, ben ik niet tevreden.

Zo wordt de functionele variant, naar aanleiding van Alarmnummer's idee en mbravenboer's uitwerking:

code:

::State  = Begin | Space | NonSpace
_
move :: State Char -> (State, [Char])
move Begin ' ' = (Begin,    [])
move _     ' ' = (Space,    [])
move Space chr = (NonSpace, [' ',chr])
move _     chr = (NonSpace, [chr])
_
foldable_move :: (State, [Char]) Char -> (State, [Char])
foldable_move (state, output) input
    = (next_state, output ++ next_output)
    where (next_state, next_output) = move state input
_           
Start = snd (foldl foldable_move (Begin,[]) ['   dit    is een  test  '])

Een unieke eind-staat is hier vrij overbodig aangezien ik ook geen eind-van-de-string symbool gebruik. Voor de duidelijkheid heb ik de type-definities er maar bij gezet, al had foldable_move ook wel als lambda-expressie geschreven kunnen worden.

Sinds wanneer worden de newlines trouwens uit code gesloopt? Dat werkte voorheen toch goed?

[Alarmnummer]

Soultaker schreef op 16 september 2002 @ 13:21:
[...]


Ik vind het zelf altijd leuk om de meest efficiente manier (op algoritmisch nivo dan) te bedenken. Als ik een algoritme ontwerp waarvan ik het vermoeden heb dat 'ie beter kan, ben ik niet tevreden.

Het ligt er een beetje aan vanuit welk oogpunt je iets benaderd. Ik probeer van alles uit en als het echt een frequent aangeroepen stukje code gaat worden dan maak ik er wel iets snels van. Maar verder maak ik me niet meer zo druk om snelheid.

Zo wordt de functionele variant, naar aanleiding van Alarmnummer's idee en mbravenboer's uitwerking:
...

Ziet er leuk uit. En verder zou ik eigelijk geen andere manieren meer weten. Eventueel zou je er nog een kunnen maken met een quantum computer + en dan alle combinaties uitproberen samen met een succes conditie (zoals je zelf in een ander topic vermelde). Trouwens een quantum computer is niet eens nodig omdat het resultaat altijd qua lengte kleiner of gelijk is aan de source en daardoor is het aantal combinaties eindig.

[mbravenboer]

Ah, dat was inderdaad wat ik in mijn hoofd had voor een functioneel taal .

Waarom begin je bij het begin? . Het onderscheid tussen de move en de foldable_move is aardig!

[Soultaker]

mbravenboer schreef op 16 september 2002 @ 13:32:Waarom begin je bij het begin? .

Het idee was dat dat makkelijker te begrijpen was, al is het principe natuurlijk precies hetzelfde. Bovendien gebruik ik liever foldl dan foldr, omdat foldl tail recursive is en foldr niet.

Helaas is mijn foldable_move nu wel heel inefficient, aangezien ik elke keer een lijst van 0 tot 2 karakters achter een 'hele lange' lijst plak. Dat kan natuurlijk ook nog beter; alle uitvoer achterstevoren genereren en op 't eind omkeren bijvoorbeeld. Het nadeel is dan wel weer dat de hele string bij de constructie in het geheugen bewaard moet worden en het resultaaat pas bruikbaar is aan het einde van de hele procedure. Nu kan het resultaat van de operatie al gebruikt worden voordat de operatie afgelopen is, wat ik altijd wel een aardige eigenschap van functionele programma's vind.

Als ik bijvoorbeeld alleen de eerste 10 karakters van de geformatteerde uitvoer wil, kan ik gewoon "take 10 ..." toepassen en dan worden ook inderdaad alleen de eerste 10 karakters berekend. Als ik op 't eind zou beginnen zou ik altijd alle karakters moeten verwerken, ook als ik er maar 10 nodig heb.

edit:
Het verhaal wat ik hier houdt, klopt niet in combinatie met het gebruik van foldl.
Pas op bij de afsluitende recursiestap wordt een resultaat opgeleverd dus zal foldl wel de hele string doorlopen. foldable_move zal echter niet vaker dan nodig aangeroepen worden. Om ook het aanroepen van foldl te beperken (en dus het verwerken van 'oneindig' grote invoer mogelijk te maken) zouden foldl en foldable_move in één functie geimplementeert moeten worden, zodat de gegevens die foldable_move nu in 'output' opslaat direct als resultaat worden opgeleverd.

[mbravenboer]

Idd, ik snap de redenatie. Ik vind foldr altijd een stuk prettiger gezien de aard van lijsten ...

Hier is er nog eentje in Haskell, die exact dezelfde opzet heeft als de Stratego versie.

code:

  _
  data State = End
             | Space
             | NonSpace
  _
  start :: String -> String
  start = fst . foldr move ("", End)
  _
  move :: Char -> (String, State) -> (String, State)
  _
  move ' ' ("", End) = ("", End)
  move c   ("", End) = ([c], NonSpace)
  _
  move ' ' (cs, NonSpace) = (cs, Space)
  move c   (cs, NonSpace) = (c : cs, NonSpace)
  _
  move ' ' (cs, Space) = (cs, Space)
  move c   (cs, Space) = (c : ' ' : cs, NonSpace)

[mbravenboer]

Soultaker: Het verhaal wat ik hier houdt, klopt niet in combinatie met het gebruik van foldl.

Het punt waar het mij met name om gaat is de ++. Die is nogal duur tov de : die ik gebruik in de foldr variant ...

[Soultaker]

mbravenboer schreef op 16 september 2002 @ 13:50:
Het punt waar het mij met name om gaat is de ++. Die is nogal duur tov de : die ik gebruik in de foldr variant ...

Klopt, vandaar het omgekeerd-invoeren-verhaal, maar dat is dus weer onbevredigend omdat je dan bij het einde moet beginnen, zelfs als je alleen maar de eerste paar karakters nodig hebt.

De volgende variant lost alle bovengenoemde problemen op:

code:

folder :: State [Char] -> [Char]
folder _ [] = []
folder state [input:rest]
    = output ++ (folder next_state rest)
    where (next_state, output) = (move state input)
_
Start = folder begin ['   dit    is een  test ']

Er wordt een constante hoeveelheid geheugen gebruikt, folder is tail recursive, werkt veilig op oneindige invoer en de executietijd is relatief aan de lengte van de invoer.

[mbravenboer]

Hum.... Ik volg dit even niet: je doet toch nog steeds een ++ ? Het lijkt mij dat die alleen te omzeilen is als je bij het einde begint?

[mbravenboer]

We dwalen trouwens wel een beetje af van de taal die in de topic-titel werd gesuggereerd .

[Verwijderd]

Recursief?? Wat dacht je van:

code:

  strUitkomst = strInput
  Do Until Instr(strUitkomst,"  ") = 0
    strUitkomst = Trim$(Replace(strUitkomst,"  "," "))
  Loop

[Soultaker]

schreef op 16 september 2002 @ 14:02[/message]:[/b]
Hum.... Ik volg dit even niet: je doet toch nog steeds een ++ ? Het lijkt mij dat die alleen te omzeilen is als je bij het einde begint?[/quote]

In Clean (en ik neem aan ook in Haskell) is de ++ operator zo gedefinieerd:

code:

(++) infixr 5::![.a] u:[.a] -> u:[.a]
(++) [hd:tl]  list = [hd:tl ++ list]
(++) nil      list = list

Never mind de vreemde syntax; dat zijn wat optimalisatiedingen. Wat belangrijk is, is dat alleen het eerste argument strict geëvalueerd wordt. Wanneer het eerste argument leeg is, wordt gewoon het tweede argument opgeleverd. (Wat 'nil' hier doet ipv [] weet ik trouwens ook niet).

De complexiteit van ++ is dus O(N), met N de lengte van het eerste argument. De lengte van het tweede argument doet er niet toe. Aangezien ik in mijn code als eerste argument het resultaat van move gebruik, dat maximaal 2 karakters lang is, maakt het gebruik van ++ dus niet uit. [a,b]++[xxx] is immers hetzelfde als [a:[b:[xxx]]] (en wordt zo ook geëvalueerd, trouwens).

edit:
In Clean zijn lijsten geimplementeert als single linked lists; vandaar dat 't duidelijk is dat [x:lijst] 'goedkoop' is.

[Soultaker]

mbravenboer schreef op 16 september 2002 @ 14:06:
We dwalen trouwens wel een beetje af van de taal die in de topic-titel werd gesuggereerd .

De topic starter wilde graag verschillende mogelijke algoritmes zien; dat is wel gelukt, geloof ik.

[.oisyn]

Soultaker schreef op 16 september 2002 @ 14:08:
[...]


De topic starter wilde graag verschillende mogelijke algoritmes zien; dat is wel gelukt, geloof ik.

nu krijgt ie vast een hoog cijfer voor z'n huiswerk
_{sorry ik kon het niet laten}

[mbravenboer]

Ah ik begrijp je verhaal ja. Het is dus een beetje kortzichtig om een ++ maar gelijk te veroordelen . Ik heb beide implementaties nog even getest in Hugs (Haskell dus) en ze komen inderdaad uit op precies hetzelfde aantal reducties en cellen .

Code van de test"

code:

  _
  data State = Begin
             | End
             | Space
             | NonSpace
  _
  move :: State -> Char -> (State, [Char])
  _
  move Begin ' ' = (Begin,    [])
  move _     ' ' = (Space,    [])
  move Space chr = (NonSpace, [' ',chr])
  move _     chr = (NonSpace, [chr])
  _
  folder :: State -> String -> String
  _
  folder _ [] = []
  folder state (input:rest) = output ++ (folder next_state rest)
                   where (next_state, output) = (move state input)
  _
  start_soultaker = folder Begin test_string
  _
  start_martin :: String
  start_martin = (fst . foldr move2 ("", End)) test_string
  _
  move2 :: Char -> (String, State) -> (String, State)
  _
  move2 ' ' ("", End) = ("", End)
  move2 c   ("", End) = ([c], NonSpace)
  _
  move2 ' ' (cs, NonSpace) = (cs, Space)
  move2 c   (cs, NonSpace) = (c : cs, NonSpace)
  _
  move2 ' ' (cs, Space) = (cs, Space)
  move2 c   (cs, Space) = (c : ' ' : cs, NonSpace)
  _
  test_string = "    dit    is    de string     voor deze test   "

[mbravenboer]

.oisyn: nu krijgt ie vast een hoog cijfer voor z'n huiswerk

Zou je een hoog cijfer krijgen als je het ego van de docent beschadigt door met Haskell en Stratego code aan te komen zetten? .

[mbravenboer]

Hum, er komt toch niet hetzelfde uit . Ik moet weer eens wat meer met Haskell doen, want het is allemaal wel wat lang geleden .

Er kwam hetzelfde uit omdat de test_string gelijk in de start methode al wordt gebruikt. Als je hem zelf meegeeft als parameter bij het draaien van de test komen er toch andere resultaten uit:

code:

foldr en :  -> (672 reductions, 948 cells)
foldl en ++ -> (844 reductions, 1469 cells)

(beide zijn stabiele getallen)

Met name het verschil in aantal cellen is wel behoorlijk. Uiteraard kan het zijn dat de getallen in Clean anders liggen, maar de definitie ++ is hetzelfde als in de Haskell Prelude.

[Soultaker]

mbravenboer schreef op 16 september 2002 @ 14:56:
Met name het verschil in aantal cellen is wel behoorlijk. Uiteraard kan het zijn dat de getallen in Clean anders liggen, maar de definitie ++ is hetzelfde als in de Haskell Prelude.

Ik denk dat 't verschil 'm er in zit, dat jij je concatenatie 'inlined' in je move functie (waardoor je dus al weet of je 0, 1 of 2 keer ':' moet gebruiken).

[Soultaker]

Ik heb de Clean profiling tools niet zo onder de knie, maar als ik even snel test met een half miljoen a's als invoer, dan is mijn algoritme drie keer zo snel en gebruikt maar een paar k geheugen, waar ik jou algortime enkele tientallen megabytes moet geven.

Ik hoef hier trouwens geen 'mijn algoritme is beter!' topic van te maken, maar ik vind het altijd wel leuk om te zien dat het maken van een 'goed' algoritme ook een beter resultaat oplevert, al zal de gecompileerde code wat groter zijn.

[mbravenboer]

Mwah, het is gewoon leuk om te zien welke aanpak beter is. Dat heeft niet zoveel met goed-slecht te maken ....

Opvallend dat er zulke grote verschillen zijn, ten eerste tussen de executie in Haskell en Clean, maar met name ook omdat de methode die ik hier toepas (foldr dus) algemeen wel als een methode wordt gezien die zuinig omgaat met geheugen en snelle uitvoer oplevert. Het enorme verschil wat jij noemt (kbs versus tientallen mbs) vind ik daarom wel erg opvallend. Ik zuig de resultaten hier natuurlijk ook niet uit mijn duim . Ik heb wel een interpreter gebruikt, misschien dat normale compilatie met ghc hele andere resultaten op zou leveren.

Kan het zijn dat de Clean library hele specifieke tweaks bevat die jouw implementatie hier veel beter laten functioneren?

[Alarmnummer]

En dan ook nog even een Nice versie:

l is een globaal gedeclareerde List van Chars. Ik kon deze info helaas niet meenemen als parameter in een tupel want Nice wil daar niet over dispatchen. (Ik had dus liever een tupe gemaakt van State en List<Char> ipv alleen State) Ik zou hiervoor de foldright functie wel voor kunnen aanpassen, maar dat is ook maar weer een beetje flauw

code:

String singleSpace(String  source){
    foldright(move,new BeginState(),toCharList(source));    
    return charListToString(l);
}

interface State{}

class BeginState implements State{}

class SpaceState implements State{}

class NonSpaceState implements State{}

State move(Char c,State state);

move(c,state@BeginState){
    if(c.getValue() != ' '){
        l.add(0,c);
        state = new NonSpaceState();
    }
    return state;
}

move(c,state@SpaceState){
    if(c.getValue()!=' '){
        l.add(0,' ');
        l.add(0,c);
        state = new NonSpaceState();
    }
    return state;
}

move(c,state@NonSpaceState){
    if(c.getValue()!=' '){
        l.add(0,c);
    }else{
        state = new SpaceState();
    }
    return state;
}

grrrr... moet je natuurlijk wel de goeie code copy pasten...
en de interfaces niet vergeten.
en niet per ongeluk de string reversen