Преобразование неотрицательного Integer в его список цифр обычно выполняется следующим образом:
import Data.Char
digits :: Integer -> [Int]
digits = (map digitToInt) . show
Я пытался найти более прямой способ выполнить задачу без использования преобразования строк, но я не могу придумать что-то более быстрое.
Вещи, которые я пытался до сих пор:
Базовая линия:
digits :: Int -> [Int]
digits = (map digitToInt) . show
Получил этот вопрос из другого вопроса в StackOverflow:
digits2 :: Int -> [Int]
digits2 = map (`mod` 10) . reverse . takeWhile (> 0) . iterate (`div` 10)
Попытка бросить свою:
digits3 :: Int -> [Int]
digits3 = reverse . revDigits3
revDigits3 :: Int -> [Int]
revDigits3 n = case divMod n 10 of
(0, digit) -> [digit]
(rest, digit) -> digit:(revDigits3 rest)
Этот был вдохновлен showInt в Numeric:
digits4 n0 = go n0 [] where
go n cs
| n < 10 = n:cs
| otherwise = go q (r:cs)
where
(q,r) = n `quotRem` 10
Теперь эталон. Примечание. Я заставляю оценку с помощью filter.
λ>:set +s
λ>length $ filter (>5) $ concat $ map (digits) [1..1000000]
2400000
(1.58 secs, 771212628 bytes)
Это ссылка. Теперь для digits2:
λ>length $ filter (>5) $ concat $ map (digits2) [1..1000000]
2400000
(5.47 secs, 1256170448 bytes)
Это 3,46 раз больше.
λ>length $ filter (>5) $ concat $ map (digits3) [1..1000000]
2400000
(7.74 secs, 1365486528 bytes)
digits3 4.89 время медленнее. Просто для удовольствия я пытался использовать только revDigits3 и избегать reverse.
λ>length $ filter (>5) $ concat $ map (revDigits3) [1..1000000]
2400000
(8.28 secs, 1277538760 bytes)
Странно, это еще медленнее, 5.24 раза медленнее.
И последний:
λ>length $ filter (>5) $ concat $ map (digits4) [1..1000000]
2400000
(16.48 secs, 1779445968 bytes)
Это 10.43 время медленнее.
У меня создалось впечатление, что только использование арифметики и минусов превосходит все, что связано с преобразованием строк. Видимо, я ничего не могу понять.
Так какой трюк? Почему digits так быстро?
Я использую GHC 6.12.3.
