Блог

 import Data.List (intercalate)
import Control.Concurrent (threadDelay)
import Data.Maybe (fromJust)
import System.IO


-- I love how amazingly concise Haskell code can be.  This same program in C, C   or Java
-- would be at least twice as long.


pascal :: Int -> Int -> Int
pascal row col | col >= 0 amp;amp; col <= row =
                 if row == 0 || col == 0 || row == col
                 then 1
                 else pascal (row - 1) (col - 1)   pascal (row - 1) col
pascal _ _ = 0


pascalFast' :: [((Int, Int), Int)] -> Int -> Int -> Int
pascalFast' dict row col | col > row = 0
pascalFast' dict row col | row == 0 || col == 0 || row == col = 1
pascalFast' dict row col =
  let value1 = lookup (row - 1, col - 1) dict
      value2 = lookup (row - 1, col) dict
  in if not(value1 == Nothing || value2 == Nothing)
     then (fromJust value1)   (fromJust value2)
     else let dict'  = ((row - 1, col), pascalFast' dict (row - 1) col) : dict
              dict'' = ((row - 1, col - 1), pascalFast' dict' (row - 1) (col - 1)) : dict' 
          in (pascalFast' dict'' (row - 1) col)   (pascalFast' dict'' (row - 1) (col - 1))


pascalFast = pascalFast' []
                

pascalsTriangle :: Int -> [[Int]]
pascalsTriangle rows =
  [[pascal row col | col <- [0..row]] | row <- [0..rows]]


main :: IO ()
main = do
  putStrLn "" 
  putStr "Starting at row #0, how many rows of Pascal's Triangle do you want to print out? "
  hFlush stdout
  numRows <- (s -> read s :: Int) <$> getLine
  let triangle = pascalsTriangle numRows
      longestStringLength = (length . show) $ foldl1 max $ flatten triangle
      triangleOfStrings = map (intercalate ", ") $ map (map (pad longestStringLength)) triangle
      lengthOfLastDiv2 = div ((length . last) triangleOfStrings) 2 
  putStrLn ""
  mapM_ (s -> let spaces = [' ' | x <- [1 .. lengthOfLastDiv2 - div (length s) 2]]
                   in (putStrLn $ spaces    s) >> threadDelay 200000) triangleOfStrings
  putStrLn ""
  

flatten :: [[a]] -> [a]
flatten xs =
  [xss | ys <- xs, xss <- ys]


pad :: Int -> Int -> String
pad i k =
  [' ' | _ <- [1..n]]    m
  where m = show k
        n = i - length m

  

Хоть убей, я не понимаю, почему pascalFast не РАБОТАЕТ БЫСТРО!!! Он проверяет тип и математически он корректен, но моя функция «pascalFast» работает так же медленно, как и моя функция «pascal». Есть идеи? И нет, это не домашнее задание. Это то, что я просто хочу попробовать для себя. Спасибо за отзыв.

Лучший, Дуглас Левит

На самом деле вы main вообще не вызываете pascalFast , поэтому мне непонятно, что именно вы делали, что заставило вас сделать вывод, что это медленно — с некоторым усилием я могу сказать, что это медленно, глядя на это, но некоторые доказательства в вопросе были бы хороши.

Что касается того, почему, у меня возникают две проблемы. Мне кажется, что, поскольку вы передаете словарь «вверх» в базовый регистр, но никогда не передаете его вниз или вбок, вы только кэшируете результаты, на которые вы никогда больше не посмотрите. Попробуйте выполнить оценку pascalFast [] 2 1 вручную, на бумаге, и посмотрите, попадете ли вы когда-нибудь в кэш.

Во-вторых, даже если вы правильно кэшировали, использование lookup займет время, линейное по размеру списка, поэтому время выполнения по крайней мере квадратично по количеству сгенерированных записей: для каждого генерируемого элемента вы просматриваете все остальные элементы хотя бы один раз. Для эффективного кэширования вам нужна реальная структура данных, например, из Data.Map .

Но отдельно от вопроса о том, как эффективно запоминать, часто лучше вообще не запоминать, начиная с базовых случаев и наращивая, а не переходя к конечному результату. Что-то вроде этого довольно классическое для треугольника Паскаля:

 triangle :: [[Int]]
triangle = iterate nextRow [1]
  where nextRow xs = 1 : zipWith ( ) xs (tail xs)    [1]

main :: IO ()
main = print $ take 5 triangle