2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Haskell: digitToInt + show быстрее численной реализации
Сообщение23.10.2016, 22:20 


28/07/13
165
Пусть digit -- функция, преобразующую число Integer в список его десятичных цифр [Int] (порядок не важен).

Вопрос. Почему такое решение, с промежуточным преобразованием числа в строку,
Код:
import Data.Char (digitToInt)
digits :: Integer -> [Int]
digits = map digitToInt . show

работает примерно в 2 раза быстрее, чем непосредственное численное вычисление
Код:
digits :: Integer -> [Int]
digits 0 = []
digits n = let (q, r) = quotRem n 10 in (fromIntegral r) : (digits q)

И в GHCI и при компиляции через ghc -O.

 Профиль  
                  
 
 Re: Haskell: digitToInt + show быстрее численной реализации
Сообщение23.10.2016, 22:37 
Аватара пользователя


18/06/12

499
планета Земля
Потому, что итерация map-а занимает заметно меньше времени, чем итерация с побитовым сдвигом, разве вывод не очевиден?

 Профиль  
                  
 
 Re: Haskell: digitToInt + show быстрее численной реализации
Сообщение23.10.2016, 23:09 
Заслуженный участник


27/04/09
28128
Вместо того чтобы делать предположения, стоит открыть исходный код инстанса Show Integer и посмотреть методы: http://hackage.haskell.org/package/base-4.9.0.0/docs/src/GHC.Show.html#line-437.

-- Пн окт 24, 2016 01:13:04 --

user14284
Кстати, попробуйте переписать вашу версию с использованием unfoldr.

-- Пн окт 24, 2016 01:21:09 --

И ещё можно попробовать заменить quotRem на divMod, раз уж у вас с отрицательными числами всё равно проблемы в обоих вариантах.

 Профиль  
                  
 
 Re: Haskell: digitToInt + show быстрее численной реализации
Сообщение24.10.2016, 05:00 


28/07/13
165
Eimrine
А как, по-вашему, show работает?

arseniiv в сообщении #1162382 писал(а):
Вместо того чтобы делать предположения, стоит открыть исходный код инстанса Show Integer и посмотреть методы:

Посмотрел, то же через quotRem реализовано (да и а как иначе)?

arseniiv в сообщении #1162382 писал(а):
И ещё можно попробовать заменить quotRem на divMod, раз уж у вас с отрицательными числами всё равно проблемы в обоих вариантах

Так divMod определяется через quotRem.

 Профиль  
                  
 
 Re: Haskell: digitToInt + show быстрее численной реализации
Сообщение24.10.2016, 05:45 
Заслуженный участник


27/04/09
28128
Хм, что-то я тут насоветовал, а сам не посмотрел. Почему-то казалось, что divMod должен быть базовым.

-- Пн окт 24, 2016 07:47:49 --

user14284 в сообщении #1162451 писал(а):
Посмотрел, то же через quotRem реализовано (да и а как иначе)?
Там ещё оптимизация (недаром такая куча кода вместо простой вашей строки). :-) В детали не вчитывался.

Про развёртку я тоже на авось написал. Разве что для интереса, как выглядеть будет.

-- Пн окт 24, 2016 07:54:07 --

Кстати, совсем уж шутки ради попробуйте не делать fromIntegral, получая список Integerов. Просто для сравнения.

P. S. Ещё я нашёл модуль Data.Digits из пакета digits, но там тоже как у вас, только основание любое, и зачем-то позволительно основание 1, которое вообще-то от другого вида позиционной системы. (Ну да ладно, этот вид заблуждений — особь статья.)

-- Пн окт 24, 2016 08:11:28 --

user14284 в сообщении #1162451 писал(а):
Так divMod определяется через quotRem.
Я таки глянул в код. В инстансах всё-таки вижу отдельные примитивы для всех div, mod, quot, rem, divMod, quotRem (и это правильно), а в классе странно, что предпоследнее определяется с помощью последнего, а наоборот не сделали. (Класс Eq прекрасно живёт с «циклическими» определениями (потому что до этого при определении инстанса дело не дойдёт — компилятор обязует нас определить хотя бы == или /=, потому что ему указали, какие минимальные полные определения позволять.)

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group