OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Пятница, 15 Ноябрь, 2019 00:32

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 32 ]  На страницу Пред.  1, 2
Автор Сообщение
 Заголовок сообщения: Re: Решето Эратосфена.
СообщениеДобавлено: Вторник, 20 Октябрь, 2009 16:00 

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
Geniepro писал(а):
А попробуйте STUArray как в том примере с shootout -- может получше будет?


Собираюсь попробовать все массивы вот отсюда: http://www.haskell.org/haskellwiki/Mode ... _libraries


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Решето Эратосфена.
СообщениеДобавлено: Вторник, 20 Октябрь, 2009 16:38 

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
Иммутабельные массивы для этой задачи плохо подходят -- будет тратиться много времени на перегонку этого массива по куче с места на место...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Решето Эратосфена.
СообщениеДобавлено: Вторник, 20 Октябрь, 2009 16:42 

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
Geniepro писал(а):
Иммутабельные массивы для этой задачи плохо подходят -- будет тратиться много времени на перегонку этого массива по куче с места на место...


Дык Array как раз иммутабельный. Да ещё и boxed ;-)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Решето Эратосфена.
СообщениеДобавлено: Среда, 21 Октябрь, 2009 00:01 

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
Вот такой код:
Код:
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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Решето Эратосфена.
СообщениеДобавлено: Среда, 21 Октябрь, 2009 00:12 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8196
Откуда: Троицк, Москва
Geniepro писал(а):
Так что это просто оптимизация.
А вы тут сразу -- "не умеешь, не умеешь!!!" :lol: :lol: :lol:
И оптимизировать тоже не умеет.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Решето Эратосфена.
СообщениеДобавлено: Среда, 21 Октябрь, 2009 07:27 

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
Info21 писал(а):
Geniepro писал(а):
Так что это просто оптимизация.
А вы тут сразу -- "не умеешь, не умеешь!!!" :lol: :lol: :lol:
И оптимизировать тоже не умеет.

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Решето Эратосфена.
СообщениеДобавлено: Среда, 21 Октябрь, 2009 08:05 

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Решето Эратосфена.
СообщениеДобавлено: Среда, 21 Октябрь, 2009 09:56 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8196
Откуда: Троицк, Москва
Geniepro писал(а):
На русском форуме задаёшь вопрос и тебе долго объясняют какой ты мудак...
Вам пенять можно только на себя.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Решето Эратосфена.
СообщениеДобавлено: Четверг, 22 Октябрь, 2009 11:10 

Зарегистрирован: Среда, 30 Сентябрь, 2009 14:45
Сообщения: 147
Info21 писал(а):
И оптимизировать тоже не умеет.

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

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

К примеру этот цикл можно было изобразить что-нибудь вроде
while ((f = (p % ps[j++])) && (ps[--j]*ps[j++] <= p));
и сказать, что это линейный поиск


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Решето Эратосфена.
СообщениеДобавлено: Четверг, 22 Октябрь, 2009 12:50 

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
Виктор О писал(а):
К примеру этот цикл можно было изобразить что-нибудь вроде
while ((f = (p % ps[j++])) && (ps[--j]*ps[j++] <= p));
и сказать, что это линейный поиск

В обероне такое не изобразишь, а мой сишный код -- просто калька с варианта на КП.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Решето Эратосфена.
СообщениеДобавлено: Четверг, 22 Октябрь, 2009 12:56 

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
Alexey Veselovsky писал(а):
Код:
c++: user  0m2.956s
hs : user  0m6.260s

Нормально.
Если же позарез нужно не медленнее, чем на Си -- перепишите тормозящий кусок на Си и прицепите к основной проге на Хаскелле.
Даром что ли GHC = Хаскелл + Си...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Решето Эратосфена.
СообщениеДобавлено: Пятница, 23 Октябрь, 2009 10:40 

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
Geniepro писал(а):
Alexey Veselovsky писал(а):
Код:
c++: user  0m2.956s
hs : user  0m6.260s

Нормально.
Если же позарез нужно не медленнее, чем на Си -- перепишите тормозящий кусок на Си и прицепите к основной проге на Хаскелле.
Даром что ли GHC = Хаскелл + Си...


Ну, я и говорю что в принципе нормально. Только поправочка -- не Си, а С++. Всё же используется std::vector и индексация идет с проверкой (использовался не operator[], а метод at()).


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 32 ]  На страницу Пред.  1, 2

Часовой пояс: UTC + 3 часа


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

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 0


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

Найти:
cron
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2019, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB