🚀 go-pugleaf

W dniu 25.11.2009 14:05, Marek pisze:

> Zależy mi, aby w aplikacji w Pythonie czas wykonywania algorytmu (akurat
> jest to naiwne wyszukiwanie liczb pierwszych w przedziałach) był
> porównywalny z implementacjami w C. Niestety, dla miliona liczb czas
> wykonania algorytmu w Pythonie jest ok 10x dłuższy.
> Moje pytanie brzmi - czy implementacja tego algorytmu w C, jako
> rozszerzenie Pythona rzeczywiście spowoduje, że będzie on liczony
> szybciej?

Zanim zaczniesz ręcznie pisać rozszerzenie w C, spróbuj użyć Cythona 
[1]. Powinno się obyć bez specjalnych modyfikacji kodu.
Ewentualnie możesz pododawać informacje o typach zmiennych, aby działało 
szybciej. Daj znać, czy pomogło.

[1] http://www.cython.org/

Marek napisał(a):
> Witam,
>
> Zależy mi, aby w aplikacji w Pythonie czas wykonywania algorytmu (akurat
> jest to naiwne wyszukiwanie liczb pierwszych w przedziałach) był
> porównywalny z implementacjami w C. Niestety, dla miliona liczb czas
> wykonania algorytmu w Pythonie jest ok 10x dłuższy.
> Moje pytanie brzmi - czy implementacja tego algorytmu w C, jako
> rozszerzenie Pythona rzeczywiście spowoduje, że będzie on liczony
> szybciej?

Odpowiedz brzmi: bezapelacyjnie tak.
Wszelkie biblioteki obliczeniowe Pythona bazuja na takich
rozszerzeniach.
Chocby sage:
http://www.sagemath.org/doc/reference/sage/rings/arith.html?highlight=primes#sage.rings.arith.primes

RW

Dnia Wed, 25 Nov 2009 06:13:13 -0800, Rob Wolfe napisał(a):

> Odpowiedz brzmi: bezapelacyjnie tak.

Dzięki wielkie za odpowiedź.

Czy macie jakąś podpowiedź jak można z poziomu distutils wpłynąć na opcje 
kompilacji?
W algorytmie używam bibliotek math.h, ktory zawsze linkowałem opcją -lm 
podczas kompilacji gcc/g++. Tutaj jednak nie wiem jak mogę to zmienic, 
albo skomfigurować distutils, aby podlinkował biblioteke.

pozdrawiam

Marek

Marek <marek@octogan.usun.net> writes:

> Dnia Wed, 25 Nov 2009 06:13:13 -0800, Rob Wolfe napisał(a):
>
>> Odpowiedz brzmi: bezapelacyjnie tak.
>
> Dzięki wielkie za odpowiedź.
>
> Czy macie jakąś podpowiedź jak można z poziomu distutils wpłynąć na opcje 
> kompilacji?
> W algorytmie używam bibliotek math.h, ktory zawsze linkowałem opcją -lm 
> podczas kompilacji gcc/g++. Tutaj jednak nie wiem jak mogę to zmienic, 
> albo skomfigurować distutils, aby podlinkował biblioteke.

Przeszukaj grupę, to było wałkowane wielokrotnie, np. tu:
http://groups.google.pl/group/pl.comp.lang.python/browse_thread/thread/59d430dac5ecf762

RW

At Wed, 25 Nov 2009 06:13:13 -0800 (PST), Rob Wolfe wrote:

>
>
> Marek napisał(a):
>> Witam,
>>
>> Zależy mi, aby w aplikacji w Pythonie czas wykonywania algorytmu (akurat
>> jest to naiwne wyszukiwanie liczb pierwszych w przedziałach) był
>> porównywalny z implementacjami w C. Niestety, dla miliona liczb czas
>> wykonania algorytmu w Pythonie jest ok 10x dłuższy.
>> Moje pytanie brzmi - czy implementacja tego algorytmu w C, jako
>> rozszerzenie Pythona rzeczywiście spowoduje, że będzie on liczony
>> szybciej?
>
> Odpowiedz brzmi: bezapelacyjnie tak.
> Wszelkie biblioteki obliczeniowe Pythona bazuja na takich
> rozszerzeniach.
> Chocby sage:
> http://www.sagemath.org/doc/reference/sage/rings/arith.html?highlight=primes#sage.rings.arith.primes

Hint, hint: ktos to juz napisal i zoptymalizowal, nie musisz pisac
swojego...

-- 
Radomir Dopieralski, http://sheep.art.pl

Dnia Thu, 26 Nov 2009 07:18:28 +0000, Radomir Dopieralski napisał(a):

> Hint, hint: ktos to juz napisal i zoptymalizowal, nie musisz pisac
> swojego...

Paradoksalnie chodzi o to, aby algorytm nie był zoptymalizowany i 
odpowiednio długo się liczył dla odpowiednich przedziałów liczb, dlatego 
też chciałem napisać swoje rozszerzenie. Priorytetem jest taki sam czas 
obliczen w porównaniu z implementacją w C. 

Anyway, dzięki za pomoc.

Dnia Wed, 25 Nov 2009 22:58:38 +0100, Rob Wolfe napisał(a):

> Przeszukaj grupę, to było wałkowane wielokrotnie, np. tu:
> http://groups.google.pl/group/pl.comp.lang.python/browse_thread/
thread/59d430dac5ecf762

Widziałem podobne rozwiązania i wstawilem je do setup.py, ale coś 
przeoczylem bo błędy okazalo sye być z powodu literówki w kodzie c.

W każdym bądź razie mam jeszcze mały dziwny problem.
Ten sam kod w ANSI C (działający), przepisany na kod pythonowy wywala się 
na dzieleniu modulo (operator %) dwóch zmiennych int. 
Jestem pewien, że to to, bo po zakomentowaniu wszystko dziala i daje 
wyniki. 
Błędem jest komunikat "Błąd w obliczeniach zmiennoprzecinkowych"
W google nie udało mi się znaleźć za wiele na ten temat.
Jak to można naprawić?

Marek  

Marek <marek@octogan.usun.net> writes:

> Dnia Wed, 25 Nov 2009 22:58:38 +0100, Rob Wolfe napisał(a):

[...]

> W każdym bądź razie mam jeszcze mały dziwny problem.
> Ten sam kod w ANSI C (działający), przepisany na kod pythonowy wywala się 
> na dzieleniu modulo (operator %) dwóch zmiennych int. 
> Jestem pewien, że to to, bo po zakomentowaniu wszystko dziala i daje 
> wyniki. 
> Błędem jest komunikat "Błąd w obliczeniach zmiennoprzecinkowych"
> W google nie udało mi się znaleźć za wiele na ten temat.
> Jak to można naprawić?

Czy aby dobrze pobierasz parametry do funkcji w rozszerzeniu?
Obstawiam, że zamiast int-ów:
PyArg_ParseTuple(args, "ii", &x, &y)

pobierasz double:

PyArg_ParseTuple(args, "dd", &x, &y)

RW

Dnia Thu, 26 Nov 2009 19:11:22 +0100, Rob Wolfe napisał(a):


> 
> Czy aby dobrze pobierasz parametry do funkcji w rozszerzeniu? 
Raczej tak, zreszta te parametry nie mają wtedy znaczenia, bo dzielenie 
modulo wykonuje na intach zadeklarowanych w funkcji.
Oto funkcja, z tego program wykłada się przy dzieleniu modulo.
Gdy się dzieli przez jakąś stałą, nie ważne czy zapisaną w zmiennej czy 
wpisaną na sztywno wszystko działa. Gdzie jest kruczek?  

#v+

#include <Python.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

static PyObject *count (PyObject* self, PyObject* args)
{
    int start,stop;
    int i,x;
    if(!PyArg_ParseTuple(args,"ii",&start,&stop))
        return NULL;

    int sq;
    PyObject *list = PyList_New(0);
    PyObject *po;
    //start counting primes

    for(i=start;i<stop;i++)
    {
        int candidate = (int)i;
        int moduler;
        sq =(int)floor(sqrt(i));
        for(x=0;x<=sq;x++)
        {

	    // ERROR ERROR	
            if(i % x  == 0) break;
        }
        //found prime, add to the list
        if(x>sq) {
            po = PyInt_FromLong((long)i);
            if(PyList_Append(list,po)) 
                return NULL;
        }
    }

    return list;
};

#v-

Marek

Marek <marek@octogan.usun.net> writes:

> Dnia Thu, 26 Nov 2009 19:11:22 +0100, Rob Wolfe napisał(a):
>
>
>> 
>> Czy aby dobrze pobierasz parametry do funkcji w rozszerzeniu? 
> Raczej tak, zreszta te parametry nie mają wtedy znaczenia, bo dzielenie 
> modulo wykonuje na intach zadeklarowanych w funkcji.
> Oto funkcja, z tego program wykłada się przy dzieleniu modulo.
> Gdy się dzieli przez jakąś stałą, nie ważne czy zapisaną w zmiennej czy 
> wpisaną na sztywno wszystko działa. Gdzie jest kruczek?  

Obawiam się, że "i % 0" to nienajlepszy pomysł. ;)

RW

Dnia Thu, 26 Nov 2009 20:05:19 +0100, Rob Wolfe napisał(a):

> 
> Obawiam się, że "i % 0" to nienajlepszy pomysł. ;)

ARGH....

Dzieki ;)

M

Dnia 25.11.2009 Marek <marek@octogan.usun.net> napisał/a:
> Witam,
>
> Zależy mi, aby w aplikacji w Pythonie czas wykonywania algorytmu (akurat 
> jest to naiwne wyszukiwanie liczb pierwszych w przedziałach) był 
> porównywalny z implementacjami w C. Niestety, dla miliona liczb czas 
> wykonania algorytmu w Pythonie jest ok 10x dłuższy.
> Moje pytanie brzmi - czy implementacja tego algorytmu w C, jako 
> rozszerzenie Pythona rzeczywiście spowoduje, że będzie on liczony 
> szybciej? 
>
> pozdrawiam
>
> Marek 

Możliwe, że zadowalający wzrost wydajności da użycie odpowiednich bibliotek
(na przykład numpy?).

Można też napisać implementacje krytycznych miejsc w czystym C, a w Pythonie
używać tego za pomocą ctypes.

-- 
Piotr Husiatyński