Hi Lindsay,

yes, Picolisp has been a great tool for me as well to explore algorithms
and datastructures.

You used the high level implementation of fastNth (took around 15 seconds)
instead of the
low level implementation (it took 3 seconds).

In fact, taken both implementations in isolation (without all that high
level code inside the loop), the low level implementation is 30 times
faster than the high level one on average.

The idx mechanism is a perfect implementation of associative array
functionality when the set of keys is a set of arbitrary strings.
But what happens when the set of keys is a more restricted set like a
sequence of numbers? That is a common scenario and I have seen people
implement that using idx, because Picolisp readily offers that solution.

I think that the Digital Search Tree structure (dst) is the perfect
solution for such a restricted set of keys (array functionality), perfect
in terms of memory space (keys are implicit, not stored), in terms of
execution time (no need to compare keys), and in terms of not needing to
change picolisp internally in order to implement arrays.

A dst complements idx, it does not substitute it.

Here is the code needed to compile the low level implementation of fastNth:

(load "@lib/gcc.l")
(gcc "fast" NIL 'fastNth)

any fastNth(any ex) {
   any x = cdr(ex);
   int n = (unDig(EVAL(cadr(x)))>>1) - 1;
   x = EVAL(car(x));

   int i;
   int A = 7 & n;
   int B = 7 & (n >>= 3);
   int C = 7 & (n >>= 3);
   int D = 7 & (n >>= 3);
   int E = 7 & (n >>= 3);
   int F = 7 & (n >>= 3);
   int G = (n >> 3);

   for (i = 0; i < G; ++i) x = cdr(x); x = car(x);
   for (i = 0; i < F; ++i) x = cdr(x); x = car(x);
   for (i = 0; i < E; ++i) x = cdr(x); x = car(x);
   for (i = 0; i < D; ++i) x = cdr(x); x = car(x);
   for (i = 0; i < C; ++i) x = cdr(x); x = car(x);
   for (i = 0; i < B; ++i) x = cdr(x); x = car(x);
   for (i = 0; i < A; ++i) x = cdr(x);
   return x;

the /**/ is an end-delimiter.


Reply via email to