Jump to content
  • Advertisement
Sign in to follow this  
Alundra

[c++] non-recursive way to iterate tree

This topic is 2037 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi all,

Imagine a scene manager who has a root node with children, so it's a tree.

One way is to iterate the tree using recursivity, but perf is not the best.

An alternative is to use a similare code to a showed code in the wxWidgets documentation :

wxTreeItemId FindItemNamed(wxTreeCtrl &tree, const std::wstring &name)
{
	std::stack<wxTreeItemId> items;
	if (tree->GetRootItem().IsOk())
		items.push(tree->GetRootItem());
 
	while (!items.empty())
	{
		wxTreeItemId next = items.top();
		items.pop();
 
		if (next != tree->GetRootItem() && tree->GetItemText(next) == name)
			return next;
 
		wxTreeItemIdValue cookie;
		wxTreeItemId nextChild = tree->GetFirstChild(next, cookie);
		while (nextChild.IsOk())
		{
			items.push(nextChild);
			nextChild = tree->GetNextSibling(nextChild);
		}
	}
 
	return wxTreeItemId();
} 

 

Is this method a good way to handle a tree ?

Thanks

Edited by Alundra

Share this post


Link to post
Share on other sites
Advertisement

This is simply a breadth-first search. It may be breadth-first for multiple reasons.

1. It avoids recursion that leads to stack overflow.

2. It finds the closest node to the root matching the supplied name, which seems to be what would be most useful.

Share this post


Link to post
Share on other sites

That method is functionally identical to recursion, the only difference being that you have to manually manage your own stack, rather than using the machine stack.

 

At best, any speedup will be minimal - the time complexity is still linear in relation to the number of nodes in the tree.

 

What makes you think that recursion is too slow?

Share this post


Link to post
Share on other sites

I have always listen that recursion is slow because of the cache miss.

For a QuickSort algorithm the solution is to have a MaxLevel variables en switch to InsertionSort if MaxLevel is reached.

For a a scene tree the best solution is to use recursion ?

Share this post


Link to post
Share on other sites

I have always listen that recursion is slow because of the cache miss.

No, "recursion is slow" is a false statement. There are situations where recursion might be slow, and then it has nothing to do with cache misses.

For a QuickSort algorithm the solution is to have a MaxLevel variables en switch to InsertionSort if MaxLevel is reached.

That's a solution to a specific problem of QuickSort, and not to a general problem with recursion.

For a a scene tree the best solution is to use recursion ?

Best solution to what?

Share this post


Link to post
Share on other sites

Best solution to what?

To traverse the tree for saving the scene, find an object by name or pointer, update each object and render the scene.

Edited by Alundra

Share this post


Link to post
Share on other sites

Write your code to be clear. If performance is a problem, use a profiler to see where the time is going. After that, if you find that traversing the tree is actually a performance bottleneck, then you can worry about this.

Share this post


Link to post
Share on other sites

That method is functionally identical to recursion, the only difference being that you have to manually manage your own stack, rather than using the machine stack.

 

At best, any speedup will be minimal - the time complexity is still linear in relation to the number of nodes in the tree.

 

What makes you think that recursion is too slow?

 

It might be worthwhile to mention that the heap usually is a lot bigger than the stack which alows for deeper traversal so both solutions are not exactly identical.

It is very likely that this won't be a limiting factor though.

 

 

About performance:

Always profile and benchmark.

If it's not too slow you don't have to care.

Otherwise it might be possible that std::stack is implemented as some kind of list with nodes allocated one by one which might lead to more cache misses than a contiguous block of stack memory which the recursive version would use.

Share this post


Link to post
Share on other sites

To traverse the tree for saving the scene, find an object by name or pointer, update each object and render the scene.

If you want to avoid cache misses when traversing a tree, then make sure that the tree's elements are stored contiguously in memory, in the order that they will be traversed. That way, it's the same as iterating through a linear array.

 

If the operation that you need to perform is "for each object", then you shouldn't even be using a tree in the first place, you should just have an array.

 

If the operation is "find object by name", then you want a hash map from names to object-pointers.

Share this post


Link to post
Share on other sites

Otherwise it might be possible that std::stack is implemented as some kind of list with nodes allocated one by one which might lead to more cache misses than a contiguous block of stack memory which the recursive version would use.

 

I don't think that can happen: By default std::stack uses std::deque as its underlying container (std::stack is not a container, but a container adaptor). There are multiple possible implementations of std::deque, but they won't be one-node-per-item implementations because of the performance guarantees (O(1) random access iterators).

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!