Using Python for programming algorithms

[Bruno Desthuilliers]

Re: Using Python for programming algorithms

Tim Golden a écrit :

Bruno Desthuilliers wrote:

>2/ actually, all known Python implementations compile to byte-code.

>
In curiosity, did your "actually" mean, in the French sense, "at the
moment" or, in the English sense, "in contrast to something stated
earlier"? Or maybe both?

I mainly intented it to be understood in the English sense - but taking
it the French way would be ok too.

[Roel Schroeven]

Re: Using Python for programming algorithms

Bruno Desthuilliers schreef:

1/ being interpreted or compiled (for whatever definition of these
terms) is not a property of a language, but a property of an
implementation of a language.
>
2/ actually, all known Python implementations compile to byte-code.
>

You keep saying that, and in theory you're right. But I'm still inclined
to disagree with it, since the practical reality is different. Python is
indeed compiled to byte code, but if you compare that byte code with
assembly code you'll see that there's a whole world of difference
between the two, largely because of the dynamical nature of Python. Fact
is that Python was designed from the start to run on a virtual machine,
not on the native hardware.

C OTOH was designed to be compiled to assembly code (or directly to
machine code) and as a result there are no (or virtually) no
implementations that interpret C or compile it to bytecode.

I love Python, but IMHO it's a bit silly to maintain that the fact that
Python compiles to byte code instead of assembly code/machine code is
purely a matter of implementation; on the contrary, I believe it's a
result of its design. I also think that there's a large difference
between byte code and machine code (in Python's case; I haven't looked
at other languages), and that it's a bit silly to try to trivialize that
difference.

--
The saddest aspect of life right now is that science gathers knowledge
faster than society gathers wisdom.
-- Isaac Asimov

Roel Schroeven

[Diez B. Roggisch]

Re: Using Python for programming algorithms

Roel Schroeven wrote:

Bruno Desthuilliers schreef:

>1/ being interpreted or compiled (for whatever definition of these
>terms) is not a property of a language, but a property of an
>implementati on of a language.
>>
>2/ actually, all known Python implementations compile to byte-code.
>>

>
You keep saying that, and in theory you're right. But I'm still inclined
to disagree with it, since the practical reality is different. Python is
indeed compiled to byte code, but if you compare that byte code with
assembly code you'll see that there's a whole world of difference
between the two, largely because of the dynamical nature of Python. Fact
is that Python was designed from the start to run on a virtual machine,
not on the native hardware.
>
C OTOH was designed to be compiled to assembly code (or directly to
machine code) and as a result there are no (or virtually) no
implementations that interpret C or compile it to bytecode.
>
I love Python, but IMHO it's a bit silly to maintain that the fact that
Python compiles to byte code instead of assembly code/machine code is
purely a matter of implementation; on the contrary, I believe it's a
result of its design. I also think that there's a large difference
between byte code and machine code (in Python's case; I haven't looked
at other languages), and that it's a bit silly to try to trivialize that
difference.

I strongly disagree. See the Java which is compiled to bytecode
*explicitly*, jet the JVM-bytecode is closer to Python than to what C++ is
compiled to. But then, it's possible to have JIT-compilers that bring
machine code back into the picture.

And see python + psyco as JIT.

And OTOH see Objective-C and it's runtime for an example of a
machine-code-compiled language that still has huge dynamic runtime parts.

All these blur the image extremely and make Bruno's point: compilation is an
artifact, not some inherent property of a language.

Diez

[Henrique Dante de Almeida]

Re: Using Python for programming algorithms

On May 19, 6:52 am, Bruno Desthuilliers <bruno.
42.desthuilli.. .@websiteburo.i nvalidwrote:

Henrique Dante de Almeida a écrit :
>

On May 17, 7:32 pm, Vicent Giner <vgi...@gmail.c omwrote:

Hello.

>
(snip)

However, it is usually said that Python is not a compiled but
interpreted programming language —I mean, it is not like C, in that
sense.

>
(snip)

 I guess that python is not a good language for that.

(snip)

 My opinion: choose compiled or byte compiled languages.

>
Slightly OT (ie : not talking about computation-heavy alorgithm being
better implemented in C then wrapped in Python - this seems quite
obvious) but just a couple facts:
>
1/ being interpreted or compiled (for whatever definition of these
terms) is not a property of a language, but a property of an
implementation of a language.
>
2/ actually, all known Python implementations compile to byte-code.

Yes, I was actually referring to statically typed JIT-compiled
languages. Sorry about that, blame the beers that entered my digestive
system that night. :-P

