<miskatonic>
hash tables suck big times when compared to balanced binary trees
<beneroth>
I'm still wondering why they even became a thing (for general data, not just for specialised cases like fulltext indexing). I grow up with C++ map<> (implemented as Red Black Tree), that the other languages didn't had map but "Dictionary" was a great confusion to me :)
<beneroth>
aaah
<beneroth>
"While the C++ standard doesn't specifically say "thou shalt use a red-black tree to implement std::map", try using anything else. An AVL tree won't work; it's insertion costs don't meet the standard. A hash won't work; a hash is unordered and hence doesn't meet the standard. The standard pretty much says "thou shalt use a red-black tree to implement std::map" without saying so explicitly"
<beneroth>
from that answer I deduce the real reason is "Hash tables are easier to implement than trees." amended with a snarky "But still gives us the feeling of complexity and superiority, I mean, we cannot be seen doing just a simple linked list, can we?"
<beneroth>
Simpler is Better.
<Regenaxer>
Yeah. PicoLisp uses the even-simpler plain binary trees
<Regenaxer>
But the reason for this decision is in fact space
<Regenaxer>
(needs only two cells per node)
<beneroth>
the argument against trees seems to be the time used to rebalance in during inserts and deletions
<beneroth>
and we use plain lists usually where in other stacks you would already use a hash table, I believe (e.g. storing HTTP arguments in memory)
<Regenaxer>
Probably
<Regenaxer>
PicoLisp idx trees are a bit minimalistic, needs a little more attention by the programmer
<Regenaxer>
red-black would be better, but needs more space
<beneroth>
<Regenaxer> PicoLisp idx trees are a bit minimalistic, needs a little more attention by the programmer
<beneroth>
<Regenaxer> PicoLisp idx trees are a bit minimalistic, needs a little more attention by the programmer
<Regenaxer>
(I believe r/b trees are a special case of b~trees, no?)
<beneroth>
in what way, beside the unhandy callign syntax ?
<beneroth>
Regenaxer, yeah, r/b is storing a bit marker on every node for faster/easier future rebalance
<Regenaxer>
The calling syntax is good, I think. It is that you must take care not to produce a denegerated tree
<beneroth>
tell me more, I'm not sure if I'm aware
<beneroth>
can be later, if you don't have time now.
<beneroth>
I should do some plio :D
orivej has quit [Ping timeout: 248 seconds]
<Regenaxer>
If you insert *sorted* data with 'idx', it degenerates to a linear list
<Regenaxer>
So you should use 'balance' then
orivej has joined #picolisp
<beneroth>
I guess you should use 'balance anyway after finishing insertion phase (when applicable)
* beneroth
was aware
<Regenaxer>
No, it is never balanced after insertion
<beneroth>
T
<Regenaxer>
'balance' *does* build the tree
<beneroth>
(idx 'var 'any) is just inserting at first possible leaf I would assume?
<Regenaxer>
yes, (idx 'var 'any T)
<beneroth>
so inserts/delets are not completely ruining a tree (when it was once balanced before), but does unbalance it until it might be completely "bad" for querying
<beneroth>
right?
<beneroth>
(sorted insert results in only one "branch" growing, therefore being the worst case)
<Regenaxer>
This happens only if you do a sorted insert or delete
<Regenaxer>
if it is just a bit unsorted, the results are sprprisingly fine
<beneroth>
yeah, so random (considering sort order) inserts/deletes is ok :)
<beneroth>
ok
<Regenaxer>
I think most theorists are too paranoid about that
<beneroth>
good, my believes are checked and confirmed :)
<beneroth>
T
<Regenaxer>
:)
<Regenaxer>
If neded, 'balance' produces a perfect tree though
<Regenaxer>
(only once as you noted)
<beneroth>
in light of "Picolispizität" (word creation by Morris), I would call this behaviour of (idx) to be in favour of programmers control. (idx) is not self-balancing, meaning programmer can decide WHEN the tree gets balanced, instead of paying overhead cost on every operation
<Regenaxer>
Exactly!
<beneroth>
as in most practical cases, you would probably first build the tree and then query it, both operations mixed don't happen so often I would say (or when, then in DB context as you need to store this information, and the DB B-Trees are self-balanced)
orivej has quit [Ping timeout: 246 seconds]
<beneroth>
so high value in Picolispicity :D
<beneroth>
ha
<Regenaxer>
Mixing build and query also happens often
<Regenaxer>
eg in namespaces
<beneroth>
Picolispicity, that should be the english word for Picolispizität. yes?
<beneroth>
Regenaxer, hm T
<beneroth>
but the internal trees are self-balanced, no?
<Regenaxer>
no
<beneroth>
ok, so completely unbalanced usually, just the split into long-symbol-name and short-symbol-name trees (and local trees for every namespace and transient scope) ?
<Regenaxer>
They assume that symbols are not created in sorted name-order
<Regenaxer>
yes
<beneroth>
hm, good point, my habit of ordering function definition in source code by name is bad :D
<Regenaxer>
In fact not
<Regenaxer>
it is not alphabetical
<Regenaxer>
but the way symbol names map to numbers
<beneroth>
ah
<Regenaxer>
So it is very hard to make a sorted build
<beneroth>
string to binary blob, interpreted as number -> number is the key
<Regenaxer>
yes
<beneroth>
so... some people could argue it is a hash tree indeed!
<beneroth>
:D
<beneroth>
just no hash collisions :D
<beneroth>
(so no hash, just transcoding)
<Regenaxer>
hmm, but no hashing is needed
<Regenaxer>
the names are there already
<beneroth>
aye T
<beneroth>
and hash is shortening, we do no shortening
<Regenaxer>
the order is kind of backwarys
<Regenaxer>
right
<Regenaxer>
no collisions
<beneroth>
thanks for this great informative discussion :)
<Regenaxer>
:)
<beneroth>
good to validate my assumptions
miskatonic has quit [Remote host closed the connection]
<beneroth>
periodic re-validation is the core of science
<Regenaxer>
true
<beneroth>
Picolispm, the ideology of increasing the picolispicity of things
<beneroth>
Picolispism ?
<Regenaxer>
Sounds cool!
<beneroth>
we are a lovely cult, full of KISSes
<beneroth>
a bit smug and snarky at times, though
<Regenaxer>
haha, yes :)
orivej has joined #picolisp
ubLIX has joined #picolisp
<beneroth>
Regenaxer, plio question, select generato clauses: I assume I can mix using arguments (which can be a value or range, as in db/3) and combined indexes (multiple index used in one single generator clause) ? therefore modelling OR conditions on indexed properties ?
* beneroth
will try ou
* beneroth
will try out
<Regenaxer>
yes, there are a lot of combinations possible
<beneroth>
everytime I look at plio, I think I should use it more!
<beneroth>
so powerful
<beneroth>
thanks :)
<Regenaxer>
:)
<Regenaxer>
I hope the syntax of select/3 is fully covered in select.html
<Regenaxer>
doc/select.html
<beneroth>
for a specific application, I made now a kind of "Query editor", the user can create conditions based on properties of an entity. I try not to generate pilog code from those editor output.
<beneroth>
I have no hint that it isn't :)
<Regenaxer>
"Query editor": Great!
<beneroth>
you had something in your applications? I don't know your stuff good enough...
<beneroth>
at the moment I just do this for this specific application. but I hope to generalize this later.
<Regenaxer>
I once had, yes, a simple chart of expressions
<beneroth>
ok
<beneroth>
in may extension of pilDB I store more metadata about schema, so this can be built upon for knowing which kind of query conditions are even meaningful.
<beneroth>
but it also complicates more things, as my "mashina entities" are versioned, a query might have to run over multiple picolisp entities :)
<Regenaxer>
true
orivej has quit [Ping timeout: 245 seconds]
<beneroth>
Regenaxer, Does the order of filter clauses matter? Are the filter clauses checked in order, or in quasi-parallel ?
<Regenaxer>
They are checked strictly in orderr
<Regenaxer>
So it may matter
<beneroth>
thanks
<Regenaxer>
Train from Hamburg back home. Unstable connections
orivej has joined #picolisp
<beneroth>
ok. save and good travels!
<Regenaxer>
Thanks! :)
razzy has joined #picolisp
razzy has quit [Changing host]
razzy has joined #picolisp
<Regenaxer>
No worries! Deutsche Bahn as always: 20 minutes late before it even started, they somehow lost waggon number 6, but we are rolling :D
<beneroth>
lol, really as usual
<beneroth>
your reserved sit did not happen to be in waggon 6 ?
<beneroth>
:D
<beneroth>
(happened to me)
<beneroth>
(and as I was modern, using their often advertised app, they were not even able to give me compensation for the lost sit...)
<beneroth>
(Köln to Frankfurt I think)
<Regenaxer>
:(
<Regenaxer>
No problem with reservation fortunately
<Regenaxer>
(we never resserve, makes no sense)
ubLIX has quit [Quit: ubLIX]
<beneroth>
I think it was required for the ICEs
<Regenaxer>
IIRC it was never required
<beneroth>
Didn't make sense always, but when travelling 8 hours or so in one go, reservations can make it quite more comfortable
<beneroth>
Maybe only when booked via SBB...
<beneroth>
I'm unsure now.
<Regenaxer>
ah, yes, possible
<beneroth>
I guess the time of day also makes a big difference in how crowded it is :)
<Regenaxer>
true, but in practice one always finds a free seat
<beneroth>
most times, not always
<Regenaxer>
T
rob_w has quit [Remote host closed the connection]
<beneroth>
Regenaxer, how to limit number of results with a pilog query? Running (query) in a pipe and cancel it ?
<Regenaxer>
I use catch/throw
<beneroth>
or (prove) ? I fail to use (prove) with select/
<beneroth>
ah
<beneroth>
in the function
<beneroth>
nice
<Regenaxer>
You mean in the 'pilog' function, right?
<beneroth>
aye
<beneroth>
yeah better than pipe lol
<beneroth>
catch/throw is the right thing
<Regenaxer>
yeah
<Regenaxer>
non-local exit :)
<beneroth>
ah, (prove (goal select-query...)) works :)
<beneroth>
so could also repeatedly call (prove) instead of catch/throw, aye?
<Regenaxer>
A simple example is in app/sales.l
<beneroth>
I see
<beneroth>
nice use of (at) :)
<Regenaxer>
catch / pilog/ throw
<beneroth>
T
<Regenaxer>
No need to call 'prove' usually
<Regenaxer>
Sorry, I have very bad connection
<beneroth>
yeah I think catch/throw is nicer code, instead of calling (prove) in a loop
<Regenaxer>
I type blind up to 2 words until I get an echo
<beneroth>
no problem
<beneroth>
oh I'm sorry!
<beneroth>
ok one last comment: (prove) is probably useful for cases when you don't know how many results (possibly not all) you want. agreed?
<beneroth>
special case. but imaginable, e.g. in a game logic or so
<Regenaxer>
haha, I typed "up to 20 words" :)
<beneroth>
wow
<beneroth>
good you are not used to Swiss mobile network, else Germany looks really bad >.<
<beneroth>
xD
<Regenaxer>
well, 'prove' is the most general
<Regenaxer>
'pilog' is just a primitive frontend
<Regenaxer>
like 'solve'
<beneroth>
naturally
<beneroth>
so pilog is fronted of solve, which is frontend of prove
<Regenaxer>
yeah, some reagions are alost dead in terms of network connection
<Regenaxer>
not quite
<Regenaxer>
plog call a Prg, solve makes a list
<beneroth>
T
<beneroth>
iter vs. collect
<beneroth>
you are right
<beneroth>
essential difference
<Regenaxer>
Simple 3-liners both :)
<beneroth>
(prove) smells like a ingredient for a curry
<beneroth>
ok, I need to go. I got the basics of pilog generation working \o/ now what remains is mostly grunt work, not so hard anymore.
<beneroth>
thanks for your help
<beneroth>
good travel!
<beneroth>
afk
<Regenaxer>
yes, or other control structures. GUI chrts call 'prove' whenever they need a new line
<Regenaxer>
thanks!
<beneroth>
aye, as I said, (prove) is useful for cases when you don't know how many results (possibly not all) you want :D
<beneroth>
I think I grokked it. THANKS <3
<Regenaxer>
👍 :)
<beneroth>
my client here cannot render that :)
<Regenaxer>
oh
<Regenaxer>
No UTF-3
<Regenaxer>
UTF-8 ;)
<beneroth>
yeah this is my outdated IRC client
<beneroth>
on the notebook I have a better one, we should check special chars there.
<beneroth>
really afk now. bye bye, greetings to family :)
<Regenaxer>
bye, and thanks!!
<beneroth>
thanks to you!!
<Regenaxer>
To be fair, I must say that the train caught up. Now we are in Fulda and in time :)
<Regenaxer>
Happens not often wit DB
orivej has quit [Ping timeout: 248 seconds]
ubLIX has joined #picolisp
orivej has joined #picolisp
orivej has quit [Ping timeout: 272 seconds]
orivej has joined #picolisp
Nistur has quit [Ping timeout: 245 seconds]
Nistur has joined #picolisp
Nistur has quit [Remote host closed the connection]
Nistur has joined #picolisp
Nistur has quit [Remote host closed the connection]