|
I think I figured out how to make binary trees that hold ints more efficient in .NET by storing them as a contiguous packed array of integers, where each 3 elements represents a kind of "tuple". The left of the 3 is the index of the left node, the center of the 3 is the value, and the right of the 3 is the index of the right node. I can save lots of allocations that way, and reordering the tree should be a lot quicker since i don't really have to move everything, just change some indices.
with a separate array for the values it could hold any type.
cool. imma try it.
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.
|
|
|
|
|
I thought this fell into the category of a doubly linked list?
If you could make it simple - how is this different?
| Ravings en masse^ |
|---|
| "The difference between genius and stupidity is that genius has its limits." - Albert Einstein | | "If you are searching for perfection in others, then you seek disappointment. If you seek perfection in yourself, then you will find failure." - Balboos HaGadol Mar 2010 |
|
|
|
|
|
How much different is a double linked list than a binary tree? It really depends on how you build it and use it.
If I treat the first node as a root node (as the center of a tree) and the edges as children it's a tree.
if I treat the first node as the first node of a list, and the edges as siblings, it's a double linked list.
Tell me what I'm missing?
I mean, it *could* be a double linked list. It really depends on whether i wrapped it with IList or IDictionary if you think about it.
Correct me if I'm wrong.
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.
|
|
|
|
|
I really have a hard time understanding how you are thinking.
You may of course traverse a tree from left to right and from right to left, to read the values in one order or the opposite, but that doesn't make it doubly linked. There are neither forwards nor backwards links in the tree, only subtree links.
B-trees (which are usually fare more exciting and useful than binary trees - and far more space efficient!) must have forward links between blocks at the same level, at both index and leaf (data) levels, and I have seen several implementations with backwards links (although they are not strictly required). I guess the same holds for predecessors of B-trees, such as ISAM structures, but you have to dig up some really outdated textbooks to find much about them. Generally speaking, any B-tree variant is an improvement.
What is the advantage of a binary tree? It takes at least one pointer for each value. Leaf nodes "waste" the space for two pointers, and for an unbalanced tree, lots of the internal nodes loose space to a null pointer. Even for a full and perfectly balanced tree (all internal nodes have non-null sons) the space overhead is 1.5 pointer per value.
Balancing a binary treee is rather costly - in particular if three are multiple accessors: For all practical purposes, you must lock the entire tree while you are doing the balancing. That's exactly why B-trees were developed: In a multiuser environment, you can do the balancing locking only a single node at a time.
I see binary trees as useful as a student exercise. When you start handling Real Data in an production environment, you need B-trees.
For small, temporary data within a single thread, you could of course say that locking and balancing of the tree is of no consern. But then you rarely have a need for the tree structure at all. You might as well put the data into a linear array, wasting no space on pointers, and do a binary search for the value you are searching for. In my student days, our professor told us to stop that binary search when the remaining interval was down to 8 values, and switch to a simple sequential search from there - binary search administration is too costly for small intervals. We didn't trust him, but when we tried to set up real tests, we couldn't even show that a breakoff at 16 made sequential search more costly.
One reason to use trees is when you do a huge amount of inserting. With anything but B-trees, you could easily end up with an extremely unbalanced tree. If inserting come in batches, appending them to a separate array in unsorted order, and periodically sorting this new elemnts array with an NlogN method (where N is the number of new elements) before merging them with the full list, which is an O(M) operation where M is the size of the full list, is in most cases far more efficient.
Curiously, I have spent a lot of vacation time this Youle on an old hobby project - a basic driver for a pure FSM implementation of protocols. This requires an efficient implementation of a sparsly populated 3D state transition table. (The main two dimensions are the states and the events, but some table cells have a sequence of alternatives, guarded by predicates to be tested one by one.) I considered several alternatives, from plain 2D dirctly state/event indexed arrays to linked lists to dictionaries (i.e. hash tables). I ended up with dense arrays, with a two-step lookup of index limits for the "inner" array that is sequentially traversed. None of the alternatives come anywhere close to what I ended up with, neither in time performance nor in memory efficiency. It should be noted that the tables are generated, not hand written, but in a rather primitive way; we are not talking about generating LALR tables! (Which, I must admit, I never got a complete understanding of, even though I have been lecturing about them  ).
Hardware has changed a lot over the years, with ever more prefetch and lookahead (whatever the difference is...), caches etc. Often, it causes locality to be essential to performance. Sequential array search is more or less synonymous with locality. Accessing one more element, in index order, is like adding one instruction to a tight loop: It is hardly noticeable on the execution time. Accessing a tree with pointers everywhere both defeats CPU caching (to some degree) and it could trigger a significant amount of hard page faults in environments where physical memory space is scarce. So my vote goes for higher respect for sequential searches through packed arrays
|
|
|
|
|
For the record I've implemented a b-tree here Bee: A Suite of Self-Balancing Binary Tree Based Dictionaries[^]
(It's not just binary trees. but i get into that at the link)
The reason the binary tree is useful to me specifically is I'm trying to speed up an already fast port of lex (flexish tho) to C# - it's called gplex. Unfortunately, it stores things as a binary tree. I don't understand how it's using it well enough to change the underlying data structure, but i can fix this:
class TreeNode
{
int min;
int max;
int value;
TreeNode lKid;
TreeNode rKid;
internal TreeNode(int mn, int mx, int vl)
{
min = mn; max = mx; value = vl;
}
...
}
I didn't write this class. I just don't like lKid or rKid being TreeNode classes. That's crap use of the heap and even though heap is cheap in .net it isn't free. This is for an nfa/dfa lexer. i think it uses both. it can backtrack, but it can also do it without that overhead.
Also in terms of binary trees, you can achieve excellent locality using a splay tree but i find that in almost all cases, the moving the tree around is more costly than what you save by locality.
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.
|
|
|
|
|
How is this better than the old way of storing a tree in an array?
Where node a[i] has the children at a[2i + 1] and a[2i + 2].
Or is there something I don't get again?
|
|
|
|
|
it's not different. that's what i'm talking about. I didn't say it was a new idea. I've used a similar approach in C for other data structures but not binary trees.
I've built a little dictionary class on it so i can perf test against my other binary tree implementation.
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.
|
|
|
|
|
for static or constant trees, this is more efficient, but if the trees change (additions, deletions, change parents, etc) during their life time, the OP's method has an additional level of indirection so that it's more flexible and easier to manage ...
modified 2-Jan-20 15:57pm.
|
|
|
|
|
With a balanced tree, the 2*I, 2*i+1method is better. With a sparse or an unbalanced tree, having pointers is more efficient.
This idea simply replaces pointers with indexes in an array.
Freedom is the freedom to say that two plus two make four. If that is granted, all else follows.
-- 6079 Smith W.
|
|
|
|
|
Long time ago, in my student days, I was engaged as a TA for the freshman "101 Programming" course, with a little above 1000 students. This was in the transition from Fortran to Pascal as the primary programming language. Ssome of the faculties at the Tech U was very conservative: Real Engineers program in Fortran! Pascal is for sisses!
So the course came in two varieties: Students of Chemistry and Construction Engineering learned Fortran, most others learned Pascal programming. The topics were the same, and three out of four homework assignments were identical. For the last one, the Pascal students were to create a linked list and define some operations on it. The Fortran student did something else, I don't remember what.
I was approached by this chemistry girl, good-looking and friendly, but she was a little crossed: She had heard that those Pascal students were learning something that she didn't learn in the Fortran course. Why not? Why couldn't they all learn it? Well... Fortran doensn't have pointers, so it isn't possible. But what are pointers? I gave her a very simple explanation - it is not a value, but it tells you where to find the value. Like this list, you have the three data fields in each record, and a fourth one that tells where the next record is.
I may have said something like "think of memory as large array, and that fourth value is the array index of the next record". I must have, because a week later, this young lady was back, telling that she had obtained a copy of the Pascal homework assignment. Now she had programmed it in Fortran, using array indexes as pointers. It appearently worked, but if I would take a look at it, she would be happy...
That lady certaily neither looked like nor behaved as the stereotype of a top rate engineer, but I have a gut feeling that she had the qualities required (not for "stereotype" but for "top rate" )! I never saw her after that 101 Programming course, so I can't tell for sure, but I am quite sure she has had a successful career.
I guess it is quite obvious why I came to think of this old memory when reading your post.
|
|
|
|
|
uptick for sweetness. 
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.
|
|
|
|
|
I came to the office this morning and my project solution was still open with a few files loaded.
I forgot what I last did, so I hit ctrl-z to see the last changes I made to the files.
I'd rather be phishing!
|
|
|
|
|
I also like that approach, sometimes I will live a compilation error on the bit of code I am working on so it's even easier to find!
|
|
|
|
|
In VS, just add a comment:
It has a "To Do" list it populates from such comments automatically.
I use it to make "fill in the blanks" function and file headers included in my project templates.
"I have no idea what I did, but I'm taking full credit for it." - ThisOldTony
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
|
And that would be fine if my To Do list wasn't already full of "things to do later" 
We are still in early stages of a new project, I (wishfully) expect them to be gone by release.
|
|
|
|
|
Except i use that to mark sections of my code that need improvement.
For me it wouldn't work because my todo list is already in use. 
But that is a neat feature of VS. I *think* you can add your own though. So maybe I should look into that.
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.
|
|
|
|
|
"Tools ... Options ... Environment ... Task List"
Add a name, set the priority, and press "Add".
As many different ones as you need ...
"I have no idea what I did, but I'm taking full credit for it." - ThisOldTony
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
|
aha, thanks
I figured it was buried in the options somewhere. I hadn't looked, but this saves me the trouble. =)
Now I could add // REMINDER
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.
|
|
|
|
|
I take it you pressed ctrl-y immediately afterwards to get the changes back?
“That which can be asserted without evidence, can be dismissed without evidence.”
― Christopher Hitchens
|
|
|
|
|
yup
I'd rather be phishing!
|
|
|
|
|
I worked at home for a bit yesterday. It was a little shocking to see files dated as 1/1/2020. (looks too much like 2000 with slightly blurry vision)
"Go forth into the source" - Neal Morse
|
|
|
|
|
The most impressive thing in this post is that your system has apparently not spontaneously rebooted in...how many days?
You can't possibly be running Windows 10...
|
|
|
|
|
yup, uptime 14 days, 22 hours and change.
uptime (safe for work image).
I'd rather be phishing!
|
|
|
|
|
Interesting
Maximilien wrote: (safe for work image)
with the text in the right column (Most Viral Images)
But I never wave bye bye
|
|
|
|
|
I usually leave with comments on the screen telling me what i did / need to do
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.
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
