libera/#commonlisp - IRC Chatlog
Search
10:49:33
jackdaniel
making ChatGPT do things being like '“You’re saying it wrong,” Harry heard Hermione snap. “It’s Wing-gar-dium Levi-o-sa, make the ‘gar’ nice and long.”'
16:12:25
_death
beach: "We do not think it is important to optimize the implementation of an operator that is not used very often." does this also apply to time complexity in "simple" cases, e.g. INTERSECTION with the defaults can often do better than n*m comparisons where n and m are the list lengths
16:15:22
beach
Well, INTERSECTION might be used a bit more often than "not very often". There is no sharp distinction as you know, because it depends on the workload. I am willing to accept contributions for optimizations that do not make the code too hard to maintain.
16:16:04
beach
Also, there is a difference between improving the asymptotic complexity as in this particular case, and shaving of a small constant factor.
16:17:18
beach
In that case, one would have to take into account the cost of allocating a hash table and the length of the sets/lists involved.
16:27:22
_death
yes, I was thinking of a hash-table.. another issue is stack blowing up (e.g., in SUBLIS implementation; I remember we had a relevant discussion about a FLATTEN operator a while ago)
16:28:56
beach
I am not sure how to prevent deep recursions in this case. I suppose one can assume that they are skinny in one dimension.
16:31:35
beach
I think I mentioned something in the README about clients who have knowledge about the structures they want to traverse, and that such clients are likely to want to implement a special version anyway.
16:32:46
_death
right, I understand what you mean, but sometimes a client has to reimplement a general version just because the implementation is too naive
16:34:11
beach
So, again, I am willing to accept contributions that improve performance significantly without sacrificing too much maintainability.
16:36:07
beach
For INTERSECTION I think computing the length of the lists first would be a good idea, because that's a linear cost, compared to the M*N cost of the default operation. And if M*N is significantly high, then allocating a hash table could pay off. Restricted by the TEST of course.
16:36:58
beach
I strongly suspect that most uses of INTERSECTION are for short lists, so it would not be a good idea to allocate a hash table in all cases.
16:38:47
beach
I need to go fix dinner for my (admittedly small) family, so I am off for today. I'll read up tomorrow.
16:42:37
_death
beach: yes, said client could very well send a patch after such reimplementation :) .. when I had a patch for alexandria's shuffle I did have some threshold that needed to be crossed in order to use a vector for list shuffling.. of course embedding such a threshold statically borders on the occult