Re: Nearest Common Ancestor Report (XDb1's $1000 Challenge)

On 18 May 2004 00:23:06 -0700, Neo wrote:

Hi Neo,

>> Note: the output shows the same starting and ending date/time. This
>> indicates an elapsed time of less than 3 milliseconds (the smallest unit
>> of time CURRENT_TIMESTAMP can measure). System used: PC running Windows
>> 2000 + MS SQL Server 2000, AMD Athlon 1.3GHz, 256MB RAM.
>
>Among other things, the difference in normalization between the
>implementations (still looking it over) is quite different.

Of course it is. My implementation is in the Relational Model (or at least as close to the RM as SQL Server gets). Your implementation is in XDb1, which is not relational at all. Implementations of this same problem in a multi-valued database, a hierarchical database and a network database would also use a different structure, suited to the needs and possibilities of those databases.

I don't demand that XDb1 should use a relational structure, you should not demand that a RM solution uses XDb1's structure. If you want to compare, do so at the level where it counts. Check that both solutions accept the same input (they do) and check that both solutions produce the correct report (they do, except that XDb1 prints ony one, randomly chosen common ancestor if several ancestors are at the same distance - but I won't hold that against you).

> Based on a
>cursory look, it seems your implementation is simply utilizing the
>hierarchy table and not having to resolve any keys to generate the
>report (which was not the desired intent).

See above. It should not matter HOW my implementation generates the report.

> In an initial attempt to
>make them more comparable, I modified XDb1 algorithm so as to not
>resolve things' names and simply prints their IDs.

Now you're changing the rules after the competition has started. Not a sign of good sportsmanship, Neo!

But if it is now permitted to produce output with only meaningless IDs instead of a human readable output, I can optimise my design as well. If I add an integer ID column to the things table and change all referencing columns in other tables to use that ID instead of the currect character key, my solution's performance will increase significantly. Integer comparison is faster than string comparison, the row size will be smaller, resulting in more rows per data page = less I/O, etc.

> Based on a few
>runs, the report generation time is 2 or 3 ms using the hi-resolution
>QueryPerformanceCounter function provided by NT on a 500 Mhz PC. In
>general, the execution is linear to PC's speed thus 2 or 3 x
>(500/1,300) should be approx 0.77 to 1.2 ms on a 1.3Gz PC. These
>numbers are too small to make reasonable comparisons.

Yes, I remember making a similar remark myself. But it was not me who set this challenge, that was you. :-)

So far, you failed to disprove my solution. Instead, you attempt to change the rules and you claim that the size of the sample data (provided by yourself!) is too small to make reasonable comparisons. Why do I get the impression that you're trying to bail out of this?

Groetjes, Hugo

-- 

Sorry, vandaag geen grappige sig lines meer.