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:[email protected]?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:[email protected]?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:[email protected]?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:[email protected]?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:[email protected]?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:[email protected]?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:[email protected]?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:[email protected]?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:[email protected]?subject=Unsubscribe
