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

C

chucky

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

salimk786

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

Eric Sosman

chucky said:
[...]
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.
 
C

chucky

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

Mark Space

chucky said:
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!
 

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

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,906
Latest member
SkinfixSkintag

Latest Threads

Top