freenode/lisp - IRC Chatlog
Search
4:26:09
BW^-
and, a non-deterministic algorithm in the sense of http://courses.csail.mit.edu/6.854/16/Projects/B/dynamic-graphs-survey.pdf connected components, what would that mean, how does it impact us that it is non-deterministic??
4:30:18
BW^-
beach: ah so it's like "make 10 iterations and each will have a 10% probability of success, hence you'll have 100% success in average in 10 iterations"
4:31:21
beach
I didn't read the article. I just know very elementary stuff. It very likely means linear time.
4:38:18
beach
Not necessarily. It could be that 0.001% of them need to be "touched". But the number of the ones that need to be "touched" is proportional to the total number of objects. Complexity theory doesn't care about constant factors.
4:43:01
beach
Designing good data structures is both very hard and very interesting. Take for instance the data structure that we all use on a daily basis, namely what I call an "editable sequence", and that we use in the form of an Emacs buffer.
4:43:08
beach
The best worst-time complexity one can hope for with such a data structure is O(log n). But if you choose such a data structure, almost every operation will take that much time.
4:43:09
beach
Emacs uses a data structure that has O(n) worst-time complexity. But in almost all cases, it takes O(1) time, so for the kind of use case that Emacs caters to, the best (according to complexity theory) data structure is really not the best.
4:44:10
beach
I know, in some cases I should use Θ(n) rather than O(n), but I think most people here know what I mean.
4:48:16
BW^-
beach: see this paper, http://epubs.siam.org/doi/pdf/10.1137/1.9781611973105.81 , slides https://pdfs.semanticscholar.org/d3b9/3729d50038a868d6dde1ac32f919168877fa.pdf
4:51:25
beach
BW^-: I am sorry, but I have a huge number of much more important tasks on my plate, so you need to look for help with this elsewhere. Reading and understanding an article like that can easily take a week or more of full-time work, and I am guessing that my rate is way too high for you.
5:15:42
BW^-
beach: ah, you mentioned that you have a rate, sounded like you do consultancy at least for a side kick; ok.
5:16:13
BW^-
would "log^2 n * V" normally mean "log(n) * log(n) * V" where log wouldbe the natural logarithm?? or 10-base logarithm??
5:16:29
beach
I could. But I am strapped for time, not for cash. So I set a higher rate for work that is not important for my research.
5:18:35
beach
jackdaniel: Not necessarily. In complexity, the base of the log is unimportant (it's just a constant). It is more likely that it means log squared.
5:32:47
beach
BW^-: Yes, log^2(n) * V nomrally means what you said, and since the base of the logarithm only makes a difference by a constant amount, the base doesn't matter, since complexity theory doesn't care about constant amounts, as I have already pointed out.
5:32:51
jackdaniel
BW^-: I admit to beach that I'm most likely wrong with my rush suggestion that it was a typo
5:33:58
beach
BW^-: That is why, in complexity theory, only log(n) should be used without reference to a base. If you see the base being used in an O(...) expression, you can count on the authors being second-rate.
5:35:18
beach
You can, of course use the base when you estimate the exact number of operations, but that is not usually done in complexity theory, simply because the number of operations is usually meaningless (because the cost of different operations can vary by orders of magnitude).
6:06:08
beach
jackdaniel: By the way, the international convention for logarithms states that the base 2 logarithm should be written lb n, the base 10 logarithm should be written lg n and the natural logarithm should be written ln n. As usual, Americans are the first to totally ignore international conventions, so you won't necessarily find that all CS papers respect those conventions.
6:20:36
jackdaniel
I've got it after seeing the first link (if hearing it from you wouldn't be enough ;) but thanks
6:22:11
beach
You know how everything said here in #lisp must be questioned, debated, altered, debunked, denied, etc. I was trying to avoid as much of that as possible.
6:22:59
jackdaniel
people usually tend to agree. the only exception are situation, when they have strong presupositions
6:23:55
beach
Correct, but there are so many participants here that if only a small percentage is in the "disagree" category, there is still likely to be a long debate.
6:24:42
beach
"Well, *I* am going to continue using what *I* have always used, because all those pages are wrong".
8:14:59
phoe
beach: "You know how everything said here in #lisp must be questioned, debated, altered, debunked, denied, etc."
8:30:34
closkar
last day before vacation, and I'd _really_ like to understand this: how do I set the default expiration time for a cookie using clack/lack? F.x set :expire to 48 hours?
8:30:35
closkar
PM or join #weblisp if you have any input but thinks it is offtopic for #lisp. TY. (I've asked this on other channels where people have tried to be helpful, but it's out of reach for me it seems).
9:35:48
phoe
Why do you think so? I disagree, I have had completely different experiences and a contrary opinion. I'd need to look at #lisp logs in general and analyze them in order to get some proper data...
14:25:52
schweers
when I have an object like this: #<MYCLASS {100359AB03}> the last part is a memory address or some other kind of identity, right? Can that change over time due to the garbage collector? I’m using sbcl
14:27:35
Bike
the identity is only used in print-unreadable-object. i don't think there are any guarantees on it at all.
14:30:01
schweers
I pass an object via a closure to another thread. I do this in a loop. Normally each thread should have its own instance of this object/class (it’s basically a calispel:channel). But for some reason I have the situation that two or more threads share an object, thus weird things happen
14:31:51
Bike
however, for your problem it sounds like you could just eq-test objects from different threads?
14:32:02
schweers
beach: normally I wouldn’t care, but I’m trying to debug a situation where I care about identities
14:33:17
beach
schweers: So what are you attempting instead? Visual inspection of the printed representation?
14:33:57
Shinmera
When you create a thread, push its object to a global list or something, and then look at it to see if any of them are the same
14:34:43
Colleen
Clhs: function sxhash http://www.lispworks.com/documentation/HyperSpec/Body/f_sxhash.htm
14:34:58
jackdaniel
sxhash doesn't guarantee distinct values for distinct objects (try calling it on two different vectors on sbcl)
14:37:22
beach
Sure. Write a method in print-object specialized to your class that uses (say) sxhash.
14:38:23
beach
schweers: Other possibility: add a slot to your class and initialize it to some huge random number.
14:39:49
beach
(defmethod print-object ((object my-class) stream) (format stream "..." (sxhash object)))
14:41:33
beach
(defmethod print-object ((object my-class) stream) (print-unreadable-object (object stream :type t) (format stream "~s" (sxhash object))))
14:44:35
pjb
schweers: clhs print-unreadable-object says: If identity is true, the output from forms is followed by a space character and a representation of the object's identity, typically a storage address.
14:45:37
beach
pjb: Except that I don't think schweers knows that PRINT-UNREADABLE-OBJECT is what is used by default for printing his objects.
14:45:40
pjb
The identity of an object should not change (even if its address changes), so I would expect it not to change. But I guess an implementation may consider the identity at the instant of printing, not over long periods.
14:46:47
pjb
AFAIK, most implementations use the address there, and since the address may change, it's safer not to rely on it over time, to identify the objects.
14:48:02
beach
Like in a trace, the same object may have a different appearance at different times during the trace.
14:49:52
schweers
if I use (gensym) repeatedly, it it guaranteed that the result always has a distinct printed representation, at least if done within one thread?
14:51:11
Shinmera
Running a primitive test, it takes //a lot// of allocation before the GC kicks in and decides to move my instance, thus changing the printed ID.
14:51:35
shka
[16:32] <schweers> beach: normally I wouldn’t care, but I’m trying to debug a situation where I care about identities
14:53:08
shka
i mean that schweers does not actually care about unique ids for classes, but he seems to just debug how content of class changes in another thread
14:53:40
schweers
I believe that I have come the conclusion that my problem was not the gc moving objects around after all, yet I still have no clue what the problem actually is :/
14:54:59
schweers
I do something like this: (iter (for obj in ...) (make-thread (lambda () ... s ...) :name ...))
14:55:46
schweers
yet on the other hand, there are at least two of these threads which have the same object
14:58:47
Shinmera
schweers: what iter does is probably something like this: (let ((s NIL)) (loop-somehow (setf s next-object) ...))
14:59:07
beach
schweers: It's the same for LOOP. The standard gives an option to behave this way for LOOP.
14:59:55
shka
schweers: try this (let ((result nil)) (map 'nil (lambda (x) (setf result x)) '(1 2 3 4 5))