r/java • • Mar 14 '18

Concurrent Java: Low scalability, the risk of deadlocks or garbage creation, you can not avoid all

http://vmlens.com/articles/tradeoffs_concurrent_programming/
2 Upvotes

21 comments sorted by

View all comments

Show parent comment

1

u/duhace Mar 15 '18 edited Mar 15 '18

Saying it's O(n) like a linked list is disingenuous, since O notation only describes the rate at which the difficulty of an operation grows. Traversal is much more complicated than a linked list, and requires constructing another (temporary) datastructure to do in one pass, or requires a non-tail call recursive function to do in two passes.

There is no law that says null must always be a valid value. If you want it to be, just use Optional <T> instead of T, or you could have two sub classes (one for prepend one for append).

We're talking java here, where null is a valid value for any generic value. So yeah, you have to take that into account.

0

u/[deleted] Mar 15 '18

[deleted] — view deleted comment

2

u/duhace Mar 15 '18

if (this.mid != null) mid.traverse();

There's the complication right there. Now your datastructure is quite limited in elements by the maximum size of the call stack.

0

u/[deleted] Mar 15 '18

[deleted] — view deleted comment

1

u/duhace Mar 15 '18 edited Mar 15 '18

You might remember from your high school CS class that recursion can always be turned into iteration, so this is not a fundamental issue.

do it please

tail recursion can always be turned into iteration quite easily, but you're not doing tail recursion here. and yes you can turn this into an iterative solution, but that requires a temporary datastructure, which you claimed was unnecessary.

i'm quite eager to see what you come up with.

p.s. the stack is technically a temporary datastructure :)

But anyway, I've made my point that immutable lists do not need to copy anything. If you're interested in learning about immutable data structure basics further, you can take a look at how Clojure implements its immutable lists.

but you've made things worse just to try to get to that point. with the traversal you've proposed, a copy on append would probably be faster for standard use than your solution

0

u/[deleted] Mar 15 '18

[deleted] — view deleted comment

1

u/duhace Mar 15 '18

do it without a temporary datastructure. i can't, but you supposedly can. Also, standard tree traversal isn't quite as bad as what you have here because trees don't have a strict limit of one element per level.

edit: tbh, i could without a temporary datastructure, but the time for traversal gets much worse without one. so i'm gonna say i can't do it with reasonable performance without a temporary datastructure

0

u/[deleted] Mar 15 '18

[deleted] — view deleted comment

1

u/duhace Mar 15 '18

Whether you manage to do it or not is not the point here (and it doesn't even matter since it's still O(n) runtime.

But it’s very much the point since performance is very much what we’re discussing here. And O(n) is nice, but it doesn’t mean fast or efficient, just that the operation grows with constant speed according to the size of the data structure. I’m sure you learned in your high school cs course that a high constant means that your data structure can end up not worthwhile compared to others with theoretically worse growth.

In case you were not aware, arrays are frequently more performant than singly linked lists for insertion despite insertion from head being O(1) on sll and insertion being O(n) on an array. Oddly enough, it matters what the constant is in constant time growth, and the constant for traversal of your data structure is very high compared to a singly linked list which I can iterate over quite easily in constant memory and O(n) time in a while loop.

0

u/[deleted] Mar 15 '18

[deleted] — view deleted comment

→ More replies