www.jammni.de

Logo - Kleiner Drache
Login
Username:

Passwort:

Daten merken
Auto-Login
Registrieren
 
Online
niemand
 
Forumsuche
Suche nach:

Logo - DracheHaskell-Forum

Skrodde

Gepostet:
06.08.2011 23:34

GHCi \"out of memory\" - Programm entschlacken oder Auslagerungsdatei nutzen?  
Hallo zusammen,
im Rahmen meiner Bachelorarbeit habe ich ein Haskell-Programm geschrieben, welches alle möglichen Zustände berechnet, in den sich das Mühle-Brett befindet, nachdem alle neun weißen und neun schwarzen Steine gesetzt wurden. Der Inhalt des Programms sei nun weniger wichtig, ich habe vor allem das Problem, dass bei der Ausführung der Arbeitsspeicher meines Laptops (4GB) voll ist. Allerdings scheint der Haskell Interpreter auch nur 1,6 GB zu nutzen und dann mit der Meldung \"out of memory\" zu terminieren. Zumindest arbeitet ab da die CPU nicht mehr für den Prozess. hat nun jemand eine Idee, wie ich den Interpreter (GHCi) dazu bewegen kann, die Auslagerungsdatei auf der Festplatte mit zu nutzen?
Ich hänge mal das Programm hier an, dann könnt ihr das Problem nachvollziehen (für Verbesserungsvorschläge bin ich dankbar):

-- Haskell-Program for calculation of all possible states after setting of stones

-- possible occupations for the positions
data Stone = E | W | B deriving (Show,Eq)

-- positions on the Nine Men\'s Morris Board
type Position = (Int,Int,Int)
-- a whole Nine Men\'s Morris Board
type Board = [(Position, Stone)]
-- a whole State of Nine Men\'s Morris including a board and the last position W placed a stone on and the last position B placed a stone on
type State = (Board,(Position,Position))
-- the set of states that is operated on
type States = [State]

-- possible coordinates for the positions
coordinates = [0,1,2]
-- the set of positions that a Nine Men\'s Morris board consists of
positions = [(r,x,y) | r <- coordinates,x <- coordinates,y <- coordinates, (x,y) /= (1,1)]

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
-- The Main Programm

-- compute all states that occur after setting of stones
computeStates :: States
computeStates = rekComputeStates 0 initState

-- compute recursively all States with 9 Stones being set by each player
rekComputeStates :: Int -> States -> States
rekComputeStates 9 a = a
rekComputeStates n a = rekComputeStates (n+1) (removeDuplicates (concat (map checkMillBTakeW (concat (map setBStone (concat (map checkMillWTakeB (concat (map setWStone a)))))))))

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
-- The atomic formulas

occupiedW :: Position -> State -> Bool
occupiedW (r,x,y) s = if elem ((r,x,y),W) (fst s) then True else False

occupiedB :: Position -> State -> Bool
occupiedB (r,x,y) s = if elem ((r,x,y),B) (fst s) then True else False

playedW :: Position -> State -> Bool
playedW (r,x,y) s = if (r,x,y) == fst(snd(s)) then True else False

playedB :: Position -> State -> Bool
playedB (r,x,y) s = if (r,x,y) == snd(snd(s)) then True else False

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
-- The more complex formulas
millClosedW :: State -> Bool
millClosedW s = or [ and [occupiedW (i,j,k) s | k<-[0,1,2]] && or [playedW (i,j,k) s| k<-[0,1,2]] | i<-[0,1,2], j<-[0,1,2]] || or [ and [occupiedW (k,1,j) s | k<-[0,1,2]] && or [playedW (k,1,j) s | k<-[0,1,2]] | j<-[0,1,2]] || (and [occupiedW (k,0,1) s | k<-[0,1,2]] && or [playedW (k,0,1) s | k<-[0,1,2]]) || (and [occupiedW (k,2,1) s | k<-[0,1,2]] && or [playedW (k,2,1) s | k<-[0,1,2]])

millClosedB :: State -> Bool
millClosedB s = or [ and [occupiedB (i,j,k) s | k<-[0,1,2]] && or [playedB (i,j,k) s| k<-[0,1,2]] | i<-[0,1,2], j<-[0,1,2]] || or [ and [occupiedB (k,1,j) s | k<-[0,1,2]] && or [playedB (k,1,j) s | k<-[0,1,2]] | j<-[0,1,2]] || (and [occupiedB (k,0,1) s | k<-[0,1,2]] && or [playedB (k,0,1) s | k<-[0,1,2]]) || (and [occupiedB (k,2,1) s | k<-[0,1,2]] && or [playedB (k,2,1) s | k<-[0,1,2]])

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
-- initialize a States set with one empty Nine Men\'s Morris board
initState :: States
initState = [([(a,E) | a <- positions],((-1,-1,-1),(-1,-1,-1)))]

-- compute a set of States starting from one state placing a white stone on an empty position of the board
setWStone :: State -> States
setWStone s = [ (deletePosition (r,x,y) (fst s) ++ [((r,x,y),W)],((r,x,y),snd (snd s))) | ((r,x,y),t) <- fst s, t == E]

-- compute a set of States starting from one state placing a black stone on an empty position of the board
setBStone :: State -> States
setBStone s = [ (deletePosition (r,x,y) (fst s) ++ [((r,x,y),B)],(fst (snd s), (r,x,y))) | ((r,x,y),t) <- fst s, t == E]

-- compute a set of States starting from one state taking a black stone from the board
takeBStone :: State -> States
takeBStone s = [ (deletePosition (r,x,y) (fst s) ++ [((r,x,y),E)],snd s) | ((r,x,y),t) <- fst s, t == B]

