freenode/#lisp - IRC Chatlog
Search
3:33:36
ahungry
Some would view the lack of version pinning in ql as a problem, but I like that it changes the implicit contract between packagers and users from "Hey, we're going to push BC breaks all the time and just do a major version bump", to something more like "we avoid breaking BC at all costs"
4:03:53
aeth
ahungry: Which would be perfectly fine, but that means that in any higher order function, it should be expected to use keyword arguments with &allow-other-keys so there's no future breakage and there's no real way to enforce that except maybe generating a random nonsense key
4:04:44
aeth
If I'm unclear: if your API expects a function somewhere (even in a macro, not just higher order functions) it should use keywords, and the user should expect to have to use &allow-other-keys so future updates don't break it
4:11:04
aeth
I suppose another alternative is to use one struct/standard-object/list/hash-table/whatever for that
9:19:48
purpur
Hi all. I tried the rosettacode.org example for the primitive version of bubble-sort and it just goes straight to something like an infinite loop for a simple list like "(bubble-sort (list 1 8 7 5 6 0 7 3 4))".
9:21:56
no-defun-allowed
Maybe it's just terribly slow? Random access to lists is slow, and bubble sort runs in O(n^2) time.
9:22:17
ck_
purpur: try handing in a symbol instead. (defparameter my-list (list 1 8 7 5 6 0 7 3 4)) (bubble-sort my-list)
9:23:06
decent-username
Is there a way to redefine a structure without starting a new REPL? I've always simple avoided the problem that way.
9:24:59
phadthai
you'll need to recompile anything that depends on that structure, as unlike for clos, accesses may be very optimized as memory offsets
9:25:32
purpur
no-defun-allowed: I waited like 1:30 min and it just keeps going. It canĀ“t be that slow for a list with less than 10 elements
9:27:17
Shinmera
The long answer is you need to remove all symbols the structure definition touches, and then recompile everything that used any of those definitions.
9:27:41
decent-username
Shinmera: thanks for the answer. So I'll have to simply start a new REPL. :^D
9:28:40
no-defun-allowed
purpur: Oh, the code is broken with duplicate elements. Try with a comparison function #'<= and it will work.
9:30:09
no-defun-allowed
https://plaster.tymoon.eu/view/1511 Here is my somewhat improved version, which will play nicer with lists.
9:35:05
purpur
no-defun-allowed: Thank you for the detailed explanation. Iam just starting with lisp and searched for a simple variant of bubble-sort. I will have a look into your code snippet.
9:36:54
lorenzoi
hello I am having issues with loading quicklisp in sbcl. I have the load script in my sbclrc but it does not load.
9:41:36
decent-username
lorenzoi: A bit more information would be nice. How did you end up in this situation?
9:42:13
lorenzoi
I wanted to load up a package in an sbcl repl in my browser, but it said that the package QL did not exist
9:43:32
decent-username
lorenzoi: You need to start sbcl with quicklisp. For this you would need to execute "sbcl --load quicklisp.lisp". After doing that you'll need to evaluate "(ql:add-to-init-file)"
9:44:20
decent-username
if you encounter any error before that, try to delete you ~/quicklisp directory and follow the procedure that's described at https://www.quicklisp.org/beta/.
13:15:24
jcowan
In particular, there is a very nice destructive mergesort on lists that uses zero space (the top-level pairs in the output are a recycled version of the top-level pairs in the input).
13:25:10
flip214
how much slower is sorting a list compared to putting all the elements in a vector and sorting there?
13:25:37
flip214
or, perhaps, how many elements does a list have to have so that sorting it becomes slower than using a vector?
13:26:06
beach
flip214: Merge sort is special in that, if you sort a vector, it needs additional space, though there is research to make that constant, at the cost of performance.
13:26:35
beach
flip214: So merge sort is actually better on a list than on a vector in that respect.
13:27:23
beach
flip214: And merge sort is substantially better than (say) quicksort. Plus, it is stable, whereas quicksort is not.
13:29:28
beach
flip214: So there is not an upper bound where it becomes more advantageous to use a vector.
13:42:31
jcowan
Yes. (+ 1 "foo") is an error (i.e. undefined behavior) and the undefined behavior can be retroactive to compile time.
13:43:04
pfdietz
The problem with that is that the code could be dead. Is the compiler limited to doing this only only exprs it can show are not dead?
13:44:10
flip214
beach: I was thinking about all that CDR traversal, compared to just incrementing a memory address by some multiple of the element size for a vector.
13:44:14
pfdietz
Ok, that means some otherwise correct transformations on the code can cause the compiler to fail.
13:45:22
beach
flip214: Merge sort always processes the elements in the order, so there is no such access.
13:46:41
pfdietz
I'd like to be able to substitute constants into the body of a let and not have to worry about the compiler failing.
13:47:35
pfdietz
The sbcl approach is to translate to an error expression, and issue a warning if it stays around after dead code elimination.
13:49:40
Xach
Ha. I was going to add a restart to the quicklisp client to deal with the local archive size problem. But I added it already, 9 years ago.
13:49:45
flip214
beach: do you have an idiomatic translation for merge sort? The example I saw does LENGTH and twice SUBSEQ on each recursion, which ought to be expensive
14:02:48
beach
flip214: If you want to, you can help shka__ investigate merge sort on vectors that do not require O(n) space. Having a good merge sort implementation for vectors would be a very good thing indeed.
14:03:07
jcowan
https://github.com/scheme-requests-for-implementation/srfi-32/blob/master/sort-ref-impl/lmsort.scm is in Scheme, but translation to CL should be trivial. It's by Olin Shivers and the license is MIT.
14:05:51
jcowan
This SO has many links to papers on O(1) space vector merge sorts: https://stackoverflow.com/questions/2571049/how-to-sort-in-place-using-the-merge-sort-algorithm
14:08:28
jcowan
One of my favorite interview questions is to ask people to write code for a procedure that, when passed a number, returns the median of that number and all other numbers previously passed, given that the number of inputs may exceed the capacity of memory.
14:09:54
jcowan
This tests a lot of things, including whether people will ask about constraints on the input and whether they collaborate well (essentially nobody gets the answer right off)
14:11:40
jcowan
I conjecture that the problem is insoluble if the inputs are arbitrary bignums, but very few people ask right off if there is a limit on the numbers being input.
14:12:53
beach
jcowan: Yes, there are several papers on O(1) space merge sort. However, it might be the case that space exists, say on the stack. I would like to see a very that uses O(1) space (with the time overhead that it implies) only if the space is really tight.
14:13:15
Bike
well i don't see how you can compute the median without having all the data, yeah... and if it's constrained to be finite you can just keep counts
14:14:19
Lycurgus
would it occur to you to not quiz someone who obviously didn need it or is that a bogus concept for you, just using judgement?
14:15:55
jcowan
The stats on candidates who look good on paper but fail the FizzBuzz test are a cautionary tale.
14:16:11
pfdietz
This makes me wonder... is there an online algorithm for median that takes O(1) time per input?
14:16:15
Lycurgus
all the more reason to develop powers of discernment, in general you won't be able to quiz
14:18:07
Lycurgus
i can ace ur dumb quiz and then sit on my ass thru whole gig like a lump because you tested me
14:18:40
Lycurgus
or rather because you failed to give me the respect and credit my experience warranted
14:18:49
jcowan
Oh yes. The point of interviews is to reduce the cost of churn, which is very high and especially for programmers.
14:19:14
jcowan
In the restaurant biz it's routine to hire anyone who isn't actually drooling into the food and be prepared to fire them in three days.
14:21:36
jcowan
ah, my problem asks for that then. Many people know the two-heap strategy, which is defeated by saying the stream may be longer than can be kept in memory.
14:22:12
jcowan
recently it turned out that the candidate had been asked for the two-heap solution in the phone screen before I got to him
14:22:38
pfdietz
There is a well-known O(n) algorithm for offline median; my question was whether that can be extended to an online version.
14:27:41
jcowan
however this is not true if the stream is truly unbounded in length because of the bignums in the buckets, so I give candidates that there might be as many as 2^64 inputs