Fascinating to see you assemble a java applet in real time! I'm retired from software development and got out just as java was hitting its stride.

I found your site while surfing for fast, high resolution interactive applications running the mandelbrodt set

Hi Fred. I feel I ought to step in and make a comment here - your points are quite correct, but in fairness this video set isn't really about the <i>efficient</i> use of data structures. John's showing new Java users how to draw and interact with a simple app!

The user gets to see John choose a structure which solves the problem in hand (a terribly useful act in its own right). He also gets to show that his first choice of data-structure is too slow (a useful point for a newbie to learn from), and that a refined choice of structure does an adequate job solving the task (making for a pragmatic solution - again useful for a newbie...it is always tricky knowing when to stop tinkering with code to make it 'better').

Whilst more efficient programming choices could have been made, it is the animation and user-interaction components of the video that should be the take-home points.

Of course, we'd welcome a video set discussing the finer points of how to choose the right data structure to solve a tricky problem, given memory/time constraints and the like...that'd also make for a great educational piece for an intermediate Java user. Maybe you'd be interested in sharing your knowledge of the subject?

Hi Fred,

Thanks for the info. I know it's faster to remove from the end of an ArrayList, but it required less typing to change the type of the list (to LinkedList) rather than remove from the end of the list...

Laziness is meant to be a programmer's virtue after all ;^)

I added an updated version of the code to <a href="http://wiki.showmedo.com/index.php?title=JavaMontgomeryAppletSeries#Performance">the wiki</a> thich was roughly how I would have done it, if I was more concerned about speed.

Cheers, John

Hi John,

ArrayList is masssively faster than LinkedList in most situations (including this one) if used appropriately. In this case remove items from the END, not the beginning of the ArrayList -- removing from the front requires copying all elements above down by one for each removal. Removing from the end only changes one index. But the better solution is to never remove elements.

-- Fred

Hi Fred,

Yeah, I am well aware of the inefficiencies of creating the ArrayList each time and could have done better on that respect, but felt that it was important to keep all of the code in sight - which is why I only commented on the fact this may be inefficient.

When I recorded this, I was partially banking on ArrayList simply being "fast enough" on the G5 iMac I was using, but it quickly became apparent that it wasn't - hence the switch mid way through to a LinkedList. It was slightly unintentional, but in the end I figured it was a good example of how using the wrong kind of data structure can have a big impact.

Again with the Java 5/generics, it was partly a desire to keep things a bit simpler, but also the fact that I had not set up Eclipse on that iMac (not my usual dev machine) to use Java 5 yet.

I guess in short I was trying not to sweat the small stuff too much and just get on with demoing something interesting. Glad you basically still liked it. Thanks for the feedback, it's always handy for other people looking at this to get some more input. Maybe you should add a section on code improvements to the wiki page for this series?

cheers, John

Hi John,

I just took a look at your dissolving Mandelbrot program. As usual I liked your style of presentation, and especially that you leave some of the abortive starts in.

However, there is a data structure error so serious as to make your program work best as a counter example. The basic problem is that you remove from the front of an ArrayList rather than the back, which makes the performance O(N) instead of O(1) -- from a trivial constant time to a substantial amount of copying, which aside from its use of the CPU seriously messes with the hardware memory cache.

But the approach of dynamically creating the ArrayList each time is flawed anyway, as you pointed out to some extent. It should be created only once, populated only once, and shuffled only once. Nothing should ever be removed from it.

And finally, it feels a little stale. Java 5 has been out for a while now, and a generic ArrayLists are the norm, at least for teaching materials. And traversing it with the enhanced for loop would be nice.

Despite this technical flaw, I still enjoyed it. I hope you don't find my comments too discouraging, and keep up the good work.

Cheers, Fred