Почему ` (карта digitToInt) .шоу` происходит так быстро?
https://stackoverflow.com/questions/4841078
-
27-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Преобразование неотрицательных 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.
Решение
Поскольку я пока не могу добавлять комментарии, я еще немного поработаю и просто проанализирую их все.Я ставлю анализ на первое место;однако соответствующие данные приведены ниже.(Примечание:все это также сделано в 6.12.3 - пока никакой магии GHC 7.)
Анализ:
Версия 1: шоу довольно хорошее для целых чисел, особенно для таких коротких, как у нас.Создание строк на самом деле имеет тенденцию быть приличным в GHC;однако чтение в строки и запись больших строк в файлы (или стандартный вывод, хотя вы бы не хотели этого делать) - это те области, где ваш код может полностью сканироваться.Я бы заподозрил, что многие детали, объясняющие, почему это происходит так быстро, связаны с умной оптимизацией в show для целых чисел.
Версия 2: Этот был самым медленным из всех при компиляции.Некоторые проблемы:обратный является строгим в своей аргументации.Это означает, что вам не выгодно выполнять вычисления над первой частью списка, пока вы вычисляете следующие элементы;вы должны вычислить их все, перевернуть их, а затем выполнить свои вычисления (а именно (`mod` 10) ) для элементов списка.Хотя это может показаться небольшим, это может привести к большему использованию памяти (обратите внимание, что здесь также выделено 5 ГБ оперативной памяти) и замедлению вычислений.(Короче говоря, длинная история:не используйте обратный ход.)
Версия 3: Помните, как я только что сказал, не используйте обратный ход?Оказывается, если вы уберете его, общее время выполнения этого уменьшится до 1,79 с - едва ли медленнее базового.Единственная проблема здесь заключается в том, что по мере углубления в число вы наращиваете корешок списка в неправильном направлении (по сути, вы вводите "в" список с помощью рекурсии, в отличие от ввода "в" список).
Версия 4: Это очень умная реализация.Вы получаете выгоду от нескольких приятных вещей:во-первых, quotRem должен использовать алгоритм Евклида, который является логарифмическим в своем большем аргументе.(Возможно, это быстрее, но я не верю, что есть что-то большее, чем постоянный множитель, быстрее Евклида.) Кроме того, вы переходите к списку, как обсуждалось в прошлый раз, так что вам не нужно решать какие-либо проблемы со списком по ходу работы - список уже полностью создан, когда вы возвращаетесь к его анализу.Как вы можете видеть, от этого выигрывает производительность.
Этот код, вероятно, был самым медленным в GHCi, потому что многие оптимизации, выполняемые с флагом -O3 в GHC, касаются ускорения составления списков, в то время как GHCi ничего из этого не сделал бы.
Уроки: чтобы правильно перейти к списку, следите за промежуточной строгостью, которая может замедлить вычисления, и проделайте некоторую работу, просматривая детализированную статистику производительности вашего кода.Также компилируйте с флагами -O3:всякий раз, когда вы этого не делаете, все те люди, которые тратят много часов на сверхбыстрое приготовление GHC, смотрят на вас большими щенячьими глазами.
Данные:
Я просто взял все четыре функции, поместил их в один файл .hs, а затем изменил по мере необходимости, чтобы отразить используемую функцию.Кроме того, я увеличил ваш лимит до 5e6, потому что в некоторых случаях скомпилированный код будет выполняться менее чем за полсекунды на 1e6, и это может начать вызывать проблемы с детализацией выполняемых нами измерений.
Параметры компилятора:использование ghc --make -O3 [имя файла].hs чтобы заставить GHC провести некоторую оптимизацию.Мы приведем статистику к стандартной ошибке, используя цифры +RTS -sstderr.
Сброс в -sstderr дает нам результат, который выглядит примерно так, в случае digits1:
digits1 +RTS -sstderr
12000000
2,885,827,628 bytes allocated in the heap
446,080 bytes copied during GC
3,224 bytes maximum residency (1 sample(s))
12,100 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 5504 collections, 0 parallel, 0.06s, 0.03s elapsed
Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 1.61s ( 1.66s elapsed)
GC time 0.06s ( 0.03s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 1.67s ( 1.69s elapsed)
%GC time 3.7% (1.5% elapsed)
Alloc rate 1,795,998,050 bytes per MUT second
Productivity 96.3% of total user, 95.2% of total elapsed
Здесь есть три ключевые статистические данные:
- Общий объем используемой памяти:всего 1 МБ означает, что эта версия очень компактна.
- Общее время:1.61s сейчас ничего не значит, но мы посмотрим, как это будет выглядеть на фоне других реализаций.
- Продуктивность:Это всего лишь 100% минус сбор мусора;поскольку мы находимся на уровне 96,3%, это означает, что мы не создаем много объектов, которые оставляем лежать в памяти..
Хорошо, давайте перейдем к версии 2.
digits2 +RTS -sstderr
12000000
5,512,869,824 bytes allocated in the heap
1,312,416 bytes copied during GC
3,336 bytes maximum residency (1 sample(s))
13,048 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 10515 collections, 0 parallel, 0.06s, 0.04s elapsed
Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 3.20s ( 3.25s elapsed)
GC time 0.06s ( 0.04s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 3.26s ( 3.29s elapsed)
%GC time 1.9% (1.2% elapsed)
Alloc rate 1,723,838,984 bytes per MUT second
Productivity 98.1% of total user, 97.1% of total elapsed
Итак, мы наблюдаем интересную закономерность.
- Тот же объем используемой памяти.Это означает, что это довольно хорошая реализация, хотя это может означать, что нам нужно протестировать на более высоких входных данных выборки, чтобы увидеть, сможем ли мы найти разницу.
- Это занимает в два раза больше времени.Мы вернемся к некоторым предположениям о том, почему это происходит позже.
- На самом деле это немного более продуктивно, но, учитывая, что GC не является огромной частью ни одной из программ, это не помогает нам ни в чем существенном.
Версия 3:
digits3 +RTS -sstderr
12000000
3,231,154,752 bytes allocated in the heap
832,724 bytes copied during GC
3,292 bytes maximum residency (1 sample(s))
12,100 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 6163 collections, 0 parallel, 0.02s, 0.02s elapsed
Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 2.09s ( 2.08s elapsed)
GC time 0.02s ( 0.02s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 2.11s ( 2.10s elapsed)
%GC time 0.7% (1.0% elapsed)
Alloc rate 1,545,701,615 bytes per MUT second
Productivity 99.3% of total user, 99.3% of total elapsed
Итак, мы наблюдаем некоторые странные закономерности.
- Общий объем используемой памяти по-прежнему составляет 1 МБ.Таким образом, мы не столкнулись ни с чем неэффективным с точки зрения памяти, и это хорошо.
- Мы не совсем в digits1, но мы довольно легко превзошли digits2.
- Очень мало GC.(Имейте в виду, что производительность выше 95% - это очень хорошо, поэтому на самом деле мы не имеем здесь дела с чем-то слишком значительным.)
И, наконец, версия 4:
digits4 +RTS -sstderr
12000000
1,347,856,636 bytes allocated in the heap
270,692 bytes copied during GC
3,180 bytes maximum residency (1 sample(s))
12,100 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 2570 collections, 0 parallel, 0.00s, 0.01s elapsed
Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 1.09s ( 1.08s elapsed)
GC time 0.00s ( 0.01s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 1.09s ( 1.09s elapsed)
%GC time 0.0% (0.8% elapsed)
Alloc rate 1,234,293,036 bytes per MUT second
Productivity 100.0% of total user, 100.5% of total elapsed
Вау!Давайте разберем это по полочкам:
- У нас все еще всего 1 мбайт.Это почти наверняка особенность этих реализаций, поскольку они остаются на уровне 1 МБ на входах 5e5 и 5e7.Свидетельство лени, если хотите.
- Мы сократили около 32% нашего первоначального времени, что довольно впечатляет.
- Я подозреваю, что приведенные здесь проценты отражают степень детализации мониторинга sstderr, а не какие-либо вычисления для сверхсветовых частиц.
Другие советы
Отвечая на вопрос "почему rem вместо mod?" в комментариях.Когда имеешь дело с положительными ценностями rem x y === mod x y таким образом, единственное, на что следует обратить внимание, - это производительность:
> import Test.QuickCheck
> quickCheck (\x y -> x > 0 && y > 0 ==> x `rem` y == x `mod` y)
Итак, что же это за производительность?Если у вас нет веской причины не делать этого (а леность не является веской причиной, равно как и незнание Критерия), тогда используйте хороший инструмент для тестирования, я использовал Criterion:
$ cat useRem.hs
import Criterion
import Criterion.Main
list :: [Integer]
list = [1..10000]
main = defaultMain
[ bench "mod" (nf (map (`mod` 7)) list)
, bench "rem" (nf (map (`rem` 7)) list)
]
Запуск этого показывает rem это значительно лучше, чем mod (скомпилирован с -O2):
$ ./useRem
...
benchmarking mod
...
mean: 590.4692 us, lb 589.2473 us, ub 592.1766 us, ci 0.950
benchmarking rem
...
mean: 394.1580 us, lb 393.2415 us, ub 395.4184 us, ci 0.950
