Re: Enumerated Trees in PicoLisp
I was already primed by Scott Adams biology experiment. Being an accelerationist and convergentist. On Thu, 25 Mar 2021 at 02:45, Alexander Burger wrote: > 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
Re: Enumerated Trees in PicoLisp
Hi all, On Thu, Mar 25, 2021 at 10:40:21AM +0100, Alexander Burger wrote: > '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 Note that the semantics changed a little meanwhile. Please look up the reference if necessary at https://software-lab.de/doc/refE.html#enum ☺/ A!ex -- UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
Re: Enumerated Trees in PicoLisp
March 25, 2021 9:48 AM, "Alexander Burger" wrote: > PicoLisp has a really cool new function! Test added and tested in LLVM 7, 11-13. (mike) -- UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
Re: Enumerated Trees in PicoLisp
On Thu, Mar 25, 2021 at 10:40:21AM +0100, Alexander Burger wrote:
> 3. The tree is automatically balanced, independent of the insertion order.
This is only true if there are no final gaps in the keys.
What we can say, however, is that every item is placed at a depth which is the
2-logarithm of its key.
: (enum 'E 64 "Test")
-> "Test"
: E
-> (NIL (NIL (NIL (NIL (NIL (NIL ("Test")))
☺/ A!ex
--
UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
Re: Enumerated Trees in PicoLisp
On Thu, Mar 25, 2021 at 01:06:58PM +0100, Tomas Hlavaty wrote: > > And useless for the intended purpose. At least I see no way to insert and > > look > > up by number (?) > > because you always take the position in the binary heap as the key. OK, so this won't work : (enum 'E 999 "Test") -> "Test" $: (enum 'E 999) -> "Test" ☺/ A!ex -- UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
Re: Enumerated Trees in PicoLisp
On Thu 25 Mar 2021 at 12:23, Alexander Burger wrote: > On Thu, Mar 25, 2021 at 12:11:55PM +0100, Alexander Burger wrote: >> Binary heaps are close, but not the same. > > And useless for the intended purpose. At least I see no way to insert and look > up by number (?) because you always take the position in the binary heap as the key. if picolisp had arrays, your use case would be reduced to trivial constant time array lookup but binary heaps can be much more useful if one can use a key which is not a position in the binary heap btw iirc representing trees this way was invented by a german guy a few centuries ago, when he tried to draw those family trees so popular with aristocrats -- UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
Re: Enumerated Trees in PicoLisp
On Thu, Mar 25, 2021 at 12:11:55PM +0100, Alexander Burger wrote: > Binary heaps are close, but not the same. And useless for the intended purpose. At least I see no way to insert and look up by number (?) ☺/ A!ex -- UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
Re: Enumerated Trees in PicoLisp
Hi Tomas, > binary heap Thanks! Binary heaps are close, but not the same. Pil's algorithm is a lot more efficient. Just bit test and shift, as opposed to the swapping of nodes as described in https://en.wikipedia.org/wiki/Binary_heap ☺/ A!ex -- UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
Re: Enumerated Trees in PicoLisp
On Thu 25 Mar 2021 at 10:40, Alexander Burger wrote: > 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). binary heap -- UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
Re: Enumerated Trees in PicoLisp
Hi Mike, > Test added and tested in LLVM 7, 11-13. Ah, yes, I forgot to add to unit tests. Will add there too. ☺/ A!ex -- UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
Enumerated Trees in PicoLisp
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 1210149 131115 In binary representation: 0001 00100011 0100011001010111 1000 1100 1010 1110 1001 1101 1011 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