[Henrique Dante de Almeida]

Re: Using Python for programming algorithms

On May 19, 7:03 am, Bruno Desthuilliers <bruno.
42.desthuilli.. .@websiteburo.i nvalidwrote:

Vicent Giner a écrit :
>

Hello.

>

I am new to Python. It seems a very interesting language to me. Its
simplicity is very attractive.

>

However, it is usually said that Python is not a compiled but
interpreted programming language

>
cf my answer to you and Henrique on this.
>

I am working on my PhD Thesis, which is about Operations Research,
heuristic algorithms, etc., and I am considering the possibility of
programming all my algorithms in Python.

>

The usual alternative is C,  but I like Python more.

>
Then use it.
>

The main drawbacks I see to using Python are these:

>

* As far as I understand, the fact that Python is not a compiled
language makes it slower than C, when performing huge amounts of
computations within an algorithm or program.

>
In which way is this a problem here ? I thought your thesis was about
algorithm, not about implementation optimisation ? And if it's the
later, then even C might sometimes be too high level - you should drop
to assembly language.
>

* I don't know how likely it is to find libraries in Python related to
my research field.

>
I can't tell but you'd be surprised by the quantity of available Python
libs.
>

* I know Python is a "serious" and mature programming language, of
course. But I do not know if it is seen as "just funny" in a research
context. Is Python considered as a good programming language for
implementing Operations Research algorithms, such as heuristics and
other soft-computing algorithms?

>
Don't know if this answers your question, but it seems that at least
some authors consider it a good choice:http://www.oreilly.com/catalog/9780596529321/
>
All code examples in this books are in Python - very badly written
Python, alas...
>

Maybe this is not the right forum, but maybe you can give me some
hints or tips...

>
Hem... Obviously, most people here will have a little biased, you know ?-)

I agree with what most people here said, that the language doesn't
really matter, etc., but that simply does not apply to the specific
case of optimization research.

