|
Jörgen Andersson wrote: it'll have to be
Small change. Done.
Also, now building the map only as needed. But still building a full index to start with.
Edit: Code more elegant if I always include Guid.Empty as the top-most parent.
modified 16-Nov-14 22:15pm.
|
|
|
|
|
Jörgen Andersson wrote: human hierarchies with less than a million nodes
Hmmm... I might actually be able to use this at work. Sometimes I have to access Active Directory -- to get information on all 400,000-plus employees and contractors. 
Now, in the tradition of !YAGNI -- let's see if it can be made generic. 
Oh, yes, generic. ![Badger | [badger,badger,badger,badger...]](https://codeproject.global.ssl.fastly.net/script/Forums/Images/badger.gif)
modified 16-Nov-14 23:32pm.
|
|
|
|
|
I don't like YAGNI. I've been forced to follow it by pure necessity, but I don't like it.
Whenever I have time to do a proper solution in beforehand (and thinking it through properly) I tend to not having to redo them, and therefore actually save time in the long run.
PIEBALDconsult wrote: Oh, yes, generic
Me likes generic.
Wrong is evil and must be defeated. - Jeff Ello
Any organization is like a tree full of monkeys. The monkeys on top look down and see a tree full of smiling faces. The monkeys on the bottom look up and see nothing but assholes.
|
|
|
|
|
Jörgen Andersson wrote: I don't like YAGNI.
Nor do I. For the same reason.
|
|
|
|
|
Jörgen Andersson wrote: Me likes generic
Oh, yes! Tested with Guid, SqlGuid, Int32, and String ! All success!
One odd discovery is that SqlGuid is IComparable, but not IComparable<T> .
Another minor problem is that default(T) for all but String yields a usable value. Not a surprise, of course, but disappointing.
P.S. SqlInt32 and SqlString also succeed!
|
|
|
|
|
|
I know. 
You'll notice from my misunderstanding where my thoughts where already then.
I already have a functional implementation doing this, but I thought there might be other ways I haven't thought about.
Wrong is evil and must be defeated. - Jeff Ello
Any organization is like a tree full of monkeys. The monkeys on top look down and see a tree full of smiling faces. The monkeys on the bottom look up and see nothing but assholes.
|
|
|
|
|
It strikes me that this problem MIGHT be solved using the simplest approach, depending on the frequency of this search for LCA relative to adding or removing elements from the tree, and the efforts already taken to maintain some level of balance in the tree. Any work that's needed to maintain the ancestor lists for every node would slow down the (typically very common) task of adding and removing nodes. It could also add up to a very large amount of storage if the tree is sufficiently large.
However, the simple process starting with the two nodes and moving back up the tree a level at a time until a common ancestor is found should be relatively fast (tree depth should be relatively shallow for a balanced tree), and it requires no additional storage per node.
I realize that this question was asked as more of a "fun" thought experiment, but I think that without more information about the specific task at hand, it's not really possible to determine whether you've found "the most efficient way".
Sorry if I sound like a killjoy.
|
|
|
|
|
Michael Sisco wrote: Sorry if I sound like a killjoy.
No probs at all, your comments are valid.
The origin of the thought experiment is from my job where we are working a lot with human hierarchies. They are not changing very much, nor are they necessarily especially balanced.
But since I'm doing this a quite a lot I've "forgotten" about all the other uses.
And you're quite right about that it's impossible to find the best method since different methods are better in different circumstances.
As a general rule I can say that lists are faster for shallow trees and dictionaries are faster for deeper trees.
But that's the methods I've tested, it would be fun to see if someone could come up with something different.
Wrong is evil and must be defeated. - Jeff Ello
Any organization is like a tree full of monkeys. The monkeys on top look down and see a tree full of smiling faces. The monkeys on the bottom look up and see nothing but assholes.
|
|
|
|
|
About a month ago I got a bar code tattoo, I thought it would be funny to ask the cashier to scan me. Apparently I'm a $5.95 box of condoms, I hate my tattoo artist.
New version: WinHeist Version 2.1.0
There's a fine line between crazy and free spirited and it's usually a prescription.
I'm currently unsupervised, I know it freaks me out too but the possibilities are endless.
|
|
|
|
|
Mike Hankey wrote: box of condoms
Can I buy you? 
|
|
|
|
|
Just think about that for a moment - where would you have to stick him?
OTH it would make for very effective birth control.
Life is like a s**t sandwich; the more bread you have, the less s**t you eat.
|
|
|
|
|
PhilLenoir wrote: where would you have to stick him?
Hmmm, never thought of that
|
|
|
|
|
There are worse things; you could have been a $2.95 package of one of these[^].
Software Zen: delete this;
|
|
|
|
|
New York Times, Nov.15: "No. 1 With a Bullet: ‘Nadeshot’ Becomes a Call of Duty Star" [^].
"Matt Haag, a professional video game player, makes close to a million dollars a year sitting in a soft chair smashing buttons.
...
Three years ago, he was flipping burgers at McDonald’s. Today Mr. Haag, 22, skinny and blindingly pale, makes his living playing Call of Duty, a popular series of war games where players run around trying to shoot one another." What was that catchy refrain in that Rod Stewart hit way-back-when ... "some guys have all the luck ... some guys have all the pain" ... was that it ? Well, wait a minute, that's hardly luck that took Matt to the stars ... is it ? I mean he must have had some genes that got him out the starting gate with the reflexes of a hummingbird on PCP with maybe a chaser of OCD, but I am sure he's earned his place in whatever it is that he's ... in.
«The greater the social and cultural distances between people, the more magical the light can spring from their contact» Milan Kundera, "Testaments Trahis"
|
|
|
|
|
It's still a very low percentage shot.
People should not be making decisions based on looking at one-in-a-million successes.
|
|
|
|
|
PIEBALDconsult wrote: making decisions based on looking at one-in-a-million successes
That is an extremely good point and it may even indicate the popularity of failure.
You see, the media pushes these types of "amazing success" stories to the small-minded people in the world. Then, the small-minded people dream of this type of "success" and yet very, very few ever attain it. However, when one out of the 100 million do, the media pushes it.
And thus, the Stupid-Circle revolves.
Meanwhile, if those 100 million or so would focus on Making Something then they would be much more likely to find real success, though possibly not as flashy.
|
|
|
|
|
newton.saber wrote: it may even indicate the popularity of failure.
That is very interesting statement; may I ask you to tell me what you mean by this ?
«The greater the social and cultural distances between people, the more magical the light can spring from their contact» Milan Kundera, "Testaments Trahis"
|
|
|
|
|
BillWoodruff wrote: may I ask you to tell me what you mean by this ?
Very similar to "Get Rich Quick Schemes". Always attempting to break into something that is extremely unlikely, but for the one in a 100 million shot you become terribly rich. Then, the media plays these stories as if they could happen to you. Well, yes, they will happen to 1 out of the 100 million, but what if you are one of the other 100 million?
In that case you spend your entire life dreaming, hoping, and sliding into irrelevancy as the "lightning strike" never happens. So I'm not saying that this kind of success should not be allowed. I'm saying others should wise up and see that it's neat when it happens but definitely "start your day job"*, which many never do.
*similar to the "don't quit your day job".
|
|
|
|
|
At home near Chicago, he has a problem with fans showing up at his house.
Yeah, real soldiers coming home from war have the same problem.
A waste of oxygen.
I wanna be a eunuchs developer! Pass me a bread knife!
|
|
|
|
|
Mark_Wallace wrote: has a problem with fans showing up at his house.
I cannot imagine how empty a person's life must be that s/he has nothing better to do than show up as a fan at such a person's house??
The mindless minions blithely roll on.
|
|
|
|
|
I find the responses here to this story more fantastic than the Life-of-Matt !
Reading about Matt, I am just fascinated: I don't perceive any subliminal message with encoded moralizing content in the story; I don't feel I am reading a parable meant to somehow convey a la Horatio Alger that anybody can do/become/have what Matt does/is/has. And, I certainly don't fantasize about the possible stupidity of unknown other people who are, at this moment, planning to be "just like Matt."
I don't judge Matt; I am sure he is a human being, has a soul, has/had parents, has feelings, has a spiritual life, in his own way seeks love. Who knows what ultimate destiny his life moves in a strange orbit around/towards ?
I can imagine, however, such emptiness in a person's life that could compel them to spend one-minute playing "Call of Duty" when they could be ... programming
And, I am filled with compassion for all those whose lives are empty for whatever reason, particularly for those who have never been able to transform their emptiness into that tasties flavor of emptiness: meaningful suffering.
«The greater the social and cultural distances between people, the more magical the light can spring from their contact» Milan Kundera, "Testaments Trahis"
|
|
|
|
|
|
|
Whoa! Space pictures that aren't comet related!
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
