Yep. If you submit it to that branch then I will probably apply it there also.
Created PR for 3.1. And I closed another PR, because I accidentally tried to add all master commits to 3.1 
Merged both. Thanks.
Would it be possible to make a binary search tree or a hashmap to go O(1) for a hashmap and O(log n) for a binary search tree?
Not sure what this question has to do with iterating over a list where you want to iterate over all of the items. Either of those options will be MUCH worse than iterating over an array.
Sorry I guess I skimmed too much, I saw where people were talking about .get() on an array list so I thought this was a searching and sorting type of problem.
Why would it be worse to search over an entire binary search tree in inorder traversal?
Well, thereās more method calls, thereās book keeping, etcā¦ I mean you are either hammering the call stack through code recursion or hammering your own local data structure with garbage in data recursion. You have to have some way to head back up the tree.
ā¦versus an array iteration where there is none of that. The code looks nicer, too.
I can see that it would make sense being that it would be better to use an array because the big O notions are the same so the simpler one would be better. Although if you used a stack data structure wouldnāt it run faster instead of using recursion?
a) no, Javaās call stack is pretty fast. At best it would probably be the same. Data recursion would give you a deeper stack, though and you have more control over it. And now that youāve start dealing with some kind of stack/list class then you are also adding in size checks and āindex out of boundsā checks, array reshuffling, etcā¦ Versus a call stack.
b) it would generate a ton of temporary garbageā¦ the whole point of this thread was to avoid generating garbage in an inner loop.
With a for( Object o : array ) loop in Java, the compiler can bypass a lot of the checks that you get penalized for when doing a regular list.get(i) call in a for(int i = 0; i < list.size(); i++) style loop. Never mind the extra method calls.
Furthermore, hotspot will know exactly what you are doing with a for( Object o : array ) because itās been encoded at the byte code level as an array iteration. It can, if it chooses, unroll, iterate over raw memory, etcā¦ lots more potential. It may do those things with List also but itās a lot more work and I doubt it would ever be as efficient as an array iteration.
Actually, in almost 20 years, I canāt think of a case where Iāve ever used a binary tree in Java. Proper use-cases must be rare. (Oh, yeah, my Quake level viewer didā¦ but thatās because the BSP structure was already built into the level format.)
We are so deeply off topic by now, though.
1 Like
Sorry I am a CS student and I am curious about this stuff, just got done with a data structures and algorithms class. I will no longer bring the thread off topic.