277 reputation
37
bio website
location Bay Area, CA
age
visits member for 3 years
seen 10 hours ago

Web application developer at Google.

Prior open source work:
www.gpxcreator.com

Click here to learn about recursion!


10h
comment Is every language written in C?
See my similar question here. I highly suggest reading the book I mention in the beginning of that question, as it would get you way beyond the confusion in your question.
Jan
13
comment Thoughts on a custom data structure for a node/chain implementation
No worries. I did some profiling (which probably wasn't 100% accurate), but with the problem sizes I was using it actually showed arraylists being 5-8 times faster than linkedlists... a big difference as you alluded to in the comments higher up. That was definitely news to me, but cache locality does indeed sound like maybe one good explanation.
Jan
13
comment Thoughts on a custom data structure for a node/chain implementation
Yeah, I ended up just going with an arraylist anyway, especially since as I noted in comments below, I have to go through my collection linearly to paint it all on screen anyway. Thanks for your thoughts though. :-)
Jan
12
comment Thoughts on a custom data structure for a node/chain implementation
@sparkleshy Thank you for capitulating to dude's demands. The annoying verbosity was helpful. Another thing which I didn't even think of - as you say, all the the elements will be on screen... which means no matter how I represent them I will already have an O(n) operation when I draw them all on a screen repaint!
Jan
12
comment Thoughts on a custom data structure for a node/chain implementation
Thanks. That seems like a reasonable suggestion. But it still bothers me that with this design, when a waypoint is chosen in the UI, even if we know without a doubt which route it belongs to, the route still will need to walk through its entire linked list from the beginning until it locates this waypoint so that it can insert something before it (please correct me if any of that is wrong). In my solution the waypoint itself (rather than the list) keeps track of its neighbors, so you never have to do O(N) search on a list. Maybe I'm just stubborn, but I'm still tempted to try it this way.
Jan
12
comment Thoughts on a custom data structure for a node/chain implementation
Good point, 2 * O(n) is still O(n). I don't know enough about the specifics of a Java linkedlist or arraylist to know that one would surely be faster or slower, come to think of it. I edited the OP to reflect that.
Jan
12
comment Thoughts on a custom data structure for a node/chain implementation
Yeah, I (the OP) would be curious as well. I can sort of see how circular references can create problems, but I'd think if you design each class well enough you could avoid those problems (i.e. make sure that for every possible way to mutate one class, the other automatically updates to reflect it). I also will admit an ArrayList would probably be fine because it's not like these chains are going to be millions of elements long. But it still irks me to choose an implementation which is less than the most efficient.
Jan
13
comment Were the first assemblers written in machine code?
+1 for the "assembler, you" comment. It's easy to get attached to one definition of a word (i.e. assembler = software) but your comment really puts the obvious back into perspective... that the "assembly process" is just a system/routine, one which easily could be undertaken by a human assembler.