libera/commonlisp - IRC Chatlog
Search
6:02:52
beach
remexre: Sets are tricky things. There is really no abstract data type called a "set" because it is impossible to have all set operations be efficient simultaneously. That is why every abstract data type that contains other objects is defined by the operations that are supported. If you give us the operations you like, perhaps we can help.
6:03:22
beach
remexre: But in general, such a representation would not allow for many operations to be efficient.
6:05:14
moon-child
sorted vector gives you binary search if you care for it, but no in-place intersection or union
6:05:41
beach
remexre: For intersection, convert to lists, do the intersection, convert to a vector, sort.
6:07:11
beach
That sounds like premature micro-optimization without any measure to determine whether it is necessary.
6:07:51
beach
remexre: You are comparing cache effects and asymptotic complexity. They are not the same order of magnitude.
6:08:29
beach
remexre: My guess is that you are going to spend all the time comparing characters in strings anyway.
6:09:05
moon-child
beach: 'For intersection, convert to lists, do the intersection, convert to a vector, sort' hmm? If you were using such a representation--and you cared for performance--you could do it in O(m+n) by iterating over both vectors and VECTOR-PUSH-EXTENDing a result
6:09:18
moon-child
(and if you don't care for performance, just use a list and don't bother with anything else)
6:09:43
remexre
the point with the asymptotics was that they're not terrible; not ruining the cache by using vectors was more of the point
6:10:55
moon-child
sure. I think the problem is insufficiently motivated/contextualized. If it's desirable for some reason to use a vector in the first reason, that same reason may also make it undesirable to use an intermediate list (which was your suggestion)
6:11:55
moon-child
given two sorted vectors, you can produce a sorted intersection vector in linear time, without consing an intermediate list and calling SORT on it
6:12:33
moon-child
yes. And if it doesn't matter then you can just use lists. We are going in circles :P
6:13:46
moon-child
remexre: can you motivate your problem? Do you have set-processing code which is slow?
6:14:09
remexre
no, I'm planning on writing code that I don't want to go back and change the set representation for
6:14:46
moon-child
if your interface is properly abstracted, it should not be prohibitively difficult to change your representation
6:16:04
remexre
right, but i know the representation I want, and I would be surprised if I needed to change *from* that later
11:02:31
neominimum
Anyone have a more elegant solution to finding the first element of a list and all sub-lists than what I have managed to hack together? https://pastebin.com/raw/6W6ppPTb
11:18:49
flip214
We've got a CI/CD pipeline for Alexandria now. Are there volunteers for finding out why some implementations disagree with the majority? https://gitlab.common-lisp.net/alexandria/alexandria/-/jobs shows 4 of 8 failing (in overlapping sets of tests).
11:56:10
phoe
I have no idea if this is conforming, because the complex number has different types for realpart and imagpart
11:57:59
phoe
no idea about cmucl and allegro - cmucl complains about some undefined function, which is weird, and acl has some type failures as well as a copy-hash-table failure
12:06:43
flip214
phoe: (EQUAL #C(0.0 0.0) 0.0) -- That's what my testing branch shows as difference. Looks like clisp doesn't see them as EQL...
12:19:19
specbot
Rule of Canonical Representation for Complex Rationals: http://www.lispworks.com/reference/HyperSpec/Body/12_aec.htm
12:20:31
phoe
if I am reading this correctly, if their parts are floats, then they are not meant to be EQL
12:29:25
flip214
phoe: https://gitlab.common-lisp.net/alexandria/alexandria/-/jobs/27975 (allegro) has the same subtypep problems
12:30:41
flip214
http://www.lispworks.com/documentation/HyperSpec/Body/f_eql.htm#eql says " If an implementation supports positive and negative zeros as distinct values, then (eql 0.0 -0.0) returns false. Otherwise, when the syntax -0.0 is read it is interpreted as the value 0.0, and so (eql 0.0 -0.0) returns true."
12:34:14
flip214
pjb: I don't understand where you get the ε from - the zero can be expressed exactly (though perhaps non-unique because of ±), and so 0.0 == 0.0??
12:35:01
flip214
https://gitlab.common-lisp.net/alexandria/alexandria/-/pipelines/5874 shows that 4 implementations were okay with (EQUAL #C(0.0 0.0) 0.0)
12:36:09
flip214
pjb: http://www.lispworks.com/documentation/HyperSpec/Body/f_eql.htm#eql has the example (eql 3.0 3.0) => true
12:36:45
flip214
http://www.lispworks.com/documentation/HyperSpec/Body/f_equal.htm says if they are numbers that are eql,
12:38:42
pjb
This is precised in the Note: Two complex numbers are considered to be eql if their real parts are eql and their imaginary parts are eql. For example, (eql #C(4 5) #C(4 5)) is true and (eql #C(4 5) #C(4.0 5.0)) is false. Note that while (eql #C(5.0 0.0) 5.0) is false, (eql #C(5 0) 5) is true. In the case of (eql #C(5.0 0.0) 5.0) the two arguments are of different types, and so cannot satisfy eql. In the case of (eql #C(5 0) 5), #C(5 0)
12:45:01
neominimum
beach: ah yes, that was intentional. removing `(atom (caar form))` prints (1 2 3)
12:45:32
beach
neominimum: The form (and root (print (car form))) is better written as (when root (print (car form)))