Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > is using system stack (recursion) faster than using ArrayList?

Reply
Thread Tools

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

 
 
chucky
Guest
Posts: n/a
 
      08-05-2007
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.

 
Reply With Quote
 
 
 
 
salimk786
Guest
Posts: n/a
 
      08-05-2007
On Aug 5, 12:02 pm, chucky <(E-Mail Removed)> 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 ?


 
Reply With Quote
 
 
 
 
Eric Sosman
Guest
Posts: n/a
 
      08-05-2007
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
http://www.velocityreviews.com/forums/(E-Mail Removed)lid
 
Reply With Quote
 
chucky
Guest
Posts: n/a
 
      08-05-2007
> 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.

 
Reply With Quote
 
Mark Space
Guest
Posts: n/a
 
      08-05-2007
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!
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Why does std::stack::pop() not throw an exception if the stack is empty? Debajit Adhikary C++ 36 02-10-2011 08:54 PM
C/C++ compilers have one stack for local variables and return addresses and then another stack for array allocations on the stack. Casey Hawthorne C Programming 3 11-01-2009 08:23 PM
stack frame size on linux/solaris of a running application stack Surinder Singh C Programming 1 12-20-2007 01:16 PM
System DSN Faster Than File DSN! Arpan ASP General 7 07-02-2005 04:01 PM
"stack level too deep"... because Threads keep their "starting" stack Sam Roberts Ruby 1 02-11-2005 04:25 AM



Advertisments