The little I know about optimization, even trivial problems may be
hairy problems. Naïve implementations simply don't finish and the
performance bottlenecks are not necessarily in the numeric computation
algorithms (so numpy doesn't help much here). If the guy is doing
research on that, it possible that he will work with thousands (or
millions) of weird constraints.

I'm pretty sure about that: when the algorithms take 4 hours to test
a single execution, you value processor time.

The situation would be simpler if there were good well-known toolkits
for optimization in python (like numpy for matrix operations), but
that's not the case.

[Robin Becker]

Re: Using Python for programming algorithms

Vicent Giner wrote:

Hello.
>
I am new to Python. It seems a very interesting language to me. Its
simplicity is very attractive.
>
However, it is usually said that Python is not a compiled but
interpreted programming language —I mean, it is not like C, in that
sense.

........

>

I programmed several large optimization problems in python. Mostly I used the
old numeric extension for the optimization parts eg vector calculations matrix
inversions etc etc, but I think numpy is used now. Since most of the work was
performed in the C extension we didn't really notice the 'slowness' of python's
interpreter.
--
Robin Becker

[Vicent Giner]

Re: Using Python for programming algorithms

On May 19, 6:11 pm, Henrique Dante de Almeida <hda...@gmail.c om>
wrote:

On May 19, 7:03 am, Bruno Desthuilliers <bruno.
>

I'm pretty sure about that: when the algorithms take 4 hours to test
a single execution, you value processor time.

Yes, of course, but that should mean that I have to do it better, in
the programming step (I would have to re-program or re-implement my
algorithm). And I think the problem would be the same in any other
language, wouldn't it?

The situation would be simpler if there were good well-known toolkits
for optimization in python (like numpy for matrix operations), but
that's not the case.

Are there such toolkits in other languages? I am not sure they exist
in C, for example.

By the way, is it possible (and easy) to call a C function from a
Python program??

[Lou Pecora]

Re: Using Python for programming algorithms

In article <hifYj.43082$4B 6.9014@newsfe14 .ams2>,
Roel Schroeven <rschroev_nospa m_ml@fastmail.f mwrote:

Bruno Desthuilliers schreef:

1/ being interpreted or compiled (for whatever definition of these
terms) is not a property of a language, but a property of an
implementation of a language.

2/ actually, all known Python implementations compile to byte-code.

>
You keep saying that, and in theory you're right. But I'm still inclined
to disagree with it, since the practical reality is different. Python is
indeed compiled to byte code, but if you compare that byte code with
assembly code you'll see that there's a whole world of difference
between the two, largely because of the dynamical nature of Python. Fact
is that Python was designed from the start to run on a virtual machine,
not on the native hardware.
>
C OTOH was designed to be compiled to assembly code (or directly to
machine code) and as a result there are no (or virtually) no
implementations that interpret C or compile it to bytecode.

But how about this C/C++ interpreter. Dr. Dobbs article:
http://www.ddj.com/cpp/184402054. Title and first two paragraphs:

Ch: A C/C++ Interpreter for Script Computing
Interactive computing in C

Ch is a complete C interpreter that supports all language features and
standard libraries of the ISO C90 Standard, but extends C with many
high-level features such as string type and computational arrays as
first-class objects.

For some tasks, C and its compile/ link/execute/debug process are not
productive. As computer hardware becomes cheaper and faster, to be
productive and cost effective, script computing in C/C++ can be an
appealing solution. To this end, we have developed Ch, an embeddable
C/C++ interpreter for cross-platform scripting, shell programming, 2D/3D
plotting, numerical computing, and embedded scripting [1].

--
-- Lou Pecora

[bruno.desthuilliers@gmail.com]

Re: Using Python for programming algorithms

On 19 mai, 15:30, Roel Schroeven <rschroev_nospa m...@fastmail.f m>
wrote:

Bruno Desthuilliers schreef:
>

1/ being interpreted or compiled (for whatever definition of these
terms) is not a property of a language, but a property of an
implementation of a language.

>

2/ actually, all known Python implementations compile to byte-code.

>
You keep saying that, and in theory you're right.

"In theory" ??? Heck, both points above are mere facts. Well, I may
accept that the 2nd one is a bit overgeneralized , since IIRC there's
an experimental Python to javascript "compiler" in Pypy, but...

But I'm still inclined to disagree with it, since the practical reality is different.

Do you mean that how source code written in a language (that is : a
grammar + a syntax) finally become a set of instructions executed by
a CPU depends on the language (I repeat : a grammer + a syntax), and
not on a piece of software turning the source code into something that
can actually be executed by the CPU ? Or that there exists a (working
and usable) implementation of the Python language that does not use an
intermediate byte-code compilation ? If the latest, I'd happly
recognize my error if proven wrong. But on the first point, I'm afraid
that, well, a fact is a fact is a fact.

Python is
indeed compiled to byte code, but if you compare that byte code with
assembly code you'll see that there's a whole world of difference
between the two,

Obviously, yes - at least for all assembly language I've seen so far.
But whoever said otherwise ?

largely because of the dynamical nature of Python. Fact
is that Python was designed from the start to run on a virtual machine,
not on the native hardware.

Nope. The facts are that
1/ Python (the language) has *not* been designed with ease of
implementation of an optimizing native-code compiler in mind, and
2/ CPython (the first and reference implementation) has been designed
to use a byte-code + VM scheme

C OTOH was designed to be compiled to assembly code (or directly to
machine code)

Note quite. C has been designed to make it as easy as possible to
write either a C to assembly or C to native binary code compiler.

and as a result there are no (or virtually) no
implementations that interpret C or compile it to bytecode.

There's at least one (possibly incomplete) C interpreter. FWIW, it
would not be harder (and possibly simpler) to write a byte-code+VM
based C implementation than it is to write CPython, Jython or
IronPython. The point is that it's just useless - C is a (very) low-
level language, and the only reason to use C is that you'll find a
pretty good optimizing native-code compiler on almost any platform -
sometimes even before the CPU physically exists.

I love Python, but IMHO it's a bit silly to maintain that the fact that
Python compiles to byte code instead of assembly code/machine code is
purely a matter of implementation; on the contrary, I believe it's a
result of its design.

There's a very naive belief we saw every here and then here, which is
that "Python would be faster if it was compiled to native code". The
point is that, given Python's (as a language) extrem dynamism,
compiling it to native code wouldn't buy you much in terms of raw
performances. The problem is not with writing a native-code
compiler[1}, but with writing an *optimising* native-code compiler.
FWIW, even Java with it's brain-dead static type-system gained more
from JIT compilation in the VM than from being directly compiled to
native code.

[1] not that I would personnaly be able to do so in a reasonable
amount of time, but given how many talented programmers have been and
are still working on making as fast as possible Python implementions,
it seems obvious that such a thing would already exists if there was
any point working on it.

I also think that there's a large difference
between byte code and machine code

No ? Really ? Now *this* is a scoop, you know ? <g>

(in Python's case; I haven't looked
at other languages), and that it's a bit silly to try to trivialize that
difference.

I'm not trying to "trivialize " anything. I'm just getting fed up with
this "Python is an interpreted and therefore slow language" non-
sense. Python is a language, and as such is neither slow nor fast nor
interpreted nor compiled nor <insert any implementation related stuff
here>. And while CPython is not blazingly fast for computation-heavy
stuff, it's not because it is "interprete d" - which it is not for a
strict definition of "interprete d", but anyway... - but because
*optimizing* execution of an highly dynamic language is nothing,
well, err, trivial.

[bruno.desthuilliers@gmail.com]

Re: Using Python for programming algorithms

On 19 mai, 18:11, Henrique Dante de Almeida <hda...@gmail.c omwrote:

On May 19, 7:03 am, Bruno Desthuilliers <bruno.
>
>
>
42.desthuilli.. .@websiteburo.i nvalidwrote:

Vicent Giner a écrit :

>

Hello.

>

I am new to Python. It seems a very interesting language to me. Its
simplicity is very attractive.

>

However, it is usually said that Python is not a compiled but
interpreted programming language

>

cf my answer to you and Henrique on this.

>

I am working on my PhD Thesis, which is about Operations Research,
heuristic algorithms, etc., and I am considering the possibility of
programming all my algorithms in Python.

>

The usual alternative is C, but I like Python more.

>

Then use it.

>

The main drawbacks I see to using Python are these:

>

* As far as I understand, the fact that Python is not a compiled
language makes it slower than C, when performing huge amounts of
computations within an algorithm or program.

>

In which way is this a problem here ? I thought your thesis was about
algorithm, not about implementation optimisation ? And if it's the
later, then even C might sometimes be too high level - you should drop
to assembly language.

>

* I don't know how likely it is to find libraries in Python related to
my research field.

>

I can't tell but you'd be surprised by the quantity of available Python
libs.

>

* I know Python is a "serious" and mature programming language, of
course. But I do not know if it is seen as "just funny" in a research
context. Is Python considered as a good programming language for
implementing Operations Research algorithms, such as heuristics and
other soft-computing algorithms?

>

Don't know if this answers your question, but it seems that at least
some authors consider it a good choice:http://www.oreilly.com/catalog/9780596529321/

>

All code examples in this books are in Python - very badly written
Python, alas...

>

Maybe this is not the right forum, but maybe you can give me some
hints or tips...

>

Hem... Obviously, most people here will have a little biased, you know ?-)

>
I agree with what most people here said, that the language doesn't
really matter, etc., but that simply does not apply to the specific
case of optimization research.
>
The little I know about optimization, even trivial problems may be
hairy problems. Naïve implementations simply don't finish and the
performance bottlenecks are not necessarily in the numeric computation
algorithms (so numpy doesn't help much here). If the guy is doing
research on that, it possible that he will work with thousands (or
millions) of weird constraints.
>
I'm pretty sure about that: when the algorithms take 4 hours to test
a single execution, you value processor time.

I'm no expert here, but this sounds like a sensible argument to me.

OTHO, if the OP ends up spending more time writing boilerplate code
and fighting with gory implementation details than working on the
algorithm themselves, he might find than relative difference between
two possible algorithms (like one takes 4 hours and the second take 2
1/2 hours, but each took less than one hour to implement) is much more
important than having the first one taking 4 minutes, the second 2 1/2
minutes, and each having take 15 days to write and debug...

The situation would be simpler if there were good well-known toolkits
for optimization in python (like numpy for matrix operations), but
that's not the case.

There's at least Psyco (if you're willing and able to restrict
yourself from using some of the most dynamic parts of Python - which
might not be a problem here). One could also mention stuff like Pyrex
and Cython.

[bruno.desthuilliers@gmail.com]

Re: Using Python for programming algorithms

On 19 mai, 20:07, Vicent Giner <vgi...@gmail.c omwrote:

On May 19, 6:11 pm, Henrique Dante de Almeida <hda...@gmail.c om>
wrote:
>

(snip)

The situation would be simpler if there were good well-known toolkits
for optimization in python (like numpy for matrix operations), but
that's not the case.

>
Are there such toolkits in other languages? I am not sure they exist
in C, for example.

Well... They do - they are called 'C compilers' !-) As Roel Schroven
mentioned - and he is at least partially right on this point - C has
been designed to make optimizing C compiler not to hairy to write.

By the way, is it possible (and easy) to call a C function from a
Python program??

Possible, yes, indeed. Easy depends on your definition of easiness,
but going down to C for computation-heavy performance-critical parts
of a program or library is not that uncommon.

[bruno.desthuilliers@gmail.com]

Re: Using Python for programming algorithms

On 19 mai, 17:53, Henrique Dante de Almeida <hda...@gmail.c omwrote:

(snip)

Yes, I was actually referring to statically typed JIT-compiled
languages. Sorry about that, blame the beers that entered my digestive
system that night. :-P

for beer in beers:
if beer.entered_he nrique_digestiv e_system_last_n ight:
beer.blame()

!-)

[Henrique Dante de Almeida]

Re: Using Python for programming algorithms

On May 19, 3:07 pm, Vicent Giner <vgi...@gmail.c omwrote:

>
Yes, of course, but that should mean that I have to do it better, in
the programming step (I would have to re-program or re-implement my
algorithm). And I think the problem would be the same in any other
language, wouldn't it?

The idea is that a C version of the same program could take, eg. 0,4
hours. But I think we have an authoritative answer here, see Robin
Becker's post (even though he programmed the problem, not the
algorithm). :-)

Are there such toolkits in other languages? I am not sure they exist
in C, for example.

I'm sure there are a lot of toolkits for linear programming (can't
tell about other solvers). glpk is the GNU implementation. It even has
its own built-in language (Mathprog). Someone posted an interesting
link of a python wrapper: "OpenOpt"

http://scipy.org/scipy/scikits/wiki/OpenOpt

It supports many solvers. It may be interesting for you, since there
are some non-linear and "global" problem solvers:

http://scipy.org/scipy/scikits/wiki/OOClasses

By the way, is it possible (and easy) to call a C function from a
Python program??

Yes. The easiest way I know of is using SWIG. People will recommend
you Cython too.

[Henrique Dante de Almeida]

Re: Using Python for programming algorithms

On May 19, 5:25 pm, "bruno.desthuil li...@gmail.com "
<bruno.desthuil li...@gmail.com wrote:

There's at least one (possibly incomplete) C interpreter. FWIW, it
would not be harder (and possibly simpler) to write a byte-code+VM
based C implementation than it is to write CPython, Jython or

You may (right now, readily, without experimental software) compile C
to, for example, llvm bytecode, interpret it in the VM, JIT-compile
it, native-compile it, etc. There's also experimental support for
compiling C to the JVM.

Notice that you usually want to optimize C code, so it will be harder
than writing a python interpreter.

IronPython. The point is that it's just useless - C is a (very) low-

It's not useless. Consider that you may distribute your C application
in byte-code instead of native code and during the installation
process, it is native compiled and optimized exactly to your
architecture (like a better "Gentoo", with the compilation split
between you and the user).

point is that, given Python's (as a language) extrem dynamism,
compiling it to native code wouldn't buy you much in terms of raw
performances. The problem is not with writing a native-code
compiler[1}, but with writing an *optimising* native-code compiler.

That's the job of pypy folks. And they are getting there. They use a
python subset, called RPython:

http://morepypy.blogspot.com/2008/01/rpython-can-be-faster-than-c.html

(note: the test in the site compares garbage collection speed)

BTW, here's how to compile RPython to (optimized) native code:

http://codespeak.net/pypy/dist/pypy/doc/standalone-howto.html

And here is the document that talks about all that:

http://codespeak.net/pypy/dist/pypy/doc/dynamic-language-translation.html

I'm not trying to "trivialize " anything. I'm just getting fed up with
this "Python is an interpreted and therefore slow language" non-
sense.  Python is a language, and as such is neither slow nor fast nor

I'm sorry for creating all those offtopic posts. I feel so ashamed :-
(. Well, not really. :-P

My suggestion was to use code suitable for optimization (not
considering things that you'd need to worry about the way you write
code, like RPython, or psyco). That's all. :-)

[Henrique Dante de Almeida]

Re: Using Python for programming algorithms

On May 19, 5:35 pm, "bruno.desthuil li...@gmail.com "
<bruno.desthuil li...@gmail.com wrote:

 The situation would be simpler if there were good well-known toolkits
for optimization in python (like numpy for matrix operations), but
that's not the case.

>
There's at least Psyco (if you're willing and able to restrict
yourself from using some of the most dynamic parts of Python - which
might not be a problem here).  One could also mention stuff like Pyrex
and Cython.

I meant toolkits for "optimizati on problems", not "code
optimization".