277 reputation
37
bio website
location Bay Area, CA
age
visits member for 2 years, 11 months
seen Nov 14 at 10:31

MSCS student, almost finished!

I enjoy Java and algorithms.


Nov
9
awarded  Good Question
Sep
24
awarded  Autobiographer
Feb
22
awarded  Notable Question
Jan
13
accepted Thoughts on a custom data structure for a node/chain implementation
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
awarded  Editor
Jan
12
revised Thoughts on a custom data structure for a node/chain implementation
deleted 6 characters in body
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
12
asked Thoughts on a custom data structure for a node/chain implementation
Dec
26
awarded  Yearling
Feb
13
awarded  Popular Question
Feb
2
accepted Recommend a text that explains the physical implementation of C (stack, heap, etc)
Jan
21
answered Recommend a text that explains the physical implementation of C (stack, heap, etc)
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.
Jan
11
awarded  Scholar
Jan
11
accepted Were the first assemblers written in machine code?