|
Thanks!
It's good to hear. Some of my discussions have gotten reported (not that they ended up being flagged) because they're "too technical for the lounge" so I'm glad to hear someone who appreciates my posts say so.
I spend a lot of my time thinking about how to solve problems of a technical nature, hence technical problems and solutions are a part of my life, ergo appropriate for the lounge, IMO.
I try to keep the actual articles to the articles, and this more casual, but the line is sometimes fuzzy.
When I was growin' up, I was the smartest kid I knew. Maybe that was just because I didn't know that many kids. All I know is now I feel the opposite.
|
|
|
|
|
Thanks! Please keep up the great work.
The unspoken truth about CP forums. We do have several forums for technical discussions. But the number people lurking around the lounge is far greater than in other forums.
So it's natural to see more replies/conversations here than in other forums.
While a serious technical question might break the rules of the lounge, A discussion on what we have done, some findings and looking for feedback for the same, I feel it's completely legit for the Lounge.
We should have a variety of discussions happening here. The mix is what makes it more lively.
Please keep sharing your technical findings. You could expect more dinos to come out from the cave and roar. Will be looking for it.
|
|
|
|
|
Interesting, I was under the impression that without recursion you can't really work with trees.
modified 20-Oct-19 21:02pm.
|
|
|
|
|
you just need a stack
When I was growin' up, I was the smartest kid I knew. Maybe that was just because I didn't know that many kids. All I know is now I feel the opposite.
|
|
|
|
|
A stack? A stack is the definition of recursion
No?
Edit: ok looked it up.
So you traverse one million items with nested loops. in the worst case csenario that's million times million loops.
modified 20-Oct-19 21:02pm.
|
|
|
|
|
well recursion uses a stack, but not the other way around
in fact, right now, i need to retool a function in my SortedSplayTreeDictionary to use a stack instead of full recursion to do what it's doing, because otherwise my dictionary can only hold between 5k and 10k items
When I was growin' up, I was the smartest kid I knew. Maybe that was just because I didn't know that many kids. All I know is now I feel the opposite.
|
|
|
|
|
As far as I know the only recursive limitation is the call stack, with a balanced tree (binary as a worst case scenario) the number of nodes is 2^depth of tree. 16K elements is 14 calls as far as I remember?
In C# you can do this:
var stackSize = 10000;
Thread thread = new Thread(new ThreadStart(BigRecursion), stackSize);
Thread Class (System.Threading) | Microsoft Docs
modified 20-Oct-19 21:02pm.
|
|
|
|
|
This is a splay tree. Worst case is different because it's doing tree rotations.
Yes, I could increase the stack size but that's not really the proper way to do this - that's like cleaning your carpet with a blowtorch - i mean sure, it gets rid of the filth, but...
but i am tempted. THis is the function i need to make non-recursive:
_Node _Splay(_Node root, TKey key)
{
int c;
if (null==root || 0==(c = _comparer.Compare(root.Key, key)))
return root;
if (0<c)
{
if (null==root.Left)
return root;
c = _comparer.Compare(root.Left.Key, key);
if (0<c)
{
root.Left.Left = _Splay(root.Left.Left, key);
root = _Ror(root);
}
else if (0>c)
{
root.Left.Right = _Splay(root.Left.Right, key);
if (null!=root.Left.Right)
root.Left = _Rol(root.Left);
}
return (null==root.Left) ? root : _Ror(root);
}
else
{
if (null==root.Right)
return root;
c = _comparer.Compare(root.Right.Key, key);
if (0<c)
{
root.Right.Left = _Splay(root.Right.Left, key);
if (null!=root.Right.Left)
root.Right = _Ror(root.Right);
}
else if (0>c)
{
root.Right.Right = _Splay(root.Right.Right, key);
root = _Rol(root);
}
return (null==root.Right ) ? root : _Rol(root);
}
}
=( =( =(
When I was growin' up, I was the smartest kid I knew. Maybe that was just because I didn't know that many kids. All I know is now I feel the opposite.
|
|
|
|
|
You will end up with nested while loops. It will be vastly less efficient:
Inorder Tree Traversal without Recursion - GeeksforGeeks
void inOrder(struct Node *root)
{
stack<Node *> s;
Node *curr = root;
<pre>
while (curr != NULL || s.empty() == false)
{
/* Reach the left most Node of the
curr Node /
while (curr != NULL)
{
/ place pointer to a tree node on
the stack before traversing
the node's left subtree */
s.push(curr);
curr = curr->left;
}
/* Current must be NULL at this point */
curr = s.top();
s.pop();
cout << curr->data << " ";
/* we have visited the node and its
left subtree. Now, it's right
subtree's turn */
curr = curr->right;
} /* end of while */
}
modified 20-Oct-19 21:02pm.
|
|
|
|
|
I'm not so sure that will work because I need to go right left right right left like that.
your solution looks like once it decided on the left path it would stay on the left path.
(Never mind the above, I read the code wrong. Whoops)
Unfortunately what I think i need is a state machine inside a single while loop, which is rough
While loops inside while loops aren't necessarily performance killers. It depends on how much the while loop is executed and in this case it doesn't matter because for every iteration it was making a function call anyway.
No matter what you do, the correct non-recursive implementation will be at least as, or more likely, more efficient than this version.
The reason is you're using less stack overall and doing the exact same number of pass throughs.
When I was growin' up, I was the smartest kid I knew. Maybe that was just because I didn't know that many kids. All I know is now I feel the opposite.
modified 13-Sep-19 14:31pm.
|
|
|
|
|
|
Message Removed
modified 13-Sep-19 9:26am.
|
|
|
|
|
Pique - the French breath is yellow and black! (10)
Sent from my Amstrad PC 1640
Never throw anything away, Griff
Bad command or file name. Bad, bad command! Sit! Stay! Staaaay...
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
|
Hufflepuff?
One of the school houses (I think)
Pique = huff The French = le Breath = puff
Guessing the house colours are yellow and black ...
Whenever you find yourself on the side of the majority, it is time to pause and reflect. - Mark Twain
|
|
|
|
|
Is the correct answer - you are up Monday.
Sent from my Amstrad PC 1640
Never throw anything away, Griff
Bad command or file name. Bad, bad command! Sit! Stay! Staaaay...
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
|
But the same theme:
Have always really rated your pick of two tea-eating ruffians - to start with, anyway! (5, 6)
Real CCC at usual time ...
Sent from my Amstrad PC 1640
Never throw anything away, Griff
Bad command or file name. Bad, bad command! Sit! Stay! Staaaay...
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
|
|
So close!: "Dotty ..."
Sent from my Amstrad PC 1640
Never throw anything away, Griff
Bad command or file name. Bad, bad command! Sit! Stay! Staaaay...
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
|
I really thought I was onto something...
|
|
|
|
|
Or was it "Hairy ..."? I'm getting all confused.
Sent from my Amstrad PC 1640
Never throw anything away, Griff
Bad command or file name. Bad, bad command! Sit! Stay! Staaaay...
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
|
Ah, that's the one character that I've actually heard of!
Whenever you find yourself on the side of the majority, it is time to pause and reflect. - Mark Twain
|
|
|
|
|
That's why I didn't use it as the "official CCC"
Sent from my Amstrad PC 1640
Never throw anything away, Griff
Bad command or file name. Bad, bad command! Sit! Stay! Staaaay...
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
|
Griff - you're a wizard at these things...
This space for rent.
|
|
|
|
|
Nemesea - Sayonara[^]
Deciding on this week's SOTW was hard!
I had a few contestants and the Dutch Nemesea was one of them.
I've been listening their latest album on repeat, which is pretty rare for an entire album!
So I went for Nemesea, but then I had to pick one song.
All songs on the album are good.
I even like the soft songs, like Lion.
I went for Sayonara because it's rather catchy, but I can recommend looking up the entire album on Spotify.
Nemesea started out as gothic metal which fitted perfectly in the Dutch tradition of After Forever, Within Temptation and Epica.
They've strayed from the metal path and have adopted a more poppy melodic rock sound.
The new singer on this album, Sanne Mieloo, also plays in musicals.
Enjoy
|
|
|
|
|
Nemesea sounds great …
but I had only 37 seconds time to listen because someone
opened Pandora's box at my work to please me I suppose,
so I bookmark Nemesea for the weekend …
and my other bookmarks are
- new AILD with TL …
- new Agonist (had no chance to check them yet …)
Cheers,
|
|
|
|