Автор Тема: Решаем задачки. :)  (Прочитано 100910 раз)

kemiisto

  • Jr. Member
  • **
  • Сообщений: 64
    • Просмотр профиля
    • kemiisto.ru
Решаем задачки. :)
« : Сентябрь 26, 2011, 01:06:48 pm »
Я читаю эту книгу. И решаю задачки в ББ!!!111 ;D Решения можно увидеть тут. valexey там же выкладывает "толстые" решения на С. :D Кому интересно, может присоединиться.
« Последнее редактирование: Сентябрь 26, 2011, 05:00:28 pm от kemiisto »

Geniepro

  • Hero Member
  • *****
  • Сообщений: 1955
  • Знайте- истина в том, что повторено трижды подряд!
    • Просмотр профиля
Re: Решаем задачки. :)
« Ответ #1 : Сентябрь 26, 2011, 01:22:04 pm »
обновление тут (в архиве): http://oberspace.dyndns.org/index.php/topic,142.msg2268.html#msg2268

module Ex_1 where

main = do
    n <- readLn :: IO Integer
    let xs = [ show i ++ " и " ++ show (n `div` i)
             | i <- takeWhile (\k -> k*k <= n) [2..]
             , n `mod` i == 0
             ]
    mapM_ putStrLn xs

module Ex_2 where

main = do
    n <- readLn :: IO Integer
    putStrLn $ if perfect n then "Да" else "Нет"
  where
    perfect x = x == sum [d | d <- [1..x `div` 2], x `mod` d == 0 ]

module Ex_3 where

main = do
    str <- getLine
    print $ sum $ filter (>0) $ map (read :: String -> Integer) $ words str

module Ex_4 where

main = do
    str <- getLine
    print $ sum $ filter even $ map (read :: String -> Integer) $ words str

module Ex_5 where

import Data.List

main = do
    str <- getLine
    let [x, y, z] = sort $ take 3 $ map (read :: String -> Integer) $ words str
    putStrLn $ if x*x + y*y == z*z then "Да" else "Нет"
« Последнее редактирование: Сентябрь 26, 2011, 05:12:08 pm от Geniepro »
to iterate is human, to recurse, divine

Салат «рекурсия»: помидоры, огурцы, салат…

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re: Решаем задачки. :)
« Ответ #2 : Сентябрь 26, 2011, 03:35:37 pm »
module Ex_2 where

main = do
    n <- readLn :: IO Integer
    putStrLn $ if perfect n then "Да" else "Нет"
  where
    perfect x = x == sum [d | d <- [1..x `div` 2], x `mod` d == 0 ]
Не компилируется (другие аналогично). Имеем следующее:
$ ghc Ex_2.hs
ld: warning: could not create compact unwind for .LFB3: non-standard register 5 being saved in prolog
Undefined symbols for architecture i386:
  "___stginit_ZCMain", referenced from:
      _main in libHSrtsmain.a(Main.o)
  "_ZCMain_main_closure", referenced from:
      _main in libHSrtsmain.a(Main.o)
ld: symbol(s) not found for architecture i386
collect2: ld returned 1 exit status
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"

Geniepro

  • Hero Member
  • *****
  • Сообщений: 1955
  • Знайте- истина в том, что повторено трижды подряд!
    • Просмотр профиля
Re: Решаем задачки. :)
« Ответ #3 : Сентябрь 26, 2011, 03:53:27 pm »
Не компилируется (другие аналогично). Имеем следующее:
$ ghc Ex_2.hs
ld: warning: could not create compact unwind for .LFB3: non-standard register 5 being saved in prolog
Undefined symbols for architecture i386:
  "___stginit_ZCMain", referenced from:
      _main in libHSrtsmain.a(Main.o)
  "_ZCMain_main_closure", referenced from:
      _main in libHSrtsmain.a(Main.o)
ld: symbol(s) not found for architecture i386
collect2: ld returned 1 exit status

Я-то проверял в интерпретаторе, а при компиляции надо имена модулей Ex_1 и тд переименовать на Main )))
module Main where

main = do
    n <- readLn :: IO Integer
    putStrLn $ if perfect n then "Да" else "Нет"
  where
    perfect x = x == sum [d | d <- [1..x `div` 2], x `mod` d == 0]
« Последнее редактирование: Сентябрь 26, 2011, 04:05:39 pm от Geniepro »
to iterate is human, to recurse, divine

