_whitelogger_ has quit [Remote host closed the connection]
_whitelogger_ has joined #picolisp
_whitelogger_ has joined #picolisp
Regenaxer has joined #picolisp
Regenaxer has joined #picolisp
emacsomancer has quit [Ping timeout: 265 seconds]
emacsomancer has quit [Ping timeout: 265 seconds]
orivej has joined #picolisp
orivej has joined #picolisp
emacsomancer has joined #picolisp
emacsomancer has joined #picolisp
rob_w has joined #picolisp
rob_w has joined #picolisp
rob_w has quit [Read error: Connection reset by peer]
rob_w has quit [Read error: Connection reset by peer]
rob_w has joined #picolisp
rob_w has joined #picolisp
orivej has quit [Ping timeout: 244 seconds]
orivej has quit [Ping timeout: 244 seconds]
orivej has joined #picolisp
orivej has joined #picolisp
Nistur has quit [Ping timeout: 256 seconds]
Nistur has quit [Ping timeout: 256 seconds]
Nistur has joined #picolisp
Nistur has joined #picolisp
<Regenaxer>
Wow! I invented a *really* cool new function
<Regenaxer>
Wow! I invented a *really* cool new function
<Regenaxer>
'enum'
<Regenaxer>
'enum'
<Regenaxer>
Binary tree with implicit keys
<Regenaxer>
Binary tree with implicit keys
<Regenaxer>
Don't know if this algorithm exists, found it by myself :)
<Regenaxer>
Don't know if this algorithm exists, found it by myself :)
<beneroth>
hm... you need to explain what you mean :D
<beneroth>
hm... you need to explain what you mean :D
<beneroth>
'enum' is usually a keyword (in SQL, C#, many languages) for a list of possible symbols)
<beneroth>
'enum' is usually a keyword (in SQL, C#, many languages) for a list of possible symbols)
<Regenaxer>
It is like 'idx', but with numeric keys
<Regenaxer>
It is like 'idx', but with numeric keys
<Regenaxer>
The keys are *not* stored
<Regenaxer>
The keys are *not* stored
<Regenaxer>
and the tree is automatically balanced
<Regenaxer>
and the tree is automatically balanced
<beneroth>
ah, a tree with random access like an array?
<beneroth>
ah, a tree with random access like an array?
<Regenaxer>
Yeah, not sure if 'enum' is a good name
<Regenaxer>
Yeah, not sure if 'enum' is a good name
<beneroth>
well yes well no
<beneroth>
well yes well no
<Regenaxer>
thought a few days about it
<Regenaxer>
thought a few days about it
<beneroth>
'enum' is probably a bad name :P
<beneroth>
'enum' is probably a bad name :P
<Regenaxer>
but I think it fits
<Regenaxer>
but I think it fits
<beneroth>
I see
<beneroth>
I see
<Regenaxer>
the inserted values are enumerated
<Regenaxer>
the inserted values are enumerated
<Regenaxer>
you can emulate arrays (also sparse!)
<Regenaxer>
you can emulate arrays (also sparse!)
<Regenaxer>
And takes only one and a half cells per entry
<Regenaxer>
And takes only one and a half cells per entry
<beneroth>
interesting
<beneroth>
interesting
<Regenaxer>
yeah
<Regenaxer>
yeah
<beneroth>
I want to know more, but no time right now. Will ask you later :)
<beneroth>
I want to know more, but no time right now. Will ask you later :)
<Regenaxer>
I intended to use 'idx' but then thought why store the keys?
<Regenaxer>
I intended to use 'idx' but then thought why store the keys?
<Regenaxer>
yes, I'm out too for shopping
<Regenaxer>
yes, I'm out too for shopping
orivej has quit [Ping timeout: 265 seconds]
orivej has quit [Ping timeout: 265 seconds]
aw- has quit [Quit: Leaving.]
aw- has quit [Quit: Leaving.]
<f8l>
This sounds like a data structure I used in my implementation of JigDo as a FUSE module during my studies. Later I discovered that a similar concept, although 256-ary is has been known as https://en.wikipedia.org/wiki/Judy_array
<f8l>
This sounds like a data structure I used in my implementation of JigDo as a FUSE module during my studies. Later I discovered that a similar concept, although 256-ary is has been known as https://en.wikipedia.org/wiki/Judy_array
<f8l>
The latter seems to have been published in 1968.
<f8l>
The latter seems to have been published in 1968.
clacke has joined #picolisp
clacke has joined #picolisp
<Regenaxer>
Hi f8l! Thanks for the links. Judy arrays look very similar, but seem a *lot* more complicated ("smallest have thousands of lines of code". 'enum' in Pil21 is 45 lines ;)
<Regenaxer>
Hi f8l! Thanks for the links. Judy arrays look very similar, but seem a *lot* more complicated ("smallest have thousands of lines of code". 'enum' in Pil21 is 45 lines ;)
<Regenaxer>
Radix trees also seem a lot more complicated
<Regenaxer>
Radix trees also seem a lot more complicated
<Regenaxer>
... and those 48 lines are rather short (indented)
<Regenaxer>
... and those 48 lines are rather short (indented)
<Regenaxer>
Pil's enum uses only short numbers as keys though, not strings as those in above links
<Regenaxer>
Pil's enum uses only short numbers as keys though, not strings as those in above links
<Regenaxer>
But for pil they are really optimal
<Regenaxer>
But for pil they are really optimal
<Regenaxer>
take only a little more space than a plain list
<Regenaxer>
take only a little more space than a plain list
<Regenaxer>
less than twice in the worst case, optimally 1.5 times the space
<Regenaxer>
less than twice in the worst case, optimally 1.5 times the space
<f8l>
Judy arrays are focused on performance, thus the sacrifice of simplicity. I may excavate my implementation for comparison. I reacted to the limited information about your data structure that you shared here. So far I don’t know how it differs from PATRICIA tree.
<f8l>
Judy arrays are focused on performance, thus the sacrifice of simplicity. I may excavate my implementation for comparison. I reacted to the limited information about your data structure that you shared here. So far I don’t know how it differs from PATRICIA tree.
rob_w has quit [Read error: Connection reset by peer]
rob_w has quit [Read error: Connection reset by peer]
<Regenaxer>
You could inspect it with (vi 'enum)
<Regenaxer>
You could inspect it with (vi 'enum)
<Regenaxer>
The algorithm is just a bitwise shift of the key
<Regenaxer>
The algorithm is just a bitwise shift of the key
<Regenaxer>
branching on the lowest bit left or right
<Regenaxer>
branching on the lowest bit left or right
<Regenaxer>
The insert takes most of the code. Lookup by key is just http://ix.io/2TSi
<Regenaxer>
The insert takes most of the code. Lookup by key is just http://ix.io/2TSi
<Regenaxer>
7 lines
<Regenaxer>
7 lines
<f8l>
I could if I had a new enough version of Pil. That’s more or less how I imagined it, and yes, it’s a pretty old idea.
<f8l>
I could if I had a new enough version of Pil. That’s more or less how I imagined it, and yes, it’s a pretty old idea.