freenode/lisp - IRC Chatlog
Search
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
18:37:17
Inline
pve: either wrapping that around the forms in my file or doing it like above both solves my problems
18:39:37
pve
like if you defun foo in the repl and then load a file that also contains (defun foo () ..), you should get the warning
19:02:41
contrapunctus
...ah, on second thoughts, that wouldn't be too effective. (I'm referring to code which uses ++ to ignore the next expression.)
21:26:56
VincentVega
Good day/night all! Wondering, so I have a dynamic variable (it's global and all functions use it conveniently). Now, I want to run the code in a few threads (independently), each having it's own (thread-specific) value of the dynamic variable. Can this be done?
21:27:51
aeth
I think dynamic variables are always thread-specific? Probably an implementation-specific thing, but I thought it's sort of part of the bordeaux-threads assumptions.
21:30:26
aeth
VincentVega: I think the most portable way to do it would be to wrap the thread entry point (inside of the lambda that's run on the new thread in bt:make-thread) in a LET?
21:31:10
aeth
initial-bindings is what I must've been thinking of, but it has some implementation-specific behavior
21:36:31
aeth
let over lambda is the implementation-specific behavior BT is warning you not to do in bt:make-thread's documentation
21:49:23
aeth
It's a design pattern. This means the proper solution is to use a make-thread* macro to do that instead. :-p
22:19:55
White_Flame
I guess a with-* macro would be a design pattern, as there aren't specifically scope management operations in lisp
22:22:17
aeth
White_Flame: Correct. When Lispers criticize design patterns as unnecessary in Common Lisp, I bring up the case of "macro design pattern" conventions, like with-foo (usually with an unwind-protect), define-foo (usually with a defun, but maybe it deals with a different global definition), do-foo (iteration), etc.
22:22:55
aeth
White_Flame: Although to be fair, you could turn some of these into macros, even though only define-modify-macro (like incf/decf) actually is like that in the standard.
22:23:19
fwoaroof[m]
I generally think of "design patterns" as involving fairly complicated code structures that have to be manually implemented every time
22:27:09
aeth
solve the package name conflict issue in Quicklisp so you can say with-every-single-asdf-system-in-quicklisp-loaded
22:29:47
aeth
think of all of the fun surprises realized by modifying global state, e.g. you might discover that (with-every-system-loaded (+ 1 1)) => ٢