Hi all,
PicoLisp has a really cool new function!
It is called 'enum', because it "enumerates" arbitrary Lisp values. That is, it
associates values with numbers, by storing them in a binary tree structure.
The cool points are:
1. The numeric keys themselves are not stored. They are implicit. This saves
half of the space: Only one and a half cell on the average are needed per
entry.
2. It allows to emulate (possibly sparse) arrays with acceptable overhead.
3. The tree is automatically balanced, independent of the insertion order.
And it hopefully silences those always demanding arrays in PicoLisp ;)
'enum' is similar to 'idx' with numeric keys. But with 'idx', the keys take up
one additional cell per entry, and the insertion order is relevant.
(enum 'var 'cnt 'any) -> any # stores a value
(enum 'var 'cnt) -> any # looks up a value
Example:
: (for (I . S) '(a b c d e f g h i j k l m n o)
(enum 'E I S) )
-> o
: E
-> (a (b (d (h) l) f (j) n) c (e (i) m) g (k) o)
: (view E T)
o
g
k
c
m
e
i
a
n
f
j
b
l
d
h
-> NIL
: (enum 'E 6)
-> f
$: (enum 'E 1)
-> a
: (enum 'E 12)
-> l
: (enum 'E 99)
-> NIL
In this example, the keys are ordered as:
1
2 3
4 6 5 7
8 12 10 14 9 13 11 15
In binary representation:
0001
0010 0011
0100 0110 0101 0111
1000 1100 1010 1110 1001 1101 1011 1111
The algorithm traverses the key from the lowest bit to the highest, branching
left for zero and right for one.
Probably this algorithm exists already, because it is so simple and obvious. But
I found it by myself and did not bother to search for it (mainly because I don't
know what name to search for).
As another example, we might replace 'cachedFibo' (from misc/fibo.l in older
PicoLisp releases)
(de cachedFibo (N)
(cache '(NIL) N
(if (>= 2 N)
1
(+ (cachedFibo (dec N)) (cachedFibo (- N 2))) ) ) )
with
(de enumFibo (N)
(let E '(NIL)
(or
(enum E N)
(enum E N
(if (>= 2 N)
1
(+ (enumFibo (dec N)) (enumFibo (- N 2))) ) ) ) ) )
'enumFibo' is about twice as fast, and reduces the space by almost two thirds.
☺/ A!ex
--
UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
