BIND - sorting of reverse domain.

[Danny Mayer]

At 11:00 PM 7/14/02, D. Stussy wrote:
>On Sun, 14 Jul 2002, Danny Mayer wrote:
> >Do you have any performance numbers to back up your conjecture and if
> >so what are the numbers?
>
>The fact that one version has an extra step as opposed to the other version
>where that step is omitted in itself shows the performance.  Obviously, you
>never studied (or don't remember) computational theory or graph, 
>directed-graph,
>and tree theory in college, else you wouldn't need to ask such trivial
>questions.

You wouldn't know. The question I asked is not trivial.

>The reading in of data stored by a MLR binary tree traversal into an identical
>binary tree structure will already be at an insertion/search minimum.  Any 
>other
>nonisomorphic arrangement of data will mean that at least one (if not many)
>additional search operations before each insert.  The number of insert
>operations will remain constant (since it is identical to the number of 
>elements
>to insert - itself a constant) regardless of structure.  This is an
>order(log2(n)) operation.
>
>The reading in of data stored by a LMR binary tree traversal into an identical
>binary tree structure will devolve into a right-unbalanced tree identical to a
>linked list.  Since everyone insists that no list structure is used, there
>cannot be an interelement shortcut by checking the last element inserted 
>to see
>if the new element to be inserted comes after.  That is a list property 
>which a
>tree does NOT share since a tree has TWO successive elements (one "above" and
>one "below" in order).  Therefore, for each insertion, the entire tree
>(effectively a list at this point) MUST be traversed.  That is an order(n^2)
>[i.e. N-squared] operation.
>
>Here's your efficiency:  Compare the computational order of operations.
>         - Order(n^2)
>vs.     - Order(log2(n)).
>
>(For all positive integers, log2(n) < n^2.  For zero, there's nothing to
>consider anyway - how much time does it take to insert 0 items!)
>QED.

Who cares?  That wasn't the question asked.


>That didn't even consider the fact that the "MLR" tree is already balanced (by
>definition - if generated from a balanced tree), while the "LMR" tree must 
>still
>be balanced.  One is already ahead before skipping the unnecessary operation.
>
> >>The other traversals, including the "LMR" one that happens to also put the
> >>zone
> >>data into domain-name alphabetical/machine order, do not have this
> >>property and
> >>are cost-penalized by needing the rebalancing operation.
> >>
> >>The benefit doesn't get simpler than that.
> >
> >If that's the only consideration.
>
>As noted above, the computational complexity of reading the data back in
>changes (decreases) as well.
>
>If none of the authors recognized the benefits of a binary tree structure over
>the alternatives, then why did they select it in the first place, 
>especially if
>they then don't follow through to take advantage of its properties?  It sounds
>to me as a result of having to explain this, that these people did not
>understand why they were making the choices they did - and that is simply
>incompetence (lack of knowledge or understanding of the necessary concepts).

You haven't a clue, but you jump to totally irrelevant conclusions based on
no knowledge whatsoever.

Let me reiterate the question that I asked: what are the performance
numbers? Let me put it in very simple terms: What is the difference in
performance in loading say 1 million records the current way or your
way? Is it 2 seconds, 2 minutes or 2 hours? Choose any machine and
O/S of reasonable perfomance and memory that you want. If the answer
to the question is 2 seconds, the work does not wanted the cost of
changing it.  If two minutes, then maybe it should looked at. If 2 hours it
should be done. You're so caught up in your trees you don't see the wood
at all.  This is practical engineering, not theory. You have to look at
what it takes in time money and resources to implement something.

Danny