|
I'll spare you the details of the context in which Bill's darkside sense of "humor" was unleashed on you rather than recursing until it ran out of stack space in the virtual sandbox of horrors that Bill's brain sometimes does dysfunctional programming [1] in during the winter solstice when his druidic heritage surfaces. As William Blake said:Quote: Rintrah roars and shakes his fires in the burdened air;
Hungry clouds swag on the deep. [2]
I would like to say: SORRY !
And, wish you and your families an auspicious beginning of this Year of the Rat.
[1] in dysfunctional programming every method must apply itself to all its ancestors ad infinitum.
[2] in "The Marriage of Heaven and Hell: The Argument"
«One day it will have to be officially admitted that what we have christened reality is an even greater illusion than the world of dreams.» Salvador Dali
|
|
|
|
|
|
Embrace the dark side, Bill...
".45 ACP - because shooting twice is just silly" - JSOP, 2010
-----
You can never have too much ammo - unless you're swimming, or on fire. - JSOP, 2010
-----
When you pry the gun from my cold dead hands, be careful - the barrel will be very hot. - JSOP, 2013
|
|
|
|
|
It's like he intentionally fell on his own sword. Just not on Christmas!
I, for one, like Roman Numerals.
|
|
|
|
|
To have an error is human, to admit it is wisdom, to apologize for it is brave
M.D.V. 
If something has a solution... Why do we have to worry about?. If it has no solution... For what reason do we have to worry about?
Help me to understand what I'm saying, and I'll explain it better to you
Rating helpful answers is nice, but saying thanks can be even nicer.
|
|
|
|
|
To apologize is a sign of weakness.
".45 ACP - because shooting twice is just silly" - JSOP, 2010
-----
You can never have too much ammo - unless you're swimming, or on fire. - JSOP, 2010
-----
When you pry the gun from my cold dead hands, be careful - the barrel will be very hot. - JSOP, 2013
|
|
|
|
|
Does that mean the brave are weak?
Well, they tend to have shorter lives...
|
|
|
|
|
Quote: To apologize is a sign of weakness.
You may not realize it, but you are quoting John Wayne in the 1949 movie "She wore a yellow ribbon." Much later Gibbs in NCIS also used the expression.
|
|
|
|
|
I do, indeed, realize it.
".45 ACP - because shooting twice is just silly" - JSOP, 2010
-----
You can never have too much ammo - unless you're swimming, or on fire. - JSOP, 2010
-----
When you pry the gun from my cold dead hands, be careful - the barrel will be very hot. - JSOP, 2013
|
|
|
|
|
To act based on your conscience, without regard to how other people may judge you, is: a road to wisdom littered with broken glass the fool must walk on barefoot ?
«One day it will have to be officially admitted that what we have christened reality is an even greater illusion than the world of dreams.» Salvador Dali
|
|
|
|
|
Ignore the wooshing noise; it'll just be a bird, or something.
Probably a vampire.
I wanna be a eunuchs developer! Pass me a bread knife!
|
|
|
|
|
Damn, looks like I missed all the fun. That'll teach me to live in a hole and spend the entire break writing code. Mmmm... code... 
/ravi
|
|
|
|
|
I thought it was dark and very unlike you....and I loved it. I don't think you owe anyone an apology, IMHO.
Cheers.
It's much easier to enjoy the favor of both friend and foe, and not give a damn who's who. -- Lon Milo DuQuette
|
|
|
|
|
Isn't it interesting that we say "owe ... an apology" ... as if there is a debt ?
«One day it will have to be officially admitted that what we have christened reality is an even greater illusion than the world of dreams.» Salvador Dali
|
|
|
|
|
If we start making apologies for being inappropriate in a forum, I'd still be typing this post next year.
The universe is not a safe-space.
Bastard Programmer from Hell 
If you can't read my code, try converting it here[^]
"If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics." -- Some Bell.
|
|
|
|
|
Eddy Vluggen wrote: I'd still be typing this post next year.
I can wait, Eddy ... I'm sure it will be a lollapalooza !
«One day it will have to be officially admitted that what we have christened reality is an even greater illusion than the world of dreams.» Salvador Dali
|
|
|
|
|
BillWoodruff wrote: I can wait, Eddy ... I'm sure it will be a lollapalooza !
Nah, not just for giving my opinion.
Lots of politicians with words that create war; they don't apologize. Also no apologies seen after some beheadings, nor after the assaults here in Europe. So, jest or simple facts, or simply an opinion people don't like - is not coming with an apology here.
Bastard Programmer from Hell
If you can't read my code, try converting it here[^]
"If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics." -- Some Bell.
|
|
|
|
|
To err is human; to forgive is not our policy. 
Your post was sick. I loved it!
Freedom is the freedom to say that two plus two make four. If that is granted, all else follows.
-- 6079 Smith W.
|
|
|
|
|
Daniel Pfeffer wrote: Your post was sick. I loved it!
If only I knew people who loved what I said when I was normal 
«One day it will have to be officially admitted that what we have christened reality is an even greater illusion than the world of dreams.» Salvador Dali
|
|
|
|
|
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?
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
