Re: [Scutigena-code] Re: new lists tests

[antirez <an...@in...>]

On Sat, Feb 07, 2004 at 12:47:55PM +0100, David N. Welton wrote:
> > # Populate the L1 list with a random function
> 
> I wonder how much this slows things down... I mean, we want to test
> the lists, not their creation via a potentially slow function.

Hello Dave,

the test is designed so that the list population has very
little effect in the total time for every not-too-small N,
because the list creation is O(N) while the other two steps
(that is where the real testing is done) are O(N^2).

But there is a design error in the test, so I'm rewriting
it. The problem is that after the list creation, the
operations performed are O(N^2) in both lists implementations
(array or linked data structure). Of course there is a
big difference in constant times, but still this may
allow a faster language to win over another that implements
lists ad linked lists even for a not so small N.

After the change the test should be O(N^2) with some language
and O(N) in some other language (but will look a bit more
artificial).

I'll post it in some day,
Salvatore

-- 
               Salvatore Sanfilippo <antirez at invece dot org>
"However, there is a tension between making the language simpler and making the
organization of a system manifest. As the variety of costructs decreases, so
does the variety of linguistic clues of a system's structure." (Ungar and Smith)