Solving simple mathematical equation solving speed

L

Lionel

Hi all,

I have an equation that gets executing many thousands of times by an
algorithm. When I it is written in code the algorithm is quite fast.
However, I want the user to be able to define the equation themselves,
to solve it this way I use java expression parser (JEP).

For a test example, the algorithm using the hard coded version runs in
about 2 seconds, but using JEP, it takes in the order of 50 seconds! The
expression is only parsed once by JEP, but evaluated many times with
different values.

The expression I'm using looks like: A - (B / C) * D

Does anyone know if such a time difference is expected, and secondly, a
possible faster way of doing this?

Thanks

Lionel.
 
A

Arne Vajhøj

Lionel said:
I have an equation that gets executing many thousands of times by an
algorithm. When I it is written in code the algorithm is quite fast.
However, I want the user to be able to define the equation themselves,
to solve it this way I use java expression parser (JEP).

For a test example, the algorithm using the hard coded version runs in
about 2 seconds, but using JEP, it takes in the order of 50 seconds! The
expression is only parsed once by JEP, but evaluated many times with
different values.

The expression I'm using looks like: A - (B / C) * D

Does anyone know if such a time difference is expected, and secondly, a
possible faster way of doing this?

Why not compile a Java class & method on the fly and load it ?

Arne
 
A

Andrew Thompson

I have an equation that gets executing many thousands of times by an
algorithm. When I it is written in code the algorithm is quite fast.
However, I want the user to be able to define the equation themselves,
to solve it this way I use java expression parser (JEP).

This one?
For a test example, the algorithm using the hard coded version runs in
about 2 seconds, but using JEP, it takes in the order of 50 seconds! The
expression is only parsed once by JEP, but evaluated many times with
different values.

The expression I'm using looks like: A - (B / C) * D

Does anyone know if such a time difference is expected, and secondly, a
possible faster way of doing this?

Use the JavaCompiler* to turn those mathematical
expressions into code within your own app.

*
<http://java.sun.com/javase/6/docs/api/javax/tools/JavaCompiler.html>
 
R

Roedy Green

Does anyone know if such a time difference is expected, and secondly, a
possible faster way of doing this?

A clever parser would generate byte code. Then it potentially could
run just as fast as hand-coded if you let the JET JIT or Sun HotSpot
at it.

Most likely though it is generating a list of delegate calls, so you
have considerable overhead just stepping from operation to operation.

see http://mindprod.com/jgloss/onthefly.html
 
J

John B. Matthews

R

Roedy Green

L

Lionel

Lionel said:
Hi all,

I have an equation that gets executing many thousands of times by an
algorithm. When I it is written in code the algorithm is quite fast.
However, I want the user to be able to define the equation themselves,
to solve it this way I use java expression parser (JEP).

For a test example, the algorithm using the hard coded version runs in
about 2 seconds, but using JEP, it takes in the order of 50 seconds! The
expression is only parsed once by JEP, but evaluated many times with
different values.

The expression I'm using looks like: A - (B / C) * D

Does anyone know if such a time difference is expected, and secondly, a
possible faster way of doing this?

Thanks for the numerous responses. I'm stuck on Java 1.5 for now, so it
appears that rules out a couple of suggestions. I was trying to avoid
the parser generator just because it would mean more code for me to
maintain, but perhaps I will have to bite the bullet and go for it. In
fact I would probably go the recursive descent parser if I take this
line anyway.

I guess that parsing it myself means I need a model of an equation. I'm
sure this has been done to death, so does anyone know of an example
model out there?

Thanks

Lionel.
 
R

Roedy Green

. I was trying to avoid
the parser generator just because it would mean more code for me to
maintain, but perhaps I will have to bite the bullet and go for it. In
fact I would probably go the recursive descent parser if I take this
line anyway.

Don't be frightened. It is duck simple. You will probably find a
grammar already suitable for your equations. It will be a lot more
work to write your own parser.

Hint, if you write your own, read the Aho and Ulman Dragon book then
use recursion. I wrote a parser for Algol-68 declarations back in my
student day in PL/I. It is one of my great life achievements. No
other student was able to do it. I basked in the approval of the
Professor Peck, one of the designers of Algol 68.
 
N

none

Roedy said:
Don't be frightened. It is duck simple. You will probably find a
grammar already suitable for your equations. It will be a lot more
work to write your own parser.


I'm not frightened. I've written numerous grammars, and some recursive
descent parsers. But I have to introduce another set of libraries to do
the parser generation from the grammars, so the recursive descent parser
is more self-contained. It is also a simple problem, so won't be very
complex.

Hint, if you write your own, read the Aho and Ulman Dragon book

Ah yes. I know the dragon book. I've got a newer book which I will refer
to. You're right, it will be worth looking at first.

