OberonCore https://forum.oberoncore.ru/ |
|
Решето Эратосфена. https://forum.oberoncore.ru/viewtopic.php?f=72&t=1964 |
Страница 2 из 2 |
Автор: | Alexey Veselovsky [ Вторник, 20 Октябрь, 2009 16:00 ] |
Заголовок сообщения: | Re: Решето Эратосфена. |
Geniepro писал(а): А попробуйте STUArray как в том примере с shootout -- может получше будет? Собираюсь попробовать все массивы вот отсюда: http://www.haskell.org/haskellwiki/Mode ... _libraries |
Автор: | Geniepro [ Вторник, 20 Октябрь, 2009 16:38 ] |
Заголовок сообщения: | Re: Решето Эратосфена. |
Иммутабельные массивы для этой задачи плохо подходят -- будет тратиться много времени на перегонку этого массива по куче с места на место... |
Автор: | Alexey Veselovsky [ Вторник, 20 Октябрь, 2009 16:42 ] |
Заголовок сообщения: | Re: Решето Эратосфена. |
Geniepro писал(а): Иммутабельные массивы для этой задачи плохо подходят -- будет тратиться много времени на перегонку этого массива по куче с места на место... Дык Array как раз иммутабельный. Да ещё и boxed |
Автор: | Alexey Veselovsky [ Среда, 21 Октябрь, 2009 00:01 ] |
Заголовок сообщения: | Re: Решето Эратосфена. |
Вот такой код: Код: import System (getArgs) import Control.Monad import Data.Array.IO main = do n <- liftM (read . (!! 0)) getArgs arr <- newListArray (2, n) (repeat True) :: IO (IOUArray Int Bool) eratosphene arr n last <- readArray arr n putStrLn $ show $ last eratosphene :: IOUArray Int Bool -> Int -> IO () eratosphene arr n = do forM_ [2..((round . sqrt . fromIntegral $ n) + 1)] $ \i -> do ai <- readArray arr i if ai then forM_ [(i*i),(i*i+i)..n] $ \j -> writeArray arr j False else return () Работает лишь в два раза медленней кода на С++. Для 100 000 000 имеем времена: Код: c++: user 0m2.956s
hs : user 0m6.260s |
Автор: | Info21 [ Среда, 21 Октябрь, 2009 00:12 ] |
Заголовок сообщения: | Re: Решето Эратосфена. |
Geniepro писал(а): Так что это просто оптимизация. И оптимизировать тоже не умеет.
А вы тут сразу -- "не умеешь, не умеешь!!!" |
Автор: | Geniepro [ Среда, 21 Октябрь, 2009 07:27 ] |
Заголовок сообщения: | Re: Решето Эратосфена. |
Info21 писал(а): Geniepro писал(а): Так что это просто оптимизация. И оптимизировать тоже не умеет.А вы тут сразу -- "не умеешь, не умеешь!!!" Вспоминается анекдот про то, чем отличаются американский, израильский и русский форумы. На американском форуме задаёшь вопрос и тебе тут же дают ответ. На израильском форуме задаёшь вопрос и тебе тут же задают встречный вопрос. На русском форуме задаёшь вопрос и тебе долго объясняют какой ты мудак... |
Автор: | Geniepro [ Среда, 21 Октябрь, 2009 08:05 ] |
Заголовок сообщения: | Re: Решето Эратосфена. |
Alexey Veselovsky писал(а): Вот такой код: ... Там у Вас в функции main для выравнивания знаки табуляции используются, а в строке " eratosphene arr n " только пробелы, из-за этого проблема с компиляцией возникает -- лишний пробел перед словом eratosphene. Вообще не стоит использовать табуляцию для выравнивания, лучше пробелы... И, кстати, раз у Вас всё равно импортируется модуль Control.Monad, то вместо Код: if ai then можно написатьforM_ [(i*i),(i*i+i)..n] $ \j -> writeArray arr j False else return () Код: when ai $
forM_ [(i*i),(i*i+i)..n] $ \j -> writeArray arr j False |
Автор: | Info21 [ Среда, 21 Октябрь, 2009 09:56 ] |
Заголовок сообщения: | Re: Решето Эратосфена. |
Geniepro писал(а): На русском форуме задаёшь вопрос и тебе долго объясняют какой ты мудак... Вам пенять можно только на себя.
|
Автор: | Виктор О [ Четверг, 22 Октябрь, 2009 11:10 ] |
Заголовок сообщения: | Re: Решето Эратосфена. |
Info21 писал(а): И оптимизировать тоже не умеет. Эк, Вы его сурово. - Разве это чушь? - вскричала Королева, - Видала я такую чушь, по сравнению с которой эта - просто мечта препода! (Алиса в Засиркалье). К примеру этот цикл можно было изобразить что-нибудь вроде while ((f = (p % ps[j++])) && (ps[--j]*ps[j++] <= p)); и сказать, что это линейный поиск |
Автор: | Geniepro [ Четверг, 22 Октябрь, 2009 12:50 ] |
Заголовок сообщения: | Re: Решето Эратосфена. |
Виктор О писал(а): К примеру этот цикл можно было изобразить что-нибудь вроде while ((f = (p % ps[j++])) && (ps[--j]*ps[j++] <= p)); и сказать, что это линейный поиск В обероне такое не изобразишь, а мой сишный код -- просто калька с варианта на КП. |
Автор: | Geniepro [ Четверг, 22 Октябрь, 2009 12:56 ] |
Заголовок сообщения: | Re: Решето Эратосфена. |
Alexey Veselovsky писал(а): Код: c++: user 0m2.956s hs : user 0m6.260s Нормально. Если же позарез нужно не медленнее, чем на Си -- перепишите тормозящий кусок на Си и прицепите к основной проге на Хаскелле. Даром что ли GHC = Хаскелл + Си... |
Автор: | Alexey Veselovsky [ Пятница, 23 Октябрь, 2009 10:40 ] |
Заголовок сообщения: | Re: Решето Эратосфена. |
Geniepro писал(а): Alexey Veselovsky писал(а): Код: c++: user 0m2.956s hs : user 0m6.260s Нормально. Если же позарез нужно не медленнее, чем на Си -- перепишите тормозящий кусок на Си и прицепите к основной проге на Хаскелле. Даром что ли GHC = Хаскелл + Си... Ну, я и говорю что в принципе нормально. Только поправочка -- не Си, а С++. Всё же используется std::vector и индексация идет с проверкой (использовался не operator[], а метод at()). |
Страница 2 из 2 | Часовой пояс: UTC + 3 часа |
Powered by phpBB® Forum Software © phpBB Group https://www.phpbb.com/ |