Салат «рекурсия»: помидоры, огурцы, салат…

Geniepro

  • Hero Member
  • *****
  • Сообщений: 1955
  • Знайте- истина в том, что повторено трижды подряд!
    • Просмотр профиля
Re: Решаем задачки. :)
« Ответ #4 : Сентябрь 26, 2011, 05:10:00 pm »
Выложил в архиве каталог с исходниками решений на хаскеле с батниками для их компиляции
GHC 7.0.3

Там во второй задачке (про совершенные числа) тестовое входное значение: 137438691328 (седьмое совершенное число).
На моём компе (P-DualCore 2.6) вычисляется за 0.1 сек.
Интересно бы сравнить время с сишным и паскалевским решениями... 8)
to iterate is human, to recurse, divine

Салат «рекурсия»: помидоры, огурцы, салат…

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re: Решаем задачки. :)
« Ответ #5 : Сентябрь 26, 2011, 06:43:01 pm »
Там во второй задачке (про совершенные числа) тестовое входное значение: 137438691328 (седьмое совершенное число).
На моём компе (P-DualCore 2.6) вычисляется за 0.1 сек.
Интересно бы сравнить время с сишным и паскалевским решениями... 8)

Вот сравнение с С++ решением:
Хаскель:
$ time echo 137438691328 | ./ex_2.exe
Да

real    0m0.142s
user    0m0.144s
sys     0m0.004s

С++:
$ time echo 137438691328 | ./a.out
Yes

real    0m0.090s
user    0m0.092s
sys     0m0.000s

Хаскель примерно в полтора раза медленнее.
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"

Geniepro

  • Hero Member
  • *****
  • Сообщений: 1955
  • Знайте- истина в том, что повторено трижды подряд!
    • Просмотр профиля
Re: Решаем задачки. :)
« Ответ #6 : Сентябрь 26, 2011, 07:21:14 pm »
Хаскель примерно в полтора раза медленнее.
Ну а какая-нить там Ада или Компонентный Паскаль -- в два раза медленнее. И чо? )))
to iterate is human, to recurse, divine

Салат «рекурсия»: помидоры, огурцы, салат…

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re: Решаем задачки. :)
« Ответ #7 : Сентябрь 26, 2011, 07:22:46 pm »
Хаскель примерно в полтора раза медленнее.
Ну а какая-нить там Ада или Компонентный Паскаль -- в два раза медленнее. И чо? )))
Это бездоказательное утверждение.
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re: Решаем задачки. :)
« Ответ #8 : Сентябрь 26, 2011, 07:27:37 pm »
Кстати, я ошибся. Хаскель не в полтора раза медленнее, а более чем в два. Это хорошо видно на больших числах:
$ time echo 1374386913280000 | ./a.out
No

real    0m6.055s
user    0m6.024s
sys     0m0.032s

$ time echo 1374386913280000 | ./ex_2.exe
Нет

real    0m13.053s
user    0m13.009s
sys     0m0.024s
Результат стабильный.
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"

Geniepro

  • Hero Member
  • *****
  • Сообщений: 1955
  • Знайте- истина в том, что повторено трижды подряд!
    • Просмотр профиля
Re: Решаем задачки. :)
« Ответ #9 : Сентябрь 26, 2011, 09:40:39 pm »
более оптимизированное решение второй задачки:
module Main where

main :: IO ()
main = do
    n <- readLn :: IO Integer
    putStrLn $ if perfect n then "Да" else "Нет"
  where
    perfect x = x == sum (1 : [ i + d
                              | i <- takeWhile (<= x') [2..]
                              , let (d, m) = x `divMod` i
                              , m == 0
                              ])
      where
        x' = truncate $ sqrt $ fromInteger x

выполняется у меня примерно в полтора раза быстрее предыдущего. Теперь должно не сильно уступать сишному ))
to iterate is human, to recurse, divine

Салат «рекурсия»: помидоры, огурцы, салат…

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re: Решаем задачки. :)
« Ответ #10 : Сентябрь 26, 2011, 09:48:20 pm »
$ time echo 1374386913280000 | ./ex_2.exe
Нет

real    0m11.238s
user    0m11.197s
sys     0m0.032s

Быстрее, но не существенно.
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"

Geniepro

  • Hero Member
  • *****
  • Сообщений: 1955
  • Знайте- истина в том, что повторено трижды подряд!
    • Просмотр профиля
