OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Пятница, 29 Март, 2024 11:59

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




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

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
А есть ли быстрые реализации оного решета на Haskell'e?

А то то, что я сотворил ни в какие ворота не лезло в плане производительности.


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

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
Когда-то я баловался с этим делом, примерно такие результаты получил:
Код:
                  100000        1000000
Haskell          1.82 sec       47.7 sec
C GCC 3.4.5      0.44 sec       11.3 sec
ComponentPascal  0.65 sec       17.0 sec
Код:
primes'wheel :: [Int]
primes'wheel = 2:3:5:7:filter isPrime'wheel (spin wheel2357 11)
  where
    isPrime'wheel :: Int -> Bool
    isPrime'wheel !x = all (\p -> x `mod` p /= 0) $ takeWhile (\p -> p*p <= x) $ tail primes'wheel

    wheel2357 :: [Int]
    wheel2357 = 2:4:2:4:6:2:6:4:2:4:6:6:2:6:4:2:6:4:6:8:4:2:4:2:
                4:8:6:4:6:2:4:6:2:6:6:4:2:4:6:2:6:4:2:4:2:10:2:10:wheel2357

    spin :: [Int] -> Int -> [Int]
    spin (x:xs) n = n:spin xs (n + x)
Код:
#define maxn 1000000

int ps[maxn];

int primes_c (int n)
{
    int  i = 2, j, p = 5, f;
    ps[0] = 2; ps[1] = 3;
    while (i < n)
    {
        f = 1; j = 1;
        while (f && (ps[j]*ps[j] <= p))
        {
            f = (p % ps[j]);
            j++;
        }
        if (f)
        {
            ps[i] = p;
            i++;
        }
        p += 2;
    }
    return ps[i-1];
}
Код:
MODULE Primes;
IMPORT SL:=StdLog;

CONST nmax = 1000000;
VAR ps : ARRAY nmax OF INTEGER;

PROCEDURE Prime(n : INTEGER) : INTEGER;
VAR i, j, p : INTEGER;
    f : BOOLEAN;
BEGIN
  ps[0] := 2; ps[1] := 3;
  i := 2; p := 5;
  WHILE i < n DO
    f := TRUE;
    j := 1;
    WHILE f & (ps[j]*ps[j] <= p) DO
      f := (p MOD ps[j]) # 0;
      INC(j)
    END;
    IF f THEN
      ps[i] := p;
      INC(i)
    END;
    INC(p,2)
  END;
  RETURN ps[n-1]
END Prime;

PROCEDURE Do*;
BEGIN
  SL.Int(Prime(1000000)); SL.Ln;
END Do;

END Primes.


Последний раз редактировалось Geniepro Вторник, 20 Октябрь, 2009 08:11, всего редактировалось 1 раз.

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

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
А вот версия, которая всего на 8% медленнее лучшей сишной:
Код:
{-# OPTIONS -O2 -optc-O -fbang-patterns #-}
--
-- The Computer Language Shootout
-- http://shootout.alioth.debian.org/
--
-- Contributed by Don Stewart
-- nsieve over an ST monad Bool array
--

import Control.Monad.ST
import Data.Array.ST
import Data.Array.Base
import System
import Control.Monad
import Data.Bits
import Text.Printf

main = do
    n <- getArgs >>= readIO . head :: IO Int
    mapM_ (sieve . (10000 *) . (2 ^)) [n, n-1, n-2]

sieve n = do
   let r = runST (do a <- newArray (2,n) True :: ST s (STUArray s Int Bool)
                     go a n 2 0)
   printf "Primes up to %8d %8d\n" (n::Int) (r::Int) :: IO ()

go !a !m !n !c
    | n == m    = return c
    | otherwise = do
          e <- unsafeRead a n
          if e then let loop !j
                          | j < m     = do
                              x <- unsafeRead a j
                              when x $ unsafeWrite a j False
                              loop (j+n)

                          | otherwise = go a m (n+1) (c+1)
                    in loop (n `shiftL` 1)
               else go a m (n+1) c


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

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Хм, занятно-подозрительное название unsafeRead :) Какой-то прямой доступ к данным в памяти?


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

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8500
Откуда: Троицк, Москва
Не умеет программировать человек.


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

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
Илья Ермаков писал(а):
Хм, занятно-подозрительное название unsafeRead :) Какой-то прямой доступ к данным в памяти?

Это вообще недокументированная функция, как и unsafeWrite. В них нет проверки индекса, которую делают документированные версии перед их вызовом этих низкоуровневых. То есть в данном случае максимальное приближение к Си.


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

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

Кто именно? :lol: Можете привести вариант получше? :wink:


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

