2014 dxdy logo

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

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





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


28/07/13
136
Пусть 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
19797
Уфа
Вместо того чтобы делать предположения, стоит открыть исходный код инстанса 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
136
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
19797
Уфа
Хм, что-то я тут насоветовал, а сам не посмотрел. Почему-то казалось, что 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 ] 

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



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

Сейчас этот форум просматривают: Astroid


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

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