-- -- orbit-int sequential implementation -- module Sequential( -- Types Generator -- Functions , orbit ) where import Data.Dequeue (BankersDequeue, fromList, popFront, pushBack) import Data.Hashable (hash) import Table (Freq, Vertex, VTable, freq_to_stat, get_freq, insert, is_member, new, to_list) import Utils (Generator, now) type SeqConf = ([Generator], Int) type SeqStats = [(String, String)] -- DATA -- Static Machine Configuration: -- {Gs, --list of generators -- TableSize} --hash table size (ie. #slots) -- -- Statistics: -- List of pairs where the first component is an atom, the second -- some data. Part of the data is the fill frequency of the table -- (a list whose ith element indicates frequency of filling degree i). -- compute orbit of elements in list Xs under list of generators Gs, -- where the hash table is of size TableSize. -- The function returns a pair consisting of the computed orbit and a singleton -- list of statistics (mainly runtime and fill degree of the table). orbit :: [Generator] -> [Vertex] -> Int -> ([Vertex], [SeqStats]) orbit gs xs tableSize = (to_list finalTable, [stat]) where -- assemble static configuration staticMachConf = mk_static_mach_conf gs tableSize -- initialise hash table and work queue table = new tableSize queue = fromList xs -- start wall clock timer startTime = now -- start vertex server and compute orbit (finalTable, vertsRecvd) = vertex_server staticMachConf table queue 0 -- measure elapsed time (in milliseconds) elapsedTime = now - startTime -- return result stat = seq_stats elapsedTime (get_freq finalTable) vertsRecvd -- main loop working off work Queue; -- StaticMachConf -- static data -- Table -- hash table holding vertices -- Queue -- work queue -- VertsRecvd -- number of vertices removed from the Queue so far vertex_server :: SeqConf -> VTable -> BankersDequeue Vertex -> Int -> (VTable, Int) vertex_server staticMachConf table queue vertsRecvd = case popFront queue of (Nothing, _) -> (table, vertsRecvd) (Just x, queue1) -> let (newTable, newQueue) = handle_vertex staticMachConf x table queue1 in vertex_server staticMachConf newTable newQueue (vertsRecvd + 1) -- handle_vertex checks whether vertex X is stored in Table; -- if not, it is in inserted and the images of the generators -- are pushed into the work queue. handle_vertex :: SeqConf -> Vertex -> VTable -> BankersDequeue Vertex -> (VTable, BankersDequeue Vertex) handle_vertex staticMachConf x table queue = case is_member x slot table of -- check whether X is already in Table -- X already in table; do nothing True -> (table, queue) -- X not in table False -> let -- insert X at Slot newTable = insert x slot table -- compute images of X under generators Gs and enqueue xs = [g x | g <- get_gens staticMachConf] newQueue = foldl pushBack queue xs in (newTable, newQueue) -- return updated table and queue where slot = hash_vertex staticMachConf x -- compute Slot -- hash_vertex computes the hash table slot of vertex X hash_vertex :: SeqConf -> Vertex -> Int hash_vertex staticMachConf x = hsh `rem` tableSize where tableSize = get_table_size staticMachConf hsh = abs $ hash x ------------------------------------------------------------------------------- -- auxiliary functions -- functions operating on the StaticMachConf mk_static_mach_conf :: [Generator] -> Int -> SeqConf mk_static_mach_conf gs tableSize = (gs, tableSize) get_gens :: SeqConf -> [Generator] get_gens staticMachConf = fst staticMachConf get_table_size :: SeqConf -> Int get_table_size staticMachConf = snd staticMachConf -- produce readable statistics seq_stats :: Int -> Freq -> Int -> SeqStats seq_stats elapsedTime frequency vertsRecvd = ("wall_time", show elapsedTime) : ("vertices_recvd", show vertsRecvd) : freq_to_stat frequency