freenode/#lisp - IRC Chatlog
Search
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
15:36:25
admich
hello, I have a problem with clsql, someone of you know howto report bugs? I tried to send an email (as written on README file) on mailing list but the mailing list is down. Then I open an issue on the github repo reported on the README: https://github.com/UnwashedMeme/clsql/issues/10 but until now no feedback
17:50:16
thijso
I'm at the point of just giving up and stuffing ecl full of debug_log print statements...
17:53:17
pfdietz
When I debug lisp i use TRACE a lot. Some lisps support single stepping; I don't know if ecl does.
18:11:49
thijso
kind of a weird setup, I'm debugging an android app that is segfaulting in ecl_init_module, I don't have a repl to work with yet at that point
18:16:50
thijso
It's not gdb, it's probably me. I have a working gdb talking to my app on my phone through gdbremote.
18:17:41
thijso
I just don't know how to go about getting exactly where the segfault is happening, and what is triggering it
22:00:09
thijso
hmmm... maybe I should figure out if the random crashes running clfswm with newer quicklisp libs is solved. And if not, find out where the problem is...
22:00:49
thijso
although... maybe I should focus on the random -- well, not random, actually -- crashes of my android app...