www.jammni.de

Gepostet:
13.05.2013 00:45

Laziness, Memory Problem

Hallo,

folgendes Programm soll eine Liste vom Bäumen entgegennehmen und diese in Int-Bäume umwandeln.
Bäume die umgewandelt werden sollen, werden analysiert, den z.B. auftretenden Char-Zeichen wird eindeutig ein Int zugewiesen und damit werden alle Bäume transformiert.

Bsp:
[Node 'a' [Node 'b' []] ,Node 'a' []] -- > [Node 1 [Node 2 []],Node 1 []]


tree = Node 'a' []
trees = map (_ -> tree) [1..]

intify :: Ord a => [Tree a] -> [Tree Int]
intify trees = 
  let s  = concatMap (concat . levels) trees
      is = zip s [0..]  
      intifiedTrees = map (fmap (convert is)) trees
  in  intifiedTrees
    where convert :: Ord a => [(a,Int)] -> a -> Int
          convert is a =
            case lookup a is of
              Just s -> s
              _      -> error ""

Mein Problem:
- für (intifiy trees) !! 100000 wird viel mehr maximaler Speicher verbraucht als für (intifiy trees) !! 0 - weshalb?
- Ich dachte, dass aufgrund der Laziness einmal die 99999 ersten Bäume nicht transfomiert werdne, da sie nicht gebraucht werden, und zumanderen beim Durchgehen der Liste die nicht gebrauchten Elemente (Bäume) direkt verworfen werden und sich nur gemerkt wird, an welcher Stelle der Liste ist; d.h. für diese wird kein Speicher gebraucht. Deswegen habe ich eigentlich mit gleichem Speicherverbrauch gerechnet.
- Ähnlich wie zu [1..] !! 100000 und [1..] !! 0 - hier ist es ja so.
Wo liegt mein Verständnisfehler bzw. was ist noch nicht richtig?

Zum Seitenanfang

Landei

Gepostet:
13.05.2013 12:49

Keine Ahnung woher das kommt, aber ich würde das Problem anders angehen: Ich würde versuchen, innerhalb von intify eine Map und den nächsten freien Index in eine State-Monade zu packen und damit den aktuellen Index zu ermitteln (und gegebenenfalls zu updaten). Ich habe gerade keine Zeit, da bräuchte ich sicher länger zum Tüfteln.

Zum Seitenanfang

IKT

Gepostet:
13.05.2013 13:04

Danke für deine schnelle Anregung, eventuell werde ich das später noch probieren. Wenn ich herausfinde, weshalb mehr Speicher verbraucht werde ich es auch noch schreiben - eigentlich schade, wenn es nicht geht, es wäre doch schön wenn es ginge die Laziness so zu nutzen.

Zum Seitenanfang

Haskell-Forum