[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: performance

   Date: Thu, 17 Sep 2009 22:32:47 -0400
   From: David Van Horn <dvanhorn@xxxxxxxxxxxxxxx>

   There are benchmarks in the Okasaki paper.  To me, the important cases 
   are lookup and update.  These things are simply not feasible using 
   sequential lists.  What this means is that algorithms where you might 
   otherwise use a vector and mutation, you can now use a list and remain 
   functional (and thus thread-safe, etc).

Of course.  But if these programs would otherwise use vectors, is
constant-time CONS important to them?  For example, would they be just
as well served by bounded-balance binary trees, or what Stephen Adams
calls weight-balanced binary trees?  I have sometimes pondered the
merit of a Lisp system with those as the basic data structure, rather
than lists, which would admit sequences, sets, and associations whose
common operations all run in logarithmic or linearithmic time.