is using system stack (recursion) faster than using ArrayList?

Discussion in 'Java' started by chucky, Aug 5, 2007.

  1. chucky

    chucky Guest

    the task: parse String on dots and create an array of portions:
    input: "part1.part2.part3.part4"
    output: {"part1", "part2", "part3", "part4" }

    One approach is to use a loop and a dynamic structure such as
    ArrayList and in every iteration find the dot and copy the portion to
    the List. In the end, call List.toArray()

    Another is to find the dot, store its index into a local variable and
    proceed by recursion. When recursion returns, store the appropriate
    portion into the resulting array at appropriate index. In the last
    recursive call allocate the resulting array of Strings with the
    accurate length and store the last portion into the last index.

    Can the second approach be faster than the first one?

    Thanks for your suggestions.
     
    chucky, Aug 5, 2007
    #1
    1. Advertising

  2. chucky

    salimk786 Guest

    On Aug 5, 12:02 pm, chucky <> wrote:
    > the task: parse String on dots and create an array of portions:
    > input: "part1.part2.part3.part4"
    > output: {"part1", "part2", "part3", "part4" }
    >
    > One approach is to use a loop and a dynamic structure such as
    > ArrayList and in every iteration find the dot and copy the portion to
    > the List. In the end, call List.toArray()
    >
    > Another is to find the dot, store its index into a local variable and
    > proceed by recursion. When recursion returns, store the appropriate
    > portion into the resulting array at appropriate index. In the last
    > recursive call allocate the resulting array of Strings with the
    > accurate length and store the last portion into the last index.
    >
    > Can the second approach be faster than the first one?
    >
    > Thanks for your suggestions.


    Have you consider using the split function in Strings ?
     
    salimk786, Aug 5, 2007
    #2
    1. Advertising

  3. chucky

    Eric Sosman Guest

    chucky wrote:
    > [...]
    > Can the second approach be faster than the first one?


    Yes, it can be faster.

    A question you didn't ask but perhaps should have:
    "Is the second approach faster than the first one?" The
    answer is "Write it both ways and measure." (Measuring
    can be tricky.)

    A question you didn't ask but *definitely* should
    have: "Is the potential speed improvement worth worrying
    about?" One way to begin thinking about this question is
    to imagine using a Magical Mystery Method that takes zero
    time. How much difference would this infinite improvement
    make to the running time of your program as a whole? The
    answer establishes an upper bound on the amount of time
    you should be willing to spend working on a speedup.

    --
    Eric Sosman
    lid
     
    Eric Sosman, Aug 5, 2007
    #3
  4. chucky

    chucky Guest

    > Have you consider using the split function in Strings ?

    Thank you for promtp reply.
    The fashion I wrote it can be misleading - it looks like I need to
    solve this particular problem. But, actually, I'm interested in more
    general consideration, if using system stack is (or can be) faster
    than using dynamic data structure.

    Using String.split() is certainly the cleanest way. Maybe also the
    fastest one (but I'm in doubt, because it makes use of a regular
    expression, so it has to compile it first).

    I used this example, because I saw the code for it and in the comment
    advocating the use of recursion by achieving speed.
     
    chucky, Aug 5, 2007
    #4
  5. chucky

    Mark Space Guest

    chucky wrote:
    > the task: parse String on dots and create an array of portions:
    > input: "part1.part2.part3.part4"
    > output: {"part1", "part2", "part3", "part4" }
    >
    > One approach is to use a loop and a dynamic structure such as
    > ArrayList and in every iteration find the dot and copy the portion to
    > the List. In the end, call List.toArray()
    >
    > Another is to find the dot, store its index into a local variable and
    > proceed by recursion. When recursion returns, store the appropriate
    > portion into the resulting array at appropriate index. In the last
    > recursive call allocate the resulting array of Strings with the
    > accurate length and store the last portion into the last index.


    One problem is I don't see how recursion helps here. You can count the
    dots and allocate a fixed length array. Then fill the array with
    components. No ArrayList or recursion required.

    So I'm not really sure what sort of problems you are really after.

    In general, I think comparing recursion vs. some sort of fixed
    computation requires you to know how many computations the recursion
    would perform. Recursion can be very fast for low numbers of repeated
    recursion (< 20 or so). But for problems requiring millions of
    recursions, a fixed computation is faster.

    I think you're also ignoring speed up by using correct algorithm. The
    Sieve of Eratosthenes is pretty fast at what it does, and it's neither
    dynamic nor recursive, just a loop.

    So I think the real answer here is: just use the correct algorithm for
    the job. If you aren't sure, ask!
     
    Mark Space, Aug 5, 2007
    #5
    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. Saravanan Rathinavelu

    Iterate through ArrayList using an another ArrayList

    Saravanan Rathinavelu, Aug 16, 2003, in forum: ASP .Net
    Replies:
    3
    Views:
    2,794
    Natty Gur
    Aug 19, 2003
  2. Ohmu

    Faster than recursion

    Ohmu, Aug 30, 2003, in forum: C++
    Replies:
    8
    Views:
    461
    Michiel Salters
    Sep 1, 2003
  3. Arpan

    System DSN Faster Than File DSN!

    Arpan, Jun 26, 2005, in forum: ASP General
    Replies:
    7
    Views:
    292
  4. Ruby Newbie
    Replies:
    8
    Views:
    133
    Marcin Raczkowski
    Sep 19, 2007
  5. Replies:
    8
    Views:
    798
    John Reye
    Apr 26, 2012
Loading...

Share This Page