-- compute a set of States starting from one state taking a white stone from the board
takeWStone :: State -> States
takeWStone s = [ (deletePosition (r,x,y) (fst s) ++ [((r,x,y),E)],snd s) | ((r,x,y),t) <- fst s, t == W]

-- Check if there is a White Mill, if there is one, take a black stone
checkMillWTakeB :: State -> States
checkMillWTakeB s = if millClosedW s then takeBStone s else [s]

-- Check if there is a Black Mill, if there is one, take a white stone
checkMillBTakeW :: State -> States
checkMillBTakeW s = if millClosedB s then takeWStone s else [s]

-- delete a position from a given board
deletePosition :: Position -> Board -> Board
deletePosition (r,x,y) [] = []
deletePosition (r,x,y) (b:bs) = if fst b == (r,x,y) then deletePosition (r,x,y) bs else b:deletePosition (r,x,y) bs

--removes duplicate entries from a list
removeDuplicates :: (Eq a) => [a] -> [a]
removeDuplicates [] = []
removeDuplicates (x:xs) = if elem x xs then removeDuplicates xs else x:removeDuplicates xs
Zum Seitenanfang    
 
Landei

Gepostet:
07.08.2011 09:52

   
Ich würde versuchen, das Ganze mal mit GHC laufen zu lassen, das ist oft Größenordnungen schneller und optimiert vieles weg. Am besten lädst du die Haskell-Platform und die IDE Leksah runter.

Den Code schaue ich mir noch genauer an, nur einige Details: removeDuplicates gibt es schon als Data.List.nub, wobei für längere Listen mit sortierbaren Datentypen das Hin- und Herschaufeln zu einem Set schneller ist.


occupiedW (r,x,y) s = if elem ((r,x,y),W) (fst s) then True else False
-->
occupiedW (r,x,y) s = elem ((r,x,y),W) (fst s)


Viele der Einzeiler kann man viel eleganter mehrzeilig schreiben, auch deshalb wäre GHC besser als GHCi.
Zum Seitenanfang    
 
Landei

Gepostet:
07.08.2011 14:04

   
Mal ein Anfang:


import Data.List

-- Haskell-Program for calculation of all possible states after setting of stones

-- opponents
data Player = Black | White deriving (Show, Eq)
-- possible occupations for the positions
data Stone = E | W | B deriving (Show,Eq)

-- positions on the Nine Men\'s Morris Board
type Position = (Int,Int,Int)
-- a whole Nine Men\'s Morris Board
type Board = [(Position, Stone)]
-- a whole State of Nine Men\'s Morris including a board and the last position W placed a stone on and the last position B placed a stone on
type State = (Board,(Position,Position))
-- the set of states that is operated on
type States = [State]

-- possible coordinates for the positions

-- the set of positions that a Nine Men\\\'s Morris board consists of
positions = [(r,x,y) | r <- coordinates, x <- coordinates, y <- coordinates, (x,y) /= (1,1)] where
coordinates = [0,1,2]

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
-- The Main Programm

-- compute all states that occur after setting of stones
computeStates :: States
computeStates = rekComputeStates 0 initState

-- compute recursively all States with 9 Stones being set by each player
rekComputeStates :: Int -> States -> States
rekComputeStates 9 a = a
rekComputeStates n a = rekComputeStates (n+1) $ nub $ concatMap (checkMillTake Black) $
concatMap (setStone Black) $
concatMap (checkMillTake White) $
concatMap (setStone White) a

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
-- The atomic formulas

stone White = W
stone Black = B

occupied :: Player -> Position -> State -> Bool
occupied player pos s = elem (pos, stone player) (fst s)

played :: Player -> Position -> State -> Bool
played White pos s = pos == fst (snd s)
played Black pos s = pos == snd (snd s)

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
-- The more complex formulas
millClosed :: Player -> State -> Bool
millClosed p s = or [ and [occupied p (i,j,k) s | k<-[0,1,2]] && or [played p (i,j,k) s | k<-[0,1,2]] | i<-[0,1,2], j<-[0,1,2]] ||
or [ and [occupied p (k,1,j) s | k<-[0,1,2]] && or [played p (k,1,j) s | k<-[0,1,2]] | j<-[0,1,2]] ||
(and [occupied p (k,0,1) s | k<-[0,1,2]] && or [played p (k,0,1) s | k<-[0,1,2]]) ||
(and [occupied p (k,2,1) s | k<-[0,1,2]] && or [played p (k,2,1) s | k<-[0,1,2]])

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
-- initialize a States set with one empty Nine Men\\\'s Morris board
initState :: States
initState = [([(a,E) | a <- positions],((-1,-1,-1),(-1,-1,-1)))]

-- compute a set of States starting from one state placing a white stone on an empty position of the board
setStone :: Player -> State -> States
setStone p s = [ (deletePosition pos (fst s) ++ [(pos, stone p)], f pos p) | (pos ,t) <- fst s, t == E] where
f pos White = (pos, snd (snd s))
f pos Black = (fst (snd s), pos)

-- compute a set of States starting from one state taking a black stone from the board
takeStone :: Player -> State -> States
takeStone p s = [ (deletePosition pos (fst s) ++ [(pos, E)],snd s) | (pos,t) <- fst s, t == stone p]

-- Check if there is a White Mill, if there is one, take a black stone
checkMillTake :: Player -> State -> States
checkMillTake p s = if millClosed p s then takeStone (opp p) s else [s] where
opp Black = White
opp White = Black

-- delete a position from a given board
deletePosition :: Position -> Board -> Board
deletePosition pos = filter ((== pos).fst)


Ich hoffe, dass ich nichts zerschossen habe. rekComputeStates und millClosed sehen noch furchtbar aus.
Zum Seitenanfang