 |
|
|
|
|
|
||
|
|
||
|
|
||
|
|
|
|
|
|
||
|
|
||
|
|
||
|
|
|
|
|
|||||||||||||||||
Add Forum to Favorites | Send Topic To a Friend | View Forum FAQ | Track this topic |
Last Thread Next Thread |
| Balanced binary search tree with a doubly linked list in C |
|
 |
Br1 Member since: 2/7/2002 From: Montevideo, Uruguay |
|||
 Posted - 7/8/2004 10:12:56 AM |
||||
| I don't understand why std::set, std::multiset or boost::indexset wouldn't work? The restriction of uniqueness is easily avoided. |
||||
|
||||
|
Seriema Member since: 6/15/2001 From: Stockholm, Sweden |
|||
 Posted - 7/8/2004 11:34:15 AM |
||||
| The first part was short and good. But I have to agree with Br1, why didn't you use the existing containers? [ ThumbView: Adds thumbnail support for DDS, PCX, TGA and 16 other imagetypes for Windows XP Explorer. ] [ Chocolate peanuts: Brazilian recipe for home made chocolate covered peanuts. Pure coding pleasure. ] |
||||
|
||||
|
HappyDude Member since: 5/31/2000 From: Toronto, Canadaland |
|||
|
Posted - 7/8/2004 5:32:28 PM |
||||
| I may be wrong, but I beleive the implementation discussed in the article is considerably faster than a multimap. Complexity for a sort of multimaps is O( N logN) according to SGI's STL website, whereas the article says that its implementation only has an overhead of O(log N), which is a huge difference. Map-type containers are good if the values you're inserting aren't changing, because it sorts as you insert. But in this case, because they do change, you would need to sort every time. |
||||
|
||||
|
Nerusai Member since: 9/17/2002 |
|||
|
Posted - 7/8/2004 7:41:50 PM |
||||
| I really love how you did everything in detail and that you didn't use the stl container! (Nice for a change, hmmm) Great article! |
||||
|
||||
|
Aprosenf Member since: 5/8/2001 From: USA |
|||
|
Posted - 7/8/2004 9:01:34 PM |
||||
A map/multimap is really just a wrapper for the STL red-black tree implementation. It takes O(log N) time to insert or delete a node, and so it thus takes O(N log N) time to insert N nodes into an empty tree. However, iterating through an STL tree takes *I think* O(N log N) time, whereas this article gives an O(N) traversal time, although a factor of log N is probably insignificant. The code for traversing an STL tree is:void _Inc() {_Lockit _Lk; if (_Right(_Ptr) != _Nil) _Ptr = _Min(_Right(_Ptr)); else {_Nodeptr _P; while (_Ptr == _Right(_P = _Parent(_Ptr))) _Ptr = _P; if (_Right(_Ptr) != _P) _Ptr = _P; }} With similar code for going backwards. |
||||
|
||||
|
Zeu5 Member since: 5/22/2002 From: Italy |
|||
|
Posted - 7/9/2004 3:33:02 AM |
||||
Quote: Iterating through an STL tree takes O(n) time. Tree traversal needs to visitate internal nodes but the complexity remains linear. The requirements of the data structure (as taken from the article) are: 1) It can be traversed quickly (the drawing loop) 2) It is sorted (need the drawing order) 3) Elements in the sorted dataset can change value (y position of sprites can change) 4) It can have duplicates (sprites can be at the same y position) I was thinking that in this specific case a simple linked list would be sufficient: For (1), (3) and (4) the list is ok. For (2) we can sort the entire list before the drawing step with the insertion sort algorithm. This algorithm has a worst case complexity O(n^2) but if the sequence is nearly ordered the expected running time is O(n). From a frame to the next one the sprite list is, with high probability, already ordered since the previous frame, so the cost is only O(n) per frame. Moreover, if you want to avoid an extra list traversal during the drawing step, you can draw the sprites as the sorting algorithm progresses. Well, this is only my opinion. A red/black tree is surely ok for this problem, but I think a list is simpler and works as well. |
||||
|
||||
|
Beer Hunter Member since: 11/22/2000 From: Canberra |
|||
|
Posted - 7/9/2004 5:43:41 AM |
||||
| I was thinking about the complexity of iterating through a normal red–black tree (like most implementations of std::set and std::multiset). It's true that some increments will take more time than others, with the longest ones taking O(log n) time; but I'm pretty confident that the overall complexity is simply O(n). No node is visited more than three times during iteration, so it can't be worse than linear time, right? |
||||
|
||||
|
Beer Hunter Member since: 11/22/2000 From: Canberra |
|||
|
Posted - 7/9/2004 6:20:30 AM |
||||
| I honestly have no idea what most of that says. Can you try to respond in terms of things that most of us can read? ;) |
||||
|
||||
|
Beer Hunter Member since: 11/22/2000 From: Canberra |
|||
|
Posted - 7/9/2004 7:04:21 AM |
||||
Quote:The succession function takes logarithmic time in the worst case. Most iterations don't take quite so long. I'm still pretty confident that the complete walk is O(n), due to my previous argument; but I'm happy to accept that I might be wrong. I'm still hoping that someone will come in and clear this up. :) |
||||
|
||||
|
DigitalDelusion Member since: 10/4/2000 From: Sodertalje, Sweden |
|||
 Posted - 7/9/2004 7:09:32 AM |
||||
| It's quite easy to derive from some know facts, set and multiset have bidirectional iterators, and the standard says in section 24 that iterators in a given category must for all operations in its category perform then in constant (amortized) time, that's why there's not a complexity column listed. So incrementing a bidirectional iterator is (amortized) O(1) doing that 'n' times gives O(n). So theoretical speed is the same, but as always we're hiding multiplicative constants and real world issues, the fact remains though, iteration through STL containers is O(n) |
||||
|
||||
|
s_p_oneil Member since: 11/26/2003 From: Atlanta, GA, United States |
|||
|
Posted - 7/9/2004 2:06:36 PM |
||||
| The stl map classes have O(n) traversal time, but it still takes longer than traversing a list. When traversing a tree without a list, you are guaranteed to never pass over the same node more than 3 times: once going down to the left, once going down to the right, and once going back up to the parent. So the worst-case time is 3*n (the average is probably closer to 2*n). It's not O(n*log(n)) because with a billion nodes, it's still 3*n. (Beer Hunter, was that clear enough?) Although I think this is a good article on red-black trees, there is a better way to sort your list. You have special knowledge about this list, and you can take advantage of that to keep it in a doubly-linked list and keep it sorted in O(n) time. (Darn, Zeu5 just edited his post and stole my thunder. ;-) When you can ensure that a list is ALMOST sorted, a slightly modified version of bubble-sort will run in O(n). Make the routine take one forward pass through the list. When it finds an element out of place, it backs up until it finds the correct place and moves the node. Then it continues where it left off. When the list is already sorted, this takes exactly n steps. When 1 element is 1 position out of place, it takes n+1 steps (and so on). This algorithm's worst-case is still O(n*n). But since frame coherence will ensure that the list order won't change much from one frame to the next (in most frames it won't change at all), the algorithm's average case is O(n). Better yet, it has no fixed multipliers, so it's not 3*n. It also doesn't have the memory or balancing overhead incurred by the tree. Even better, since you already have to iterate through the list to update object positions, you can sort in the same pass and that makes the performance cost negligible. (Extra passes through the list hurt performance, especially with large lists, so don't make it a separate pass.) Let me know if you agree, Sean |
||||
|
||||
|
ProgramMax Member since: 3/26/2000 From: Ohio, USA |
|||
|
Posted - 7/9/2004 4:05:15 PM |
||||
| I dislike the idea of combining data sctructures. Sure you can quickly search using which ever method would be quicker, but the modifying needs to be done to both data structures and thus has the down side of both. If you add an extra level of indirection you could have each RB tree node just maintain a count (so if there are 2 copies of '3' in the list, it will show that). The level of indirection could then maintain which pointers are similar. Or have each node in the tree be a head to a linked list...that way only the first 3 is in the tree but you have both of them referenced in place. Insertion/deletion would probably be quicker due to not having to alter 2 data structures on each move. |
||||
|
||||
|
Anonymous Poster |
|||
Posted - 7/10/2004 10:27:39 AM |
||||
| Well, it's fun, but you can just use a linked list or dynamic array and sort it in O(n) using radix sort, since you actually sort numeric values (integers or floats). Ask google, if you don't know this fastest sorting algorithm (O(n)). Faster than qsort, but not suitable for generic data, such as text strings, and requires some extra memory. |
||||
|
||||
|
s_p_oneil Member since: 11/26/2003 From: Atlanta, GA, United States |
|||
|
Posted - 7/10/2004 9:13:34 PM |
||||
| A radix sort would be much slower than an insertion sort in this case. Even though it's O(n), it requires multiple passes through the list, and each pass would require several nodes to be moved around. If you want 5 digits of precision, you have to make 5 passes through the list, and a bunch of elements will be moved around with each pass. This is 5-15 times slower than 1 pass through the list with very few elements moving at all. (For simple numeric comparisons, moving a node in the list can be more expensive than the comparison itself.) If you need more digits of precision, it's even worse. If you have a case where the list is not almost sorted but a radix sort will work, often a bucket sort will be even faster. Just create a set of ranges for your buckets, dump the elements into the various buckets they fall into, which is O(n) with only 1 pass, then sort the elements in each bucket with something simple. That last sorting step isn't necessary if you don't need very many buckets. (Space partitioning schemes like quad-trees and oct-trees set up the buckets for free.) Also keep in mind that the radix and bucket sorts can work very well for sorting data like strings. If you use a radix sort to sort the first 5-10 characters in the string, an insertion sort should take care of the rest in close to O(n) time (unless there is a lot of repetition at the front of the strings). Sean |
||||
|
||||
|
Anonymous Poster |
|||
Posted - 7/11/2004 6:11:45 AM |
||||
| You don't need to move nodes, you can just store their indices in buckets, resulting in sorted list of indices. Dynamic array is preferred in this case over linked list, because of fast random access using indices. Should work fine for draw order. 5 passes is enough for sorting 32-bit floats or 32-bit signed integers using radix sort, 4 for unsigned. That's one for sign and 4 for each byte, using 256 buckets. And it's easy to make it span less memory, to improve cache usage. Very helpful if you sort large arrays. Of course, it'll be most efficient for a large number of intesively moving nodes. In case of few rarely moving nodes early-reject methods are better. As for strings, I meant radix sort is not for sorting generic data, as qsort is for example. So you won't find it in common libraries etc... |
||||
|
||||
|
SnprBoB86 Member since: 5/29/2001 |
|||
|
Posted - 7/11/2004 7:45:37 PM |
||||
| I may be neive, but judging from the screenshot, this is overkill. Couldn't you simple store the level in a large 2D array and then simply render across from top-left to bottom-right? |
||||
|
||||
|
s_p_oneil Member since: 11/26/2003 From: Atlanta, GA, United States |
|||
|
Posted - 7/12/2004 12:15:16 PM |
||||
| > Couldn't you simple store the level in a large 2D array and then simply render across from top-left to bottom-right? Woops, I had to edit this post because I mis-read it. What you described is simple space-partitioning, which is similar to the bucket sort I mentioned above. There are actually a number of issues with this. First of all, it is limited in size. Second, since you can probably have multiple objects in each bucket, you also have to sort the objects in each bucket. Third (and worst of all), sprites in one bucket can overlap sprites in a neighboring bucket. In that case you can't draw them sorted by which bucket they're in because it will break. You end up having to sort objects between neighboring buckets, which is a major pain. You also have to check to see when an object moves from one bucket to another. If you need space partitioning for something else, it may be worth it. Otherwise, it's much easier (and probably quicker) to just store them in an array and keep it sorted. Sean |
||||
|
||||
|
fillipe Member since: 8/26/2003 |
|||
 Posted - 7/17/2004 12:24:27 PM |
||||
| I might be missing something, but isn't this a case where the simple heap data structure would do the trick you want? You don't need all drawing elements to be totally ordered all the time, you just need to be drawing the currently most prioritary element at any given time (priority being the y-coordinate). The heap maintains the most prioritary element at the top for cost O(logn). Iterating over all elements respecting their priority has cost O(n) and we go for the (not surprising) cost of O(nlogn) for sorting the drawing objects (yes, heapsort). Since the heap can be implemented using any random access container, you get O(n) for traversal and O(1) for indexing. Using the RB-tree is a huge overkill because you don't have the requirement of total ordering and, more, the degeneration into linked list seems unlikely. Keeping the RB property of the tree is too complicated. Keeping a linked list inside of it is even more complicated. -- Andre' Fillipe (bhzkun AT yahoo DOT co DOT jp) |
||||
|
||||
|
apollodude217 Member since: 2/22/2007 From: Athens, GA, United States |
|||
|
Posted - 3/5/2007 1:06:14 PM |
||||
| It just so happens that I have a game programming project due today in which I have to implement a little collision detection, so this issue is rather relevant to me, and I have pondered it very deeply for quite a while now, and here are my thoughts: It would be a little more difficult to implement, but using a threaded RB tree instead of an RB tree _and_ a DLL that share the same nodes would save some space. I think a sorted DLL or array would be better for a simple game, however, as it is MUCH easier to implement. Note that you can do collision detection AND sorting in one swift stroke, so to speak. But which data structure to use? Arrays cut down on space by eliminating the need for next and prev pointers. Plus, using arithmetic to determine indices, you can traverse the array as you would a tree (rootIndex = length / 2, its left child = 1/2 * its index, right child index = 3/2 * its index, watch for special cases, etc.). However, to move an entity X positions in the list, you would have to do 2+X pointer reassignments (O(X) or O(N), whatever), whereas with a DLL, you would have to do 6 pointer reassignments (O(1)). It just depends on how much the sprites move around along the axis of interest. Also, if you do sprite relocation / movement, collision detection, and reordering the list in one "swift stroke", then you have a few substantial problems to work around: 1. If 2 entities move in the same direction, then you might end up with them swapping places and then un-swapping places 2. collision detection gets less accurate 3. traversal of the list / array gets out of order if reording takes place while you're traversing. Because I'm also going to have an array sorted by type of entity (avatar, bullet, alien) for updating purposes, prob. 3 is taken care of. |
||||
|
||||
| All times are ET (US) |
Last Thread Next Thread |
|
