Solving simple mathematical equation solving speed

Discussion in 'Java' started by Lionel, Jun 21, 2008.

  1. Lionel

    Lionel Guest

    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.
     
    Lionel, Jun 21, 2008
    #1
    1. Advertising

  2. Lionel

    Arne Vajhøj Guest

    Lionel wrote:
    > 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
     
    Arne Vajhøj, Jun 21, 2008
    #2
    1. Advertising

  3. On Jun 21, 12:28 pm, Lionel <> wrote:
    ...
    > 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?
    <http://www.singularsys.com/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?


    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>

    --
    Andrew Thompson
    http://pscode.org/
     
    Andrew Thompson, Jun 21, 2008
    #3
  4. Lionel

    Stefan Ram Guest

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


    The following example page shows how to evaluate expressions
    with the compiler API.

    http://www.purl.org/stefan_ram/pub/evaluating-expressions-with-java

    (It uses disk-based compilation. There also is an option to
    compile in memory, which is not shown on that page.)
     
    Stefan Ram, Jun 21, 2008
    #4
  5. Lionel

    Roedy Green Guest

    On Sat, 21 Jun 2008 12:28:12 +1000, Lionel <> wrote,
    quoted or indirectly quoted someone who said :

    >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
    --

    Roedy Green Canadian Mind Products
    The Java Glossary
    http://mindprod.com
     
    Roedy Green, Jun 21, 2008
    #5
  6. On Jun 21, 1:00 pm, (Stefan Ram) wrote:
    ...
    >   (...There also is an option to
    >   compile in memory, which is not shown on that page.)


    For 'in memory' compilation, see..
    <http://forum.java.sun.com/thread.jspa?threadID=5305018>

    (But in case anybody is wonderring. No, it
    cannot be achieved within a sandbox, despite
    getting the code directly from a text area.)

    --
    Andrew Thompson
    http://pscode.org/
     
    Andrew Thompson, Jun 21, 2008
    #6
  7. In article
    <>,
    Andrew Thompson <> wrote:

    > On Jun 21, 12:28 pm, Lionel <> wrote:
    > [...]
    > > 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>


    As Andrew & Stefan suggest, using the compiler will definitely be
    faster, but version 1.6 is required. If JEP is too slow or you need
    backward compatibility or your syntax is unique, writing your own
    recursive descent parser isn't hard:

    <http://home.woh.rr.com/jbmatthews/java/calc.html>

    --
    John B. Matthews
    trashgod at gmail dot com
    home dot woh dot rr dot com slash jbmatthews
     
    John B. Matthews, Jun 21, 2008
    #7
  8. Lionel

    Roedy Green Guest

    On Sat, 21 Jun 2008 18:31:22 +0100, "Daniel Dyer" <"You don't need
    it"> wrote, quoted or indirectly quoted someone who said :

    >Alternatively, you could use ANTLR (http://www.antlr.og) to generate a
    >parser. In fact, the book "The Definitive ANTLR Reference" by Terrence
    >Parr has an example of a mathematical expression parser and even extends
    >it to compile to Java bytecode using Jasmin
    >(http://jasmin.sourceforge.net/). This approach will work without
    >requiring the Compiler API from Java 6.


    or any of the other parser generators, see
    http://mindprod.com/jgloss/parser.html
    --

    Roedy Green Canadian Mind Products
    The Java Glossary
    http://mindprod.com
     
    Roedy Green, Jun 21, 2008
    #8
  9. Lionel

    Lionel Guest

    Lionel wrote:
    > 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.
     
    Lionel, Jun 22, 2008
    #9
  10. Lionel

    Roedy Green Guest

    On Sun, 22 Jun 2008 09:09:57 +1000, Lionel <> wrote,
    quoted or indirectly quoted someone who said :

    >. 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.
    --

    Roedy Green Canadian Mind Products
    The Java Glossary
    http://mindprod.com
     
    Roedy Green, Jun 22, 2008
    #10
  11. Lionel

    none Guest

    Roedy Green wrote:
    > On Sun, 22 Jun 2008 09:09:57 +1000, Lionel <> wrote,
    > quoted or indirectly quoted someone who said :
    >
    >> . 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.



    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.
     
    none, Jun 22, 2008
    #11
  12. In article <485d8a46$>, Lionel <>
    wrote:

    > Lionel wrote:
    > > 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>

    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.

    --
    John B. Matthews
    trashgod at gmail dot com
    home dot woh dot rr dot com slash jbmatthews
     
    John B. Matthews, Jun 22, 2008
    #12
  13. none wrote:
    > Roedy Green wrote:
    >> On Sun, 22 Jun 2008 09:09:57 +1000, Lionel <> wrote,
    >> quoted or indirectly quoted someone who said :
    >>
    >>> . 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.

    >
    >
    > 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
     
    Patricia Shanahan, Jun 22, 2008
    #13
  14. Lionel

    none Guest

    Patricia Shanahan wrote:
    > none wrote:
    >> Roedy Green wrote:
    >>> On Sun, 22 Jun 2008 09:09:57 +1000, Lionel <> wrote,
    >>> quoted or indirectly quoted someone who said :
    >>>
    >>>> . 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.

    >>
    >>
    >> 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.


    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.
     
    none, Jun 23, 2008
    #14
  15. Lionel

    none Guest

    John B. Matthews wrote:
    > In article <485d8a46$>, Lionel <>
    > wrote:
    >
    >> Lionel wrote:
    >>> 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.


    My thoughts exactly.

    Cheers

    Lionel.
     
    none, Jun 23, 2008
    #15
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. greg.smith

    solving differential equation

    greg.smith, Sep 22, 2003, in forum: C Programming
    Replies:
    3
    Views:
    447
    Bigdakine
    Sep 24, 2003
  2. TG

    solving equation system

    TG, Jul 17, 2006, in forum: Python
    Replies:
    9
    Views:
    387
    Carl Banks
    Jul 18, 2006
  3. Avi
    Replies:
    6
    Views:
    530
    James Kanze
    May 14, 2008
  4. dmitrey
    Replies:
    0
    Views:
    759
    dmitrey
    Oct 25, 2009
  5. Carlos
    Replies:
    6
    Views:
    701
    Gerhard Hoffmann
    Dec 9, 2012
Loading...

Share This Page