Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!know!zaphod.mps.ohio-state.edu!julius.cs.uiuc.edu!ux1.cso.uiuc.edu!ux1.cso.uiuc.edu!m.cs.uiuc.edu!gillies
From: gillies@m.cs.uiuc.edu
Newsgroups: comp.theory
Subject: Re: data structures of Tarjan, et.al an
Message-ID: <37800016@m.cs.uiuc.edu>
Date: 27 Sep 90 05:05:00 GMT
References: <193541@<1990Sep23>
Lines: 23
Nf-ID: #R:<1990Sep23:193541:m.cs.uiuc.edu:37800016:000:1232
Nf-From: m.cs.uiuc.edu!gillies    Sep 27 00:05:00 1990


I implemented a recursive Tarjan Splay and my own splay on a 16Mhz Mac
II (2-3 MIPS, about as fast as a SUN III).  I was disappointed because
after substantial tuning, I could only achieve about 40,000-50,000
integer comparisons / second.  In other words, to insert 1000 integers
and then look them up repeatedly, you would get about 5,000 lookups
per second.  I used straightforward recursive algorithms in C.

Has anyone written a splay that is faster?  I suspect the splays just
posted are not as fast.  However, my splay is just a benchmark and
does not contain the all trivial amenities (like delete() or join()).
The splay constant of proportionality is very large (there is an MIT
Sloan School tech report just to complain about this fact).  In fact,
the number above suggest the constant may be 5-10 times slower than
search in a balanced tree.  It seems that in many applications, AVL
trees would still be a bigger win, especially when insertions and
deletions are relatively rare, and locality of reference is unlikely.
Anyone care to comment?


Don W. Gillies, Dept. of Computer Science, University of Illinois
1304 W. Springfield, Urbana, Ill 61801      
ARPA: gillies@cs.uiuc.edu   UUCP: {uunet,harvard}!uiucdcs!gillies