Зарегистрирован: Суббота, 10 Ноябрь, 2007 21:28
Сообщения: 584
Откуда: Хабаровск
Geniepro писал(а):
Info21 писал(а):
Не умеет программировать человек.

Кто именно? :lol: Можете привести вариант получше? :wink:


Эратосфен придумал свой алгоритм для того, чтобы избавиться от операций деления и умножения в любом виде. То есть от нахождения остатка тоже надо избавлятся. Там достаточно операций счета количества пройденных чисел. Сейчас кстати у меян идет занятия и на соседней машине мальчишка 9-классник завершает решето без делений. Это не в обиду сказано. Просто использование операций деления в решете достаточно типичная ошибка. Это я не как программист, это я как учитель.


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

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8500
Откуда: Троицк, Москва
vvp писал(а):
Просто использование операций деления в решете достаточно типичная ошибка.
Как и неумение писать циклы.


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

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

Кто именно? :lol: Можете привести вариант получше? :wink:


Вот вариант накиданый по быстрому по описанию с википедии (http://ru.wikipedia.org/wiki/Решето_Эратосфена):
Код:
#include <iostream>
#include <vector>

int main () {
    int n = 0;
    std::cin >> n;
    std::vector<bool> prime (n);
    for (int i=2; i<n; ++i) prime[i]=true;
    for (int i=2; (i*i)<=n; ++i) {
        if (prime[i])
            for (int j=(i*i); j<=n; j+=i)
                prime[j]=false;
    }

    for (int i=0; i<n; ++i) if (prime[i]) std::cout << " " << i;
    std::cout << std::endl;
    return 0;
}


Миллион считает сильно быстрее чем за секунду.

PS. Да, первые два элемента в векторе лишние. И да, можно было написать чуть красивей.


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

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
vvp писал(а):
Эратосфен придумал свой алгоритм для того, чтобы избавиться от операций деления и умножения в любом виде. То есть от нахождения остатка тоже надо избавлятся.
Ну значит у меня не решето Эратосфена вышло... :lol:


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

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

Ну а в циклах-то где проблема? :roll:


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

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
Alexey Veselovsky писал(а):
А то то, что я сотворил ни в какие ворота не лезло в плане производительности.

А что Вы сотворили-то?


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

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Если в цикле возникает "f: BOOLEAN" - флаг в условии, то это значит, что цикл составлен неверно. Эмуляция break через логический флаг. (Излюбленное возражение самоделкиных - "а если я буду без брейков, то мне нужны логические флаги..").


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

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
Илья Ермаков писал(а):
Если в цикле возникает "f: BOOLEAN" - флаг в условии, то это значит, что цикл составлен неверно. Эмуляция break через логический флаг.

Вы имеете в виду этот кусок:
Код:
    f := TRUE;
    j := 1;
    WHILE f & (ps[j]*ps[j] <= p) DO
      f := (p MOD ps[j]) # 0;
      INC(j)
    END;
    IF f THEN
      ps[i] := p;
      INC(i)
    END;
Да, помню это место. Вначале так не было, приходилось дважды вычислять выражение (p MOD ps[j]) # 0, а так как оптимизатора в компиляторе BB нет, то это замедляло выполнение на 20%. Так что это просто оптимизация.
А вы тут сразу -- "не умеешь, не умеешь!!!" :lol: :lol: :lol:


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

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Ну да, правда.


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

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

А что Вы сотворили-то?


Вот такой вот ужоз:

Код:
prime' n = loop1 (listArray (2,n) (repeat True)) 2 n
           where
               loop1 arr i n | (i*i)>n  = arr
               loop1 arr i n | (arr ! i)= loop1 (loop2 arr (i*i) i n) (i+1) n
               loop1 arr i n            = loop1 arr (i+1) n
               loop2 arr j i n | j<=n = loop2 (arr//[(j,False)]) (j+i) i n
               loop2 arr j i n        = arr

main = do  s <- getLine
           cout (prime' $ read s) 2 (read s)

cout :: Array Int Bool -> Int -> Int -> IO ()
cout arr i n | i<=n && (arr ! i) = do print i
                                      cout arr (i+1) n
cout arr i n | i<=n = cout arr (i+1) n
cout arr i n        = print "--"


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

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
Alexey Veselovsky писал(а):
Вот такой вот ужоз:

Массивы Array в GHC жутко тормозные, я это тоже замечал...


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

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
Geniepro писал(а):
Alexey Veselovsky писал(а):
Вот такой вот ужоз:

Массивы Array в GHC жутко тормозные, я это тоже замечал...


Не думаю, что если этот же пример собрать каким-нибудь UHC, программа станет работать существенно быстрее ;-)


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

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
А попробуйте STUArray как в том примере с shootout -- может получше будет?


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

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


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

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


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

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