more efficient implementation of runMarkov

[jwaldmann]

(will make a PR, just writing down the observation and idea now)

current implemenation is inefficient in several ways (basically, every usage of the list type for storing data for repeated access is questionable)

runMarkov n tp xi seed = reverse -- computes full list before outputting first element
  $ (iterate (markovStep $ renorm) [xi])!! (n-1) where
  markovStep tp' xs = (fromJust
   $ findIndex (r <=) -- linear cost for searching 
 $ scanl1  (+) (tp'!!(head xs) -- linear cost for accessing the matrix
  )) : xs 
 where
    r = timeToRand $ seed + (fromIntegral . length -- computes length each time
  ) xs / fromIntegral n
  renorm = [ map (/ sum x) x | x <- tp ]

of course, this is all quite irrelevant if the set of states is small (e.g., small interval of notes). But perhaps it is not, e.g., if you want to keep previous 2 notes in the state as well.

Ideas for a better implemetation

• to avoid linear findIndex, use binary search. This only helps when acces by index is fast, so ...
• instead of [[Double]], use Vector (Vector Double)

My implementation achieves these timings:

tidal> m w = [[ abs(x-y) | y <-[0 .. w-1]] | x <- [0 .. w-1]]

tidal> e = 5 ; w = 10

tidal> drop (10^e) $ runMarkov  (10^e + 10) (m w) 0 0
[6,9,6,3,7,2,7,3,8,3]
(18.34 secs, 162,666,416 bytes)

tidal> drop (10^e) $ runMarkov' (10^e + 10) (m w) 0 0
[6,9,6,3,7,2,7,3,8,3]
(0.18 secs, 87,951,624 bytes)

NB - output also shows that results are identical