Re: Решаем задачки. :)
« Ответ #11 : Сентябрь 26, 2011, 11:15:16 pm »
ладно, вот три окончательных варианта второй задачи:

main :: IO ()
main = do
    n <- readLn :: IO Integer
    putStrLn $ if perfect n then "Да" else "Нет"
  where
    perfect x = x == sum (1 : [ i + d
                              | i <- [2..x']
                              , let (d, m) = x `divMod` i
                              , m == 0
                              ])
      where
        x' = truncate $ sqrt $ fromInteger x

import Control.Parallel

main :: IO ()
main = do
    n <- readLn :: IO Integer
    putStrLn $ if perfect n then "Да" else "Нет"
  where
    perfect x = sum2 `par` sum3 `pseq` x == 1 + sum2 + sum3
      where
        sum2 = bs 2
        sum3 = bs 3
        bs b = sum  [ i + d
                    | i <- [b, b + 2 .. sqx]
                    , let (d, m) = x `divMod` i
                    , m == 0
                    ]
        sqx   = truncate $ sqrt $ fromInteger x

import Control.Concurrent

main :: IO ()
main = do
    n <- readLn :: IO Integer
    p <- perfect n
    putStrLn $ if p then "Да" else "Нет"
  where
    perfect x = do
        sum2c <- newChan
        sum3c <- newChan
        forkOS $ calcSum 2 sum2c
        forkOS $ calcSum 3 sum3c
        sum2 <- readChan sum2c
        sum3 <- readChan sum3c
        return $ x == 1 + sum2 + sum3
      where
        calcSum b c = do
            writeChan c $! sum  [ i + d
                                | i <- [b, b + 2 .. sqx]
                                , let (d, m) = x `divMod` i
                                , m == 0
                                ]
        sqx   = truncate $ sqrt $ fromInteger x

Время выполнения на числе 1374386913280000, соответственно:
6.2 сек
5.2 сек
4.8 сек
К сожалению, время уменьшилось не в два раза на моём двухядернике ((

UPD. Поправил первое решение
« Последнее редактирование: Сентябрь 26, 2011, 11:21:09 pm от Geniepro »
to iterate is human, to recurse, divine

Салат «рекурсия»: помидоры, огурцы, салат…

Geniepro

  • Hero Member
  • *****
  • Сообщений: 1955
  • Знайте- истина в том, что повторено трижды подряд!
    • Просмотр профиля
Re: Решаем задачки. :)
« Ответ #12 : Сентябрь 27, 2011, 10:21:59 am »
проверил на процессоре P-DualCore 1.6 сишный вариант с int64 на tinycc 0.9.23 и три варианта на хаскеле (тоже с Int64)

сишный вариант 5.1 сек
хаскельные: 7.2, 4.1 (par) и 3.9 (forkOS) сек

Ура!!! хаскель рулит! обогнал сишника )))

ЗЫ. TinyCC -- неоптимизирующий, почти однопроходный компилятор, который по качеству генерации маш. кода примерно соответствует BBCP (когда-то я их сравнивал на микротестах -- всяких там сортировках и тд) и сильно (как минимум в 2 раза) уступает в этом плане GCC
to iterate is human, to recurse, divine

Салат «рекурсия»: помидоры, огурцы, салат…

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re: Решаем задачки. :)
« Ответ #13 : Сентябрь 27, 2011, 10:22:54 am »
К сожалению, время уменьшилось не в два раза на моём двухядернике ((
А ты как запускал?
У меня получилось 6 секунд, то есть раза в два быстрее прежних решений (по тактам сответственно так же).
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re: Решаем задачки. :)
« Ответ #14 : Сентябрь 27, 2011, 10:25:46 am »
проверил на процессоре P-DualCore 1.6 сишный вариант с int64 на tinycc 0.9.23 и три варианта на хаскеле (тоже с Int64)

сишный вариант 5.1 сек
хаскельные: 7.2, 4.1 (par) и 3.9 (forkOS) сек

Ура!!! хаскель рулит! обогнал сишника )))

ЗЫ. TinyCC -- неоптимизирующий, почти однопроходный компилятор, который по качеству генерации маш. кода примерно соответствует BBCP (когда-то я их сравнивал на микротестах -- всяких там сортировках и тд) и сильно (как минимум в 2 раза) уступает в этом плане GCC
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"