I just don't want to have to re-invent the wheel. There should be
something out there to do it already that is nice and fast, hence the
reason for my original post. I have googled but not found anything
appropriate yet.

I know it won't take too long to write the recursive descent parser, so
I might end up taking that line.

Thanks

Lionel.
 
J

John B. Matthews

[QUOTE="Lionel said:
Hi all,

I have an equation that gets executing many thousands of times by an
algorithm. When I it is written in code the algorithm is quite fast.
However, I want the user to be able to define the equation themselves,
to solve it this way I use java expression parser (JEP).

For a test example, the algorithm using the hard coded version runs in
about 2 seconds, but using JEP, it takes in the order of 50 seconds! The
expression is only parsed once by JEP, but evaluated many times with
different values.

The expression I'm using looks like: A - (B / C) * D

Does anyone know if such a time difference is expected, and secondly, a
possible faster way of doing this?

Thanks for the numerous responses. I'm stuck on Java 1.5 for now, so it
appears that rules out a couple of suggestions. I was trying to avoid
the parser generator just because it would mean more code for me to
maintain, but perhaps I will have to bite the bullet and go for it. In
fact I would probably go the recursive descent parser if I take this
line anyway.[/QUOTE]

Using 1.6 to invoke the compiler is more reliable, but it's not terribly
hard to do under 1.5 with Runtime.getRuntime().exec(). There's an
excellent example in Frank Felfe's delightful fractal project; see the
IteratorManager.compileTemplate() method:

<http://sourceforge.net/projects/benojt/>
<http://benojt.svn.sourceforge.net/viewvc/benojt/trunk/benojt/src/net/ben
ojt/IteratorManager.java?view=markup>

The alternative using a parser generator is indeed a maintenance
problem. I believe a custom recursive descent parser can be optimized
more readily, assuming the grammar is suitable.
 
P

Patricia Shanahan

none said:
I'm not frightened. I've written numerous grammars, and some recursive
descent parsers. But I have to introduce another set of libraries to do
the parser generation from the grammars, so the recursive descent parser
is more self-contained. It is also a simple problem, so won't be very
complex.
....

I suggest making it an expression-to-Java-source translator, and then
feeding the Java code to javac, if necessary by exec.

The fast results for static code may depend on the JVM's ability to
compile and optimize the bytecode. Its optimization is likely to have
been tested and tuned primarily on bytecode as generated by javac,
rather than arbitrary bytecode. The easiest way to produce bytecode that
is stylistically similer to javac generated bytecode is to use javac to
generate it.

Patricia
 
N

none

Patricia said:
...

I suggest making it an expression-to-Java-source translator, and then
feeding the Java code to javac, if necessary by exec.

The fast results for static code may depend on the JVM's ability to
compile and optimize the bytecode. Its optimization is likely to have
been tested and tuned primarily on bytecode as generated by javac,
rather than arbitrary bytecode. The easiest way to produce bytecode that
is stylistically similer to javac generated bytecode is to use javac to
generate it.

There is another requirement. The equations would need to be loaded
every time the application starts. Does this still make the above
suggestion valid?

I think I will see what the speed is without the compiling step, then,
if it is really necessary I will consider it.

Thanks

Lionel.
 
N

none

John said:
[QUOTE="Lionel said:
Hi all,

I have an equation that gets executing many thousands of times by an
algorithm. When I it is written in code the algorithm is quite fast.
However, I want the user to be able to define the equation themselves,
to solve it this way I use java expression parser (JEP).

For a test example, the algorithm using the hard coded version runs in
about 2 seconds, but using JEP, it takes in the order of 50 seconds! The
expression is only parsed once by JEP, but evaluated many times with
different values.

The expression I'm using looks like: A - (B / C) * D

Does anyone know if such a time difference is expected, and secondly, a
possible faster way of doing this?
Thanks for the numerous responses. I'm stuck on Java 1.5 for now, so it
appears that rules out a couple of suggestions. I was trying to avoid
the parser generator just because it would mean more code for me to
maintain, but perhaps I will have to bite the bullet and go for it. In
fact I would probably go the recursive descent parser if I take this
line anyway.

Using 1.6 to invoke the compiler is more reliable, but it's not terribly
hard to do under 1.5 with Runtime.getRuntime().exec(). There's an
excellent example in Frank Felfe's delightful fractal project; see the
IteratorManager.compileTemplate() method:

<http://sourceforge.net/projects/benojt/>
<http://benojt.svn.sourceforge.net/viewvc/benojt/trunk/benojt/src/net/ben
ojt/IteratorManager.java?view=markup>
Thanks.

The alternative using a parser generator is indeed a maintenance
problem. I believe a custom recursive descent parser can be optimized
more readily, assuming the grammar is suitable.[/QUOTE]

My thoughts exactly.

Cheers

Lionel.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,743
Messages
2,569,478
Members
44,899
Latest member
RodneyMcAu

Latest Threads

Top