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 писал(а):
Так что это просто оптимизация.
А вы тут сразу -- "не умеешь, не умеешь!!!" :lol: :lol: :lol:
И оптимизировать тоже не умеет.

Автор:  Geniepro [ Среда, 21 Октябрь, 2009 07:27 ]
Заголовок сообщения:  Re: Решето Эратосфена.

Info21 писал(а):
Geniepro писал(а):
Так что это просто оптимизация.
А вы тут сразу -- "не умеешь, не умеешь!!!" :lol: :lol: :lol:
И оптимизировать тоже не умеет.

Вспоминается анекдот про то, чем отличаются американский, израильский и русский форумы.

На американском форуме задаёшь вопрос и тебе тут же дают ответ.
На израильском форуме задаёшь вопрос и тебе тут же задают встречный вопрос.
На русском форуме задаёшь вопрос и тебе долго объясняют какой ты мудак...

Автор:  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 писал(а):
И оптимизировать тоже не умеет.

Эк, Вы его сурово.

- Разве это чушь? - вскричала Королева, - Видала я такую чушь, по сравнению с которой эта - просто мечта препода! (Алиса в Засиркалье).:wink:

К примеру этот цикл можно было изобразить что-нибудь вроде
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/