[VB] Meerdere spaties omzetten naar 1 *

[Soultaker]

mbravenboer schreef op 16 september 2002 @ 15:21:
Mwah, het is gewoon leuk om te zien welke aanpak beter is. Dat heeft niet zoveel met goed-slecht te maken ....

Nee, dat vind ik ook, maar toevallig zeg ik elke keer dat ik m'n eigen versie beter vind; dat zou verkeerd over kunnen komen.

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.

Zoals ik al eerder zei, is foldl tail recursive in tegenstelling tot foldr. Daarom gebruikt foldr normaal gesproken een hoeveelheid geheugen relatief aan de lengte van de lijst waarop 'ie werkt en foldl constant geheugen. Ik weet niet hoe foldl en foldr in Haskell gedefineerd zijn, maar in Clean gaat het zo:

code:

foldl op r l :== foldl r l
    where
        foldl r []      = r
        foldl r [a:x]   = foldl (op r a) x
_
foldr op r l :== foldr l
    where
        foldr []    = r
        foldr [a:x] = op a (foldr x)

Door de ':==' zijn het macro's, zodat de compiler ze zal inlinen. Hier is wel goed te zien dat foldr eerst de hele gereduceerde expressie moet uitvinden, voordat 'op' voor de eerste keer toegepast kan worden. Het resultaat is dat voor (bijvoorbeeld) 'foldr (+) 0 [1,2,3,4,5]' eerst naar '0 + (1 + (2 + (3 + (4 + (5) ) ) )' uitgewerkt moet worden, waarna die expressie wordt uitgevoerd.

Stapsgewijs ziet dat er zo uit:

code:

1. foldr 0 [1,2,3,4,5]
2. 1 + (foldr 0 [2,3,4,5])
3. 1 + (2 + (foldr 0 [3,4,5]))
4. 1 + (2 + (3 + (foldr 0 [4,5]))
5. 1 + (2 + (3 + (4 + (foldr 0 [5])))
6. 1 + (2 + (3 + (4 + (foldr 0 [5]))))
7. 1 + (2 + (3 + (4 + (5+ 0)))))
8. 1 + (2 + (3 + (4 + 5))))
9. 1 + (2 + (3 + 9))
10. 1 + (2 + (12))
11. 1 + (14)
12. 15

Duidelijk is dat bij stap 7 alle tussenresultaten in het geheugen staan.

foldl voert eerst de operator uit en dan pas de recursiestap, die direct de huidige functieaanroep kan vervangen (dat heet dus tail recursive). Het resultaat is dat de evaluatie van 'foldl (+) 0 [1,2,3,4,5]' als volgt gaat:

code:

1. foldl 0 [1,2,3,4,5]
2. foldl (0+1) [2,3,4,5]
3. foldl 1 [2,3,4,5]
4. foldl (1+2) [3,4,5]
5. foldl 3 [3,4,5]
6. foldl (3+3) [4,5]
7. foldl 6 [4,5]
8. foldl (6+4) [5]
9. foldl 10 [5]
10. foldl (10+5) []
11. fold 15 []
12. 15

Vergeef me als ik haakjes ben vergeten of tussenstappen heb gemist, ik vind het voorbeeld zo wel lang genoeg. Ik denk dat zo wel duidelijk is dat foldr op deze manier niet echt praktisch is. Het zou kunnen dat Haskell foldr anders gedefinieerd heeft (en echt aan 't einde van de lijst begint) maar dat zou ik niet durven zeggen.

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

Vanuit de implemenatie van de standaard library verbaast het me niets dat foldr minder efficient werkt. Het aantal reductiestappen is wel gelijk, maar doordat veel meer geheugen wordt gebruikt, valt het voordeel van caching e.d. weg. Ook het alloceren van zo veel geheugen kost natuurlijk tijd (het garbage collecten heb ik niet meegeteld).

[Alarmnummer]

In nice is hij als volgt gedeclareerd:

code:

<Any A, Any B> B foldRight((A, B)->B func, B start, Sequence<A> seq) {
  B result = start;
  for(int i = size(seq) - 1; i >= 0; i--) {
    result = func(seq[i], start);
  }
  return result;
}

[Soultaker]

Alarmnummer schreef op 16 september 2002 @ 15:47:
In nice is hij als volgt gedeclareerd:

Maar dan zit je ook goed genaait als je Sequence een single linked list is, aangezien je dan elke keer helemaal naar 't eind moet. De elende in gebruik van ruimte heb je dan in gebruik van tijd.

Als je een Sequence gebruikt waarin je wel efficient van achter naar voor kunt indexeren, is deze oplossing natuurlijk ideaal.

edit:
Erm.... Klopt dit wel:

code:

    result = func(seq[i], start);

Moet dat niet func(seq[i], result) zijn?

[Alarmnummer]

Ach ja.. je kunt niet alles hebben. Maar ik ben al heel blij dat ik een aantal features die je eigelijk alleen ziet in functionele talen ook kan gebruiken in een imperatieve taal. Binnenkort komt er geloof ik ook betere ondersteuning voor patronen ed dus we moeten maar even zien wat dat allemaal gaat bieden. Als je vanuit de functionele hoek hierna kijkt dan ga je een stapje achteruit, maar vanuit de imperatieve hoek is Nice wel een paar honderd stappen vooruit.. Hmmzz.. zet je toch aan het denken over de imperatieve hoek

[mbravenboer]

Soultaker: Nee, dat vind ik ook, maar toevallig zeg ik elke keer dat ik m'n eigen versie beter vind; dat zou verkeerd over kunnen komen.

Nee hoor, maak je maar geen zorgen .

Zoals ik al eerder zei, is foldl tail recursive in tegenstelling tot foldr.

Het voordeel van tail-recursion was me bekend, maar ik had er in deze context niet bij nagedacht dat de gevolgen zo enorm zouden zijn. Je verhaal is helemaal duidelijk . Ik ben voortaan gewaarschuwd.

Ik vond nog dit linkje:
http://www.cs.mu.oz.au/~lee/papers/hose2/naish/node12.html

Wel jammer op zich dat dit probleem zich voor doet. Ik vind de foldr zelf namelijk een stukje duidelijk, maar dat kan ook komen doordat ik hem meer gewend ben .

[GraasGast]

marcusk schreef op 15 september 2002 @ 00:33:
aangezien er nog geen werkende regex oplossing gegeven is:

PHP:

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

als je +'s maakt van die twee *'s is hij 20% sneller

en als je alle spaties vervangt door \s werkt hij met alle witruimte, dus ook met tabs enzo

de snelste methode in php is deze, maar dan is het niet meer 1 regex:

PHP:

preg_replace("/\s{2,}/", " ", trim($str));

65% sneller

[Soultaker]

Wie zij ook alweer dat dit een oninteressant algoritme was? We zijn er nu al ruim 100 berichten mee bezig.

[Alarmnummer]

Hmmzz... iets zegt me dat we te veel vrije tijd hebben

[Soultaker]

Alarmnummer schreef op 16 september 2002 @ 16:23:
Hmmzz... iets zegt me dat we te veel vrije tijd hebben

Valt mee; ik ben gewoon aan 't werk (al gaat m'n efficientie wel omlaag zo).

[GraasGast]

ghehe, same here

('k heb al die dingen lopen benchmarken )

[mbravenboer]

Hier is nog een Foldr in Java (met voorbeeld! ). Ik had toendertijd geen zin om Foldr een echte functie te maken kennelijk .

code:

package org.mbravenboer.collection;
_
import org.mbravenboer.function.Function;
import java.util.ArrayList;
import java.util.ListIterator;
import java.util.List;
_
public class Foldr {
_
  public static <A, R, E extends A> R foldr(Function<A,Function<R,R>> op, R end, List<E> list) {

    ListIterator<E> iterator = list.listIterator(list.size());
    R result = end;
_
    while(iterator.hasPrevious()) {
      result = op.apply(iterator.previous()).apply(result);
    }
_
    return result;
  }
_
  public static void main(String[] ps) {
    List<Integer> list = new ArrayList<Integer>();
    list.add(new Integer(3));
    list.add(new Integer(2));
    list.add(new Integer(4));
_
    System.out.println("Result: " + Foldr.foldr(new Plus(), new Integer(0), list));
  }
_
  public static class Plus implements Function<Integer, Function<Integer, Integer>> {
_
    public Function<Integer, Integer> apply(final Integer val1) {
      return new Function<Integer, Integer>() {
        public Integer apply(Integer val2) {
            return new Integer(val1.intValue() + val2.intValue());
        }
      };
    }
  }
}

[ Voor 0% gewijzigd door mbravenboer op 16-09-2002 16:44 . Reden: fuck wat zijn die newlines irritant :( ]

[mbravenboer]

Soultaker: Wie zij ook alweer dat dit een oninteressant algoritme was? We zijn er nu al ruim 100 berichten mee bezig.

Laten we het dus maar niet over interessante algoritmen gaan hebben .

Ik moet nog het stronlgy-connected components algoritme implementeren in Stratego, dus als iemand zich geroepen voelt in Haskell of Clean .

[Alarmnummer]

Wat vreemd trouwens dat jullie underscores moeten plaatsen, ik heb er geen last van.

[Soultaker]

Alarmnummer schreef op 16 september 2002 @ 16:55:
Wat vreemd trouwens dat jullie underscores moeten plaatsen, ik heb er geen last van.

Ik heb het even getest en in Mozilla 1.1 gaat 't fout, in Microsoft Internet Explorer 6.0 gaat 't goed. Ik plaats wel even een bug-report...