| I am simply trying to choose the best tool for certain
| class of algorithms.
| Given a choice of Array, List and one of the varieties
| of Random Accees List; and assuming that I am not doing
| anything really stupid implementation-wise, such as using
| indexing for Lists; the practical question is:
| which of those data structures would give me the best
| response time?
Ahh, I can't resist the plug... "Auburn" will help!
Auburn is a data structure benchmarking tool for Haskell. Auburn
takes a description of how to use a data structure, and constructs a
benchmark that uses the data structure in the given way. This
benchmark can be run for competing implementations of the same data
structure, to find out which is best for that particular pattern of
use. This allows us to build up a picture of which data structure is
best according to how it is used.
I am currently working on an automatic decision tree inducer that will
take a sample of benchmarks and induce a decision tree for the best
data structure based on how the data structure is used.
For example, using the six implementations of random-access list given
by Chris Okasaki in his FPCA'95 paper [1], I have induced the
following decision tree:
if lookupW <= 0.01
then use Naive List
else if updateW <= 0.05
then use Myers' Stack
else if size <= 20
then use Myers' Stack
else use AVL Tree
This tree has proved to be 90% reliable (ie. it decides on the best
data structure correctly 9 times out of 10).
"lookupW" is the proportion of operations done that are lookup
operations, similarly for "updateW" and update operations, and
"size" is the average size of a list.
The types of lookup and update are:
lookup :: RAList a -> Int -> a
update :: RAList a -> Int -> a -> RAList a
For further details, see the Auburn home page:
http://www.cs.york.ac.uk/~gem/auburn/
Cheers,
Graeme.
