View Single Post
Old 02 August 2015, 18:13   #191
Mrs Beanbag
Glastonbridge Software
Mrs Beanbag's Avatar
Join Date: Jan 2012
Location: Edinburgh/Scotland
Posts: 2,202
Originally Posted by Thorham View Post
A plain hash table based string table search doesn't even take twice as much code as a plain string compare version, and that's not exactly a lot to begin with. Especially in C it's not much code at all. The basic hash table is a very simple data structure, after all. That's why it's a bad example for complexity.
Well, it depends how basic. If it is a fixed size and you can guarantee no collisions, it is very simple. If it can dynamically grow, you have to think about different strategies. And just the hash function can range from simple to complex.

I'm embarrassed to say I've never actually implemented a binary tree before Can't possibly complicated, though
A basic (naive) binary search tree is simple enough, but it has worst case performance of O(n^2) if you happen to insert things in alphabetical order, for instance. It's keeping it well balanced that is the dark art. And iterating over it (if you need to do so linearly, like standard template library does... recursion is obviously easy).

Hours? Is that stuff really that heavy?
We can go off topic and discuss this if you like...

actually i'll send you a PM

but the long and the short of it is, yes, it's a pretty heavy calculation if you have a lot of triangles and you need it to be numerically stable (CAD level accuracy, not just visually good enough for games), and we need it to be interactive.
Mrs Beanbag is offline  
Page generated in 0.06724 seconds with 9 queries