Re[21]: Fuzzy и Call-by-callback в ФЯ?
От: naje  
Дата: 10.09.04 08:32
Оценка:
Здравствуйте, ON, Вы писали:

ON>С рекурсией подставляющей значения хранящиеся в самой функции я тоже думал, но там нужно вводить значение nil для всех типов. А если уж оно появится придется делать все {{0,1},nil},nil}....


если мне не изменяет память, это называется flat CPO, можно погуглить и найти много интересного
Re[24]: Сильные стороны функционального программирования
От: Gaperton http://gaperton.livejournal.com
Дата: 10.09.04 15:38
Оценка:
Здравствуйте, WolfHound, Вы писали:

Q>>Кстати, OCaml, думаю, вообще не проиграл бы в производительности, поскольку на него твою программу можно перенести 1 в 1.

WH>Если писать императивно. Кстати напиши. И сравним производительность

Ну зачем сразу императивно. Давай попробуем писать чиста функционально , на чиста функциональном языке Clean.

module fsieve

/*
The Fast Sieve of Eratosthenes.

A sequential and optimized version of the sieve of Eratosthenes.
The program calculates a list of the first NrOfPrime primes.
The result of the program is the NrOfPrimes'th prime.

Strictness annotations have been added because the strictness analyser
is not able to deduce all strictness information. Removal of these !'s
will make the program about 20% slower.
*/

import StdClass; // RWS
import StdInt, StdReal
     
NrOfPrimes :== 100000 
    
//    The sieve algorithm: generate an infinite list of all primes.
Primes::[Int]
Primes = pr where pr = [5 : Sieve 7 4 pr]

Sieve::Int !Int [Int] -> [Int]
Sieve g i prs
    | IsPrime prs g (toInt (sqrt (toReal g)))    =  [g : Sieve` g i prs]
                                                =  Sieve (g + i) (6 - i) prs

Sieve`::Int Int [Int] -> [Int]
Sieve` g i prs =  Sieve (g + i) (6 - i) prs

IsPrime::[Int] !Int Int -> Bool
IsPrime [f:r] pr bd | f>bd             =  True
                    | pr rem f==0    =  False
                                    =  IsPrime r pr bd
                                  
//    Select is used to get the NrOfPrimes'th prime from the infinite list.
Select::[x] Int -> x
Select [f:r] 1 =  f
Select [f:r] n =  Select r (n - 1)

/*    The Start rule: Select the NrOfPrimes'th prime from the list of primes
    generated by Primes.
*/
Start::Int
Start = Select [2, 3 : Primes] NrOfPrimes


А вот это скомпилированный мной .exe
Использует ленивые вычисления. Вычисяет первые 100000 простых чисел. Печатает последнее вычисленое число.
Пишет время выполнения, и время GC. У меня — от 0.29 до 0.31 секунды.
Re[25]: Сильные стороны функционального программирования
От: WolfHound  
Дата: 10.09.04 16:48
Оценка:
Здравствуйте, Gaperton, Вы писали:

G>А вот это скомпилированный мной .exe

G>Использует ленивые вычисления. Вычисяет первые 100000 простых чисел. Печатает последнее вычисленое число.
G>Пишет время выполнения, и время GC. У меня — от 0.29 до 0.31 секунды.
Твой ехешник у меня дает примерно такоеже время.
А это мои результаты
last = 1299709 time = 0.0657921

Вот сама программа. Я ее немного порефакторил.
//Это ограничительная константа(твоя программа раньше сдохнет.)
//На 64х битных платформах ее можно со спкойной совестью еще поднять.
//Но у меня 32х битная машина :(
size_t const max_number=2*1024*1024*1000;
//Этой константой можно играться для тонкой настройки производительности алгоритма
size_t const buf_count=4*1024*1024;
size_t const buf_size=buf_count/CHAR_BIT;

struct prime_numbers
{
    size_t cur_number;
    size_t state;
    size_t offset;
    size_t next_offset;
    std::vector<byte> buf;
    std::vector<size_t> numbers;

    prime_numbers()
        :state(8)
        ,offset(0)
        ,next_offset(buf_count)
        ,buf(buf_size+100)
    {
        numbers.reserve(110*1024*1024);
    }
    bool test_number(size_t n)
    {
        if(n>=next_offset)
        {
            offset=next_offset;
            next_offset+=buf_count;
            std::fill(buf.begin(), buf.end(), 0);
            //вычеркивать начинаем с 7 ибо числа кратные 2, 3, 5 нам всеравно не попадутся :))
            for(std::vector<size_t>::const_iterator i=numbers.begin()+3, e=numbers.end();i!=e;++i)
                remove_number(*i);
        }
        n-=offset;
        size_t pos=n/CHAR_BIT;
        size_t ofs=n%CHAR_BIT;
        return buf[pos]&(1<<ofs);
    }
    void new_number(size_t i)
    {
        numbers.push_back(i);
        remove_number(i);
    }
    void __forceinline remove_number(size_t i)
    {
        size_t m=offset%i;
        size_t n=m?i-m:0;
        for(;n<buf_count;n+=i)
        {
            size_t pos=n/CHAR_BIT;
            size_t ofs=n%CHAR_BIT;
            buf[pos]|=1<<ofs;
        }
    }
    void next()
    {
        size_t i=cur_number;
        switch(state)
        {
            case  8:    new_number(2);  state= 9;   cur_number=2;   return;
            case  9:    new_number(3);  state=10;   cur_number=3;   return;
            case 10:    new_number(5);  state=11;   cur_number=5;   return;
            case 11:    i=1;
            case 0:
            for(;i<max_number;)
            {
                    i+=6;   if(!test_number(i)) {new_number(i); state=1;    cur_number=i;   return;}
            case 1: i+=4;   if(!test_number(i)) {new_number(i); state=2;    cur_number=i;   return;}
            case 2: i+=2;   if(!test_number(i)) {new_number(i); state=3;    cur_number=i;   return;}
            case 3: i+=4;   if(!test_number(i)) {new_number(i); state=4;    cur_number=i;   return;}
            case 4: i+=2;   if(!test_number(i)) {new_number(i); state=5;    cur_number=i;   return;}
            case 5: i+=4;   if(!test_number(i)) {new_number(i); state=6;    cur_number=i;   return;}
            case 6: i+=6;   if(!test_number(i)) {new_number(i); state=7;    cur_number=i;   return;}
            case 7: i+=2;   if(!test_number(i)) {new_number(i); state=0;    cur_number=i;   return;}
            }
            state=12;
            case 12:;
        }
    }
    bool is_end()const
    {
        return state==12;
    }
    size_t cur()const
    {
        return cur_number;
    }
};
int main()
{
    prime_numbers numbers;
    timer.reset();
    for(size_t i=0;i<100000;++i)
    //for(;;)
    {
        numbers.next();
        if(numbers.is_end())
            break;
        //on_prime_number_print(numbers.cur());
    }
    std::cout<<"last = "<<numbers.cur()<<" time = "<<timer.time()<<std::endl;
    return 0;
}


ЗЫ А что будет с твоей программой если задать такой 10000000 лимит?
last = 179424673 time = 7.35434
... << RSDN@Home 1.1.4 rev. 142 >>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[26]: Сильные стороны функционального программирования
От: Gaperton http://gaperton.livejournal.com
Дата: 10.09.04 17:15
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>ЗЫ А что будет с твоей программой если задать такой 10000000 лимит?

WH>last = 179424673 time = 7.35434
WH>

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

Сделаю — напишу Надеюсь сократить проигрыш минимум до 1.5-2х раз (в худшем случае).
Справка: пока моя прога медленнее в 4.5 раза
Re[27]: Сильные стороны функционального программирования
От: WolfHound  
Дата: 10.09.04 18:54
Оценка: +1
Здравствуйте, Gaperton, Вы писали:

G>Ну раз пошла такая пьянка, то мне тоже надо немного порефакторить.

G>А именно, отключить ленивые вычисления,
Дык я какраз их и вводил
G>сохранив итеративный рассчет. Т. е. как это и сделано у тебя.
Это не от хорошей жизни. В исходной
Автор: WolfHound
Дата: 23.06.04
программе этого небыло.

А это
Автор: WolfHound
Дата: 23.06.04
вобще базовый алгоритм.

G>Сделаю — напишу Надеюсь сократить проигрыш минимум до 1.5-2х раз (в худшем случае).

G>Справка: пока моя прога медленнее в 4.5 раза
На ста тысячах. А ты на 10 миллионах запусти.
... << RSDN@Home 1.1.4 rev. 142 >>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[17]: Сильные стороны функционального программирования
От: VladD2 Российская Империя www.nemerle.org
Дата: 10.09.04 18:58
Оценка:
Здравствуйте, Курилка, Вы писали:

К>VladD2, слушай можно нескромный вопрос — у тебя какие-то проблемы или как?


О... Множество. Вот процессор никак достать не могу.

К>Если честно — надоело уже читать вашу перепалку с гапертоном и лойдом читать, причём в последнее время они больше отвечают лишь на твои выпады.


Дык не читай.

К>Может быть есть смысл оставить это и заняться гораздо более конструктивными вещами?


Я это предлагал уже несколько раз. Даже вроде взялись за статьи. Но пока что они недоделаны. Я даже переспросил не нужна ли помощь. Может в интерактиве попробовать... Но видимо интереснее флэйимить...

К>ЗЫ Извиняюсь за интонацию, но уже конкретно достало, ибо топик был не вашей перебранке посвящён всё-таки


Да все в норме. Извиняться, лично тебе незачто.
... << RSDN@Home 1.1.4 beta 2 >>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[20]: Сильные стороны функционального программирования
От: VladD2 Российская Империя www.nemerle.org
Дата: 10.09.04 18:58
Оценка: -1 :)
Здравствуйте, Курилка, Вы писали:

К>Священная война Vlad2 vs. (Gaperton & Lloyd) ?


Не лучше так VladD2 vs. все прогрессивное человечество.
... << RSDN@Home 1.1.4 beta 2 >>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[21]: Сильные стороны функционального программирования
От: VladD2 Российская Империя www.nemerle.org
Дата: 10.09.04 18:58
Оценка: -1
Здравствуйте, INTP_mihoshi, Вы писали:

INT>Никода не спорьте с Владом. Люди могут не замеитить между вами разницы


И не подначивайте его. А то люди могут не заметить и всего остального.
... << RSDN@Home 1.1.4 beta 2 >>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[11]: Сильные стороны функционального программирования
От: VladD2 Российская Империя www.nemerle.org
Дата: 11.09.04 03:25
Оценка:
Здравствуйте, Курилка, Вы писали:

К>Т.е. для каждой такой заплатки ждём новую версию? Тебе нравится такое решение подобных проблем?


Нет. Поэтому мы и делаем R#. Где такие "заплатки" можно будет делать самому.
... << RSDN@Home 1.1.4 beta 2 >>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[27]: Сильные стороны функционального программирования
От: VladD2 Российская Империя www.nemerle.org
Дата: 11.09.04 03:25
Оценка: :)
Здравствуйте, Gaperton, Вы писали:

G>Ну раз пошла такая пьянка, то мне тоже надо немного порефакторить. А именно, отключить ленивые вычисления, сохранив итеративный рассчет. Т. е. как это и сделано у тебя.


Далее остается отключить функциональный стиль ивсе будет в пордяке.
... << RSDN@Home 1.1.4 beta 2 >>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[28]: Сильные стороны функционального программирования
От: Quintanar Россия  
Дата: 11.09.04 07:06
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Здравствуйте, Gaperton, Вы писали:


G>>Ну раз пошла такая пьянка, то мне тоже надо немного порефакторить. А именно, отключить ленивые вычисления, сохранив итеративный рассчет. Т. е. как это и сделано у тебя.


VD>Далее остается отключить функциональный стиль ивсе будет в пордяке.



Чем непонятнее программа, тем она императивнее, но и быстрее. Что нужнее каждый выбирает сам. Сейчас скорость далеко не самая важная составляющая.
Re[29]: Сильные стороны функционального программирования
От: INTP_mihoshi Россия  
Дата: 11.09.04 11:38
Оценка: +1
Здравствуйте, Quintanar, Вы писали:

Q>Чем непонятнее программа, тем она императивнее, но и быстрее. Что нужнее каждый выбирает сам. Сейчас скорость далеко не самая важная составляющая.


Чем более программа оптимизирована, тем она непонятнее, но и быстрее.

Императивность здесь абсолютно нипричем. Кроме того, что обычно императивный код позаоляет точнее управлять конечной машиной.
Re[30]: Сильные стороны функционального программирования
От: Quintanar Россия  
Дата: 11.09.04 12:39
Оценка: +1 -1
Здравствуйте, INTP_mihoshi, Вы писали:

INT> обычно императивный код позаоляет точнее управлять конечной машиной.


Поэтому и причем. Оптимизации связаны, как правило, с "императивнизацией" некоторых частей программы.
Re[29]: Сильные стороны функционального программирования
От: VladD2 Российская Империя www.nemerle.org
Дата: 11.09.04 20:20
Оценка:
Здравствуйте, Quintanar, Вы писали:

Q>Чем непонятнее программа, тем она императивнее, но и быстрее. Что нужнее каждый выбирает сам. Сейчас скорость далеко не самая важная составляющая.


Довольно странно говорить эти слова после демонстрации нечитаемости функционального стиля приведенной выше.
... << RSDN@Home 1.1.4 beta 2 >>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[31]: Сильные стороны функционального программирования
От: VladD2 Российская Империя www.nemerle.org
Дата: 11.09.04 20:20
Оценка:
Здравствуйте, Quintanar, Вы писали:

Q>Здравствуйте, INTP_mihoshi, Вы писали:


INT>> обычно императивный код позаоляет точнее управлять конечной машиной.


Q>Поэтому и причем. Оптимизации связаны, как правило, с "императивнизацией" некоторых частей программы.


Тут уже приводился пример быстрой сортировки разпухший на глазах от мелкой оптимизации. Почему-то императивщины там небыло вовсе. Это как-то объясняется?
... << RSDN@Home 1.1.4 beta 2 >>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[30]: Сильные стороны функционального программирования
От: Quintanar Россия  
Дата: 11.09.04 22:06
Оценка: 1 (1) +3
Здравствуйте, VladD2, Вы писали:

VD>Здравствуйте, Quintanar, Вы писали:


Q>>Чем непонятнее программа, тем она императивнее, но и быстрее. Что нужнее каждый выбирает сам. Сейчас скорость далеко не самая важная составляющая.


VD>Довольно странно говорить эти слова после демонстрации нечитаемости функционального стиля приведенной выше.


Чего там непонятного-то? Любой человек, знающий хоть один функциональный язык программирования, легко поймет, что делает программа. Я Clean не знаю, но все понял.
Тебе запись кажется малопонятной, поскольку ты просто не знаешь, что к чему — интиуиция наработанная на использовании императивных языков здесь не поможет.
Re[12]: Сильные стороны функционального программирования
От: Lloyd Россия  
Дата: 12.09.04 11:49
Оценка:
Здравствуйте, VladD2, Вы писали:

L>>Абалдеть. А Вы иконы со своим ликом еще не пишете?


VD>Ну, поделись своим опытом. Может и попробую.


У меня нет такого опыта.
... << RSDN@Home 1.1.4 @@subversion >>
Re[28]: Сильные стороны функционального программирования
От: Gaperton http://gaperton.livejournal.com
Дата: 12.09.04 17:59
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Здравствуйте, Gaperton, Вы писали:


G>>Ну раз пошла такая пьянка, то мне тоже надо немного порефакторить. А именно, отключить ленивые вычисления, сохранив итеративный рассчет. Т. е. как это и сделано у тебя.


VD>Далее остается отключить функциональный стиль ивсе будет в пордяке.

В Clean нельзя отключить функциональный стиль. Но все равно все будет в порядке.
Re[28]: Сильные стороны функционального программирования
От: Gaperton http://gaperton.livejournal.com
Дата: 12.09.04 18:16
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Здравствуйте, Gaperton, Вы писали:


G>>Ну раз пошла такая пьянка, то мне тоже надо немного порефакторить.

G>>А именно, отключить ленивые вычисления,
WH>Дык я какраз их и вводил
Ни одного ленивого вызова у тебя в программе нет. Приколись? Ты их вводил-вводил, но так и не ввел. Ты ввел итеративный рассчет. А у меня они в проге есть. Их я и собираюсь убрать.

G>>сохранив итеративный рассчет. Т. е. как это и сделано у тебя.

WH>Это не от хорошей жизни. В исходной
Автор: WolfHound
Дата: 23.06.04
программе этого небыло.

А почему жизнь настолько плоха? В чем причина? Неужели в том, что Haskell и Clean оказались шустрее, чем должны?

WH>А это
Автор: WolfHound
Дата: 23.06.04
вобще базовый алгоритм.


G>>Сделаю — напишу Надеюсь сократить проигрыш минимум до 1.5-2х раз (в худшем случае).

G>>Справка: пока моя прога медленнее в 4.5 раза
WH>На ста тысячах. А ты на 10 миллионах запусти.
А зачем? Мой алгоритм имеет асимптотику O(N*sqrt(N)). И время будет расти соответственно. Судя по твоим замерам, ты просто используешь другой алгоритм. Сравнение теряет смысл, если мы не будем использовать одинаковый алгоритм. При одинаковых алгоритмах коэффициент плавать не будет.

Если конечно, речь не идет об очередном втыкании рога в землю на тему "х.. догонишь". Замечу, что у тебя полнее контроль над машиной, и пока ты еще не пользовался ассемблерными вставками и набором инструкций SSE2. Так что резерв для рывка есть.
Re[27]: Особенности компилятора Clean
От: Gaperton http://gaperton.livejournal.com
Дата: 13.09.04 12:26
Оценка:
Здравствуйте, Gaperton, Вы писали:

Порефакторил. Выяснил ряд интересных вещей.
G>Ну раз пошла такая пьянка, то мне тоже надо немного порефакторить. А именно, отключить ленивые вычисления, сохранив итеративный рассчет. Т. е. как это и сделано у тебя.

На ленивом вызове в проге потери никакой нет. Соответственно, убирать его не надо. Это я стормозил — мог бы и сразу додуматься. Потому как 98% времени тратится на проверку IsPrime. А именно, на сканирование списка уже построеных простых чисел.

А вот самое интересное в том, что пробежаться по массиву, как выяснилось, это чуть медленнее, чем по списку . Прикол, однако. Так что оптимизировать дальше не получится. Вот такие дела.

Так что, Wolfhound, можешь праздновать победу!
Ну, пока кто-нибудь не сделал пример на OCaml (или на Sisal, чего мы вряд-ли дождемся).
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.