freenode/lisp - IRC Chatlog
Search
6:45:03
philweb
jackdaniel: I added asdf to dependencies thinking that would pull them in (apparently it didn't work) then I tried adding the named packages (uiop/os and uiop/pathname) but that results in component not found when loading my top-level system
9:31:30
phoe
because here you have a situation where you're redefining methods that were already present in Lisp
9:38:31
phoe
I actually don't know; it seems like an issue with cl-jupyter, since I assume that's what you are using
9:39:16
Inline
btw jupyter:install from a running repl has problems establishing a server connection, the server times out or whatever and gets killed
13:41:13
remexre
is there a common naming convention for functions made to be passed as the second argument to SORT?
13:42:28
remexre
And, stepping back a bit, if I need to manipulate sets of a struct and sets of those sets, is there a better representation than sorted vectors?
13:44:37
remexre
so I can do (member foo-set foo-foo-set :test #'equalp), to check for membership of the set in the set of sets
13:44:53
beach
Well, then, it is impossible to answer your question, because there is no abstract data type named SET, simply because it is not possible to design one that has optimal performance for all possible set operations. That's why we have stacks, queues, union-find sets, binary trees, hash tables, etc.
13:45:26
beach
So you need to come up with a protocol (i.e. a set of operations) that you need to perform on those sets. Then you will know the best data structure.
13:46:11
remexre
I think I just need mapc and "insert, returning whether the item was present" (or separate member and insert, which is what I'm doing now)
13:46:56
beach
But if you can come up with a total order, then you can use binary search or you can use a balanced tree.
14:09:52
u0_a156
I think this is close: ensure-gethash key hash-table &optional default https://common-lisp.net/project/alexandria/draft/alexandria.html#Hash-Tables
14:24:09
beach
They are O(1) "average" complexity which is even better than a balanced tree. But again, it depends on what your domain can handle.
14:24:38
beach
The overhead is somewhat large for a hash table, but that pays off when you have a lot of elements.
14:25:45
remexre
yeah, I'm never going to have more than a hundred elements per set anyway, so I think constant factors would win out
14:50:23
ralt
an hour ago I wrote a (let ((presentp (nth-value (gethash key table))) (if presentp (incf (gethash key table)) (setf (gethash key table) 0))
14:51:37
ralt
which reminds me, anyone has an idea of how to do this better? https://pastebin.com/Jzd8hhab
14:59:03
ralt
the `(push v top-10) (sort top-10 #'<)` is not great but OTOH it's a list with 10 elements... I guess an `(insert-sorted v top-10)` would be better, but not by that much? idk
15:01:40
MichaelRaskin
I believe separately storing the minimum and its position could be faster than sorting every time (but maybe array of length 10 is short enough)
15:06:44
beach
Also, MichaelRaskin is right, you can use a vector, and you can use bubble sort or insertion sort which are linear if you only insert one element, but you already figured that out.
15:12:26
ralt
the (SETF FIRST) + (SORT) ends up with double the amount of CPU cycles than pop/push/sort?
16:01:59
philweb
jackdaniel: getting closer. I've reduced the code to a trivial test and pasted it with notes in case there's something obvious I'm doing wrong: https://pastebin.com/YG1aqisj