Написали мы программу, которая находит первые N простых чисел и вычисляет их сумму. Написали на C и на Haskell. Алгоритм тупой, но суть в том, что он одинаковый. В результате, программа на C выполняет задачу за 4 с, а на Haskell -- за 54 c. Из опций стоит только -O2.
Почему же такая разница? Привожу исходники:
int isPrime( int num ) {
int count = 0;
int i = 1;
for( ; i <= num ; ++i ) {
if( num % i == 0 ) ++count;
}
return 2 == count;
}
#define COUNT 5000
#include <stdio.h>
int main( void ) {
int count = 0;
int num = 1;
int sum = 0;
for( ; count < COUNT ; ++num ) {
if( isPrime( num ) ) {
sum += num;
++count;
}
}
printf( "%d\n" , sum );
return 0;
}
divisors num = filter (\i -> (mod num i) == 0 ) [1..num]
isPrime num = length (divisors num) == 2
firstPrimes count = take count (filter isPrime [1..])
count = 5000
main = print $ sum $ firstPrimes count
Впрочем, видно, что вариант на Haskell весь из себя ленивый и использует списки. Я пробовал расставлять строгость (сначала обдуманно, потом где попало) -- не помогло. Затем я подглядел вариант с параметром-аккумулятором и получился вот такой (страшный) код:
incDiv num i acc | mod num i == 0 = 1+acc
| otherwise = acc
divisors num i acc | i <= num = divisors num (i+1) (incDiv num i acc)
| otherwise = acc
isPrime' num = divisors num 1 0 == 2
primesSum count num acc | count > 0 = if isPrime' num
then primesSum (count-1) (num+1) (num+acc)
else primesSum count (num+1) acc
| otherwise = acc
count = 5000
main = print (primesSum count 1 0)
Однако я получил всё те же 54 с. Подскажите, пожалуйста, что я делаю не так, и возможно ли вообще в данном случае приблизить время исполнения к сишному варианту (хотя бы в два раза медленнее, но не в 13).
Предположу, что это связано с длинной арифметикой (большими числами), которую поддерживает haskell. Чтобы избавиться от этого, надо явно прописать тип Int.
divisors :: Int -> [Int]
divisors num = filter (\i -> (mod num i) == 0 ) [1..num]
isPrime num = length (divisors num) == 2
firstPrimes count = take count (filter isPrime [1..])
count = 3000
main = print $ sum $ firstPrimes count
У меня везде получается haskell в два раза медленне, чем С. Пробовал для COUNT = 1000,2000,3000,5000.
Конфигурация: Ubuntu 10.04 LTS, GHC 7.0.3, -O2
Здравствуйте, Буравчик, Вы писали:
Б>Предположу, что это связано с длинной арифметикой (большими числами), которую поддерживает haskell. Чтобы избавиться от этого, надо явно прописать тип Int. Б>... Б>А вот если Int заменить на Integer (длинное целое), то время работы увеличивается в три раза.
Да, действительно, после явного указания Int время работы программы Haskell снизилось с 54с до 20с, т.е. в 2.5 раза.
Хотя это всё ещё в 5 раз больше, чем вариант на C (4с).
Здравствуйте, Kirikaza, Вы писали:
K>Написали мы программу, которая находит первые N простых чисел и вычисляет их сумму. Написали на C и на Haskell. Алгоритм тупой, но суть в том, что он одинаковый. В результате, программа на C выполняет задачу за 4 с, а на Haskell -- за 54 c. Из опций стоит только -O2.
имхо это на С медленно. в статьях известных хаскелистов приводятся типичные для низхкоуровневого кода случаи разницы в несколько сотен раз
Haskell lists are ordinary single-linked lists. (Look up the term in any book on data structures.) This gives them certain speed properties which are well worth knowing.
2.1 Fast operations
The following operations are always 'fast':
Prepend 1 element (the
:
operator)
head
(get first element)
tail
(remove first element)
2.2 Slower operations
Any function that does something with the Nth element or the first N elements generally gets slower as N increases. The following all slow down as
n
gets larger:
xs !! n
take n xs
drop n xs
splitAt n xs
Any function which needs to process the entire list obviously gets slower as the list gets bigger. The following all slow down as the list
xs
gets larger:
length xs
list1 ++ list2
(speed depends only on the size of
list1
)
last xs
map my_fn xs
filter my_test xs
zip my_fn list1 list2
(speed depends on the smallest of the two lists — as does the size of the result list!)
x `elem` xs
sum xs
minimum xs
maximum xs
Здравствуйте, samius, Вы писали:
S>Здравствуйте, Alex912, Вы писали:
A>> Поэтому думаю без takeWhile (как я поставил в коде) такой подход будет не быстрым.
S>Смысл замера в том, что бы использовать одинаковый алгоритм в C и Haskell, а не в том что бы сделать его хоть сколько-нибудь эффективным.
Я помню была лаба на начальных курсах в университете. Посчитать фибоначчи на си через рекурсию и итерацию. В конце сделать вывод как считать лучше, как делать не стоит.
Здравствуйте, Alex912, Вы писали:
S>>Смысл замера в том, что бы использовать одинаковый алгоритм в C и Haskell, а не в том что бы сделать его хоть сколько-нибудь эффективным.
A>Я помню была лаба на начальных курсах в университете. Посчитать фибоначчи на си через рекурсию и итерацию. В конце сделать вывод как считать лучше, как делать не стоит.
Всё от задачи зависит. Если в теле рекурсии стоит что-то посложнее чем простое сложение, то затраты на рекурсивность нивелируются общим временем исполнения внутреннего кода.
Здравствуйте, peterbes, Вы писали:
P>Всё от задачи зависит. Если в теле рекурсии стоит что-то посложнее чем простое сложение, то затраты на рекурсивность нивелируются общим временем исполнения внутреннего кода.
В случае фибоначчи там просто разная сложность получается — экспоненциальная и линейная. Рекурсивно многие значения будут по несколько раз считаться.
Здравствуйте, peterbes, Вы писали:
P>Здравствуйте, Alex912, Вы писали:
S>>>Смысл замера в том, что бы использовать одинаковый алгоритм в C и Haskell, а не в том что бы сделать его хоть сколько-нибудь эффективным.
A>>Я помню была лаба на начальных курсах в университете. Посчитать фибоначчи на си через рекурсию и итерацию. В конце сделать вывод как считать лучше, как делать не стоит.
P>Всё от задачи зависит. Если в теле рекурсии стоит что-то посложнее чем простое сложение, то затраты на рекурсивность нивелируются общим временем исполнения внутреннего кода.
Здравствуйте, Kirikaza, Вы писали:
K>Да, действительно, после явного указания Int время работы программы Haskell снизилось с 54с до 20с, т.е. в 2.5 раза.
K>ArchLinux 64, E8400 @3.00GHz K>GHC 7.0.3, -O2
1) Используйте rem всесто mod. Операция % в хаскеле называется rem.
2) Используйте -fllvm.
У меня на Windows Vista x64 Q6600 @2.40GHz GHC 7.0.3 (x86) -O2 -fllvm LLVM 2.9
получается 6.25 сек. с rem и 11.69 с mod
... << RSDN@Home 1.2.0 alpha 4 rev. 1476>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
A>import Data.List
A>firstPrimes ::Int->[Int]
A>firstPrimes n= take n $ filter (isPrime) [2..]
A>count::Int->Int
A>count n= foldl' (+) 0 (firstPrimes n)
A>isPrime::Int->Bool
A>isPrime x = null $ filter (\y -> x `mod` y == 0) $ takeWhile (\y -> y*y <= x) [2..]
A>main = do
A> putStrLn $ (show . count) 5000
A>
Здесь есть "нечестная" оптимизация при поиске делителей (до квадратного корня), поэтому цифра фантастическая – 0,04c.
Я заменил эту проверку на \y -> y < x – и о чудо! – удалось выжать 3.7с на Haskell против 3.9с на Си! Круто, копаю дальше.
Заменил конструкцию takeWhile (\y -> y < x) [2..] на [2..x-1]... и получил уже 1.9с!
Стало весьма интересно, откуда всё это. С foldl' я уже пробовал баловаться вместо sum – разницы не было. Проведя несколько экспериментов, выяснил, что null xs работает гораааздо быстрее, чем length xs == 0. На данном примере – в 10 раз. В принципе, можно найти этому объяснение; тем не менее в Notes_about_speed об этом ни слова.
В приводимом мной коде делители считались от 1 до самого числа включительно, поэтому длину списка делителей нужно было сравнивать с 2. Т.е. null уже не подходит... И тут пришла идея сравнивать не длину списка делителей, а сам этот список с [1,x]. И чудо повторилось: программа выполнилась за 1,9с.
Таким образом, минимальным изменением время выполнения снизилось с 20с до 1,9с:
divisors num = filter (\i -> (mod num i) == 0 ) [1..num]
-- isPrime num = length (divisors num) == 2isPrime num = (divisors num) == [1,num]
firstPrimes count = take count (filter isPrime [1..])
count = 5000
main = print $ sum ( firstPrimes count :: [Int])
В принципе, мне так даже больше нравится, но... может кто-нибудь объяснить, в чём здесь фокус?
P.S.: После замены mod на rem время снизилось ещё – до 1,5c.
Здравствуйте, Kirikaza, Вы писали:
K>Здравствуйте, Alex912, Вы писали:
divisors num = filter (\i -> (mod num i) == 0 ) [1..num]
-- isPrime num = length (divisors num) == 2isPrime num = (divisors num) == [1,num]
firstPrimes count = take count (filter isPrime [1..])
count = 5000
main = print $ sum ( firstPrimes count :: [Int])
Этот код не соответствует коду на С. Дело в ленивости при вычислении выражения "(divisors num) == [1,num]".
Здесь divisors вычисляется лениво. Сначала вычисляется первый элемент divisors и сравнивается с единицей. Затем вычисляется второй элемент и сравнивается с num. И если второй элемент будет не равен num, то списки будут признаны не равными. Именно это происходит, если num — составное число (не простое).
Т.е. для простых чисел divisors проверяет все делители, а для составных чисел divisors будет работать до первого попавшегося делителя отличного от единицы, и другие делители искать не будет. А вот код на С всегда просматривает все возможные делители. Поэтому С получился медленнее.
Здравствуйте, Kirikaza, Вы писали:
K>Стало весьма интересно, откуда всё это. С foldl' я уже пробовал баловаться вместо sum – разницы не было. Проведя несколько экспериментов, выяснил, что null xs работает гораааздо быстрее, чем length xs == 0. На данном примере – в 10 раз. В принципе, можно найти этому объяснение; тем не менее в Notes_about_speed об этом ни слова.
Для вычисления length xs требуется пройтись по всему списку xs и посчитать элементы. А для вычисления null достаточно просмотреть первый элемент xs. Если он существует, то список не пуст.
Поэтому думаю без takeWhile (как я поставил в коде) такой подход будет не быстрым.
