2009-04-23
| 00:48 | lisppaste8 | cark annotated #79053 "this one is working" at http://paste.lisp.org/display/79053#4 |
| 00:50 | replaca | you're parsing binary data into maps? |
| 00:50 | Cark | yes |
| 00:51 | Cark | that's gnuvince's project |
| 01:03 | replaca | cool |
| 01:03 | replaca | that's a useful idea |
| 01:03 | Cark | i'm not sure clojrue is the best tool for that, but yes |
| 01:04 | Cark | and performance isn't too bad |
| 01:04 | Cark | 43 seconds to parse 150Mb of data |
| 01:04 | replaca | well, yeah, but finding very flexible ways to manage serialized data is interesting |
| 01:05 | replaca | I have nothing to compare that to, so it seems good to me :-) |
| 01:05 | Cark | i don't know, i always use sexprs for that =P |
| 01:05 | replaca | great if you've got lisp at the other end |
| 01:05 | Cark | well it's easy to parse anyways ! |
| 01:06 | replaca | less great if you have, say, images or video streams in the mix |
| 01:06 | Cark | sure |
| 01:06 | replaca | in my day job, we have distributed systems that often run over severely bandwidth restricted networks |
| 01:06 | replaca | so every bit counts |
| 01:07 | Cark | well then you can compress your stream |
| 01:07 | replaca | if you get it compressed better, you can send more and deliver a better user eexperience |
| 01:07 | replaca | yeah, we do that too |
| 01:07 | Cark | (not talking about video of course) |
| 01:07 | Cark | do you get better results by compressing binary data ? |
| 01:08 | replaca | yeah, cause even binary data isn't fully compressed |
| 01:08 | replaca | i'm sorry-> evenly distrubyted |
| 01:08 | replaca | *distributed |
| 01:08 | replaca | cause a bunch of it ends up being text |
| 01:09 | Cark | ah i see |
| 01:09 | replaca | (not the video, but other stuff |
| 01:09 | replaca | and when it's not text, it's biased low (1s and 2s far outweigh 254s and 255s) even after we do minimum byte int compression |
| 01:10 | replaca | so basically, we do every trick in the book :-) |
| 01:10 | Cark | heh must be interesting |
| 01:10 | replaca | and we're adding more (adaptive video encoding, etc.) |
| 01:11 | replaca | yeah, it's fun. I mostly do architecture and management at work, so I don't get to code too much |
| 01:11 | replaca | though I have done most of the compression and bandwidth management/allocation stuff |
| 01:12 | replaca | (but Clojure ends up being my coding outlet :-)) |
| 01:13 | Cark | it's a nice lisp |
| 01:13 | Cark | but the java stuff is sometimes killing me |
| 01:13 | hiredman | ~clojure |
| 01:13 | clojurebot | clojure is the best way to learn java |
| 01:13 | hiredman | ~botsnack |
| 01:13 | clojurebot | thanks; that was delicious. (nom nom nom) |
| 01:14 | Cark | clojuebot is very wise |
| 01:14 | replaca | java is both a blessing and a curse, no doubt |
| 01:14 | hiredman | one out of eleven shot that factiod would come up |
| 01:14 | hiredman | ~literal [?] clojure |
| 01:14 | clojurebot | 11 |
| 01:20 | Cark | ~def sort |
| 01:28 | Cark | i wonder why there's not a version of reduce with more than one calletionc, is the same fashion as map |
| 01:28 | Cark | is/in |
| 01:50 | replaca | the idea behind reduce is that you're "squishing" down a collection, whereas map is coollecting function results. That said, I don't why it wouldn't work. |
| 01:52 | Cark | there are many cases where i need to do ugly destructuring because of this |
| 01:52 | hiredman | map+reduce+apply |
| 01:53 | hiredman | (reduce (partial apply somefunction) (map list some collections here)) |
| 01:53 | clojurebot | map is *LAZY* |
| 01:53 | hiredman | clojurebot: I KNOW |
| 01:53 | clojurebot | Huh? |
| 01:53 | Cark | mhh |
| 01:55 | Cark | there still is structuring/destructuring under the hood |
| 01:55 | hiredman | for where? |
| 01:55 | Cark | the map form strutures into a list |
| 01:56 | Cark | and the apply destructures the list |
| 01:56 | Cark | but you're right it's not as ugly |
| 01:56 | Cark | i wonder about performances though |
| 01:57 | hiredman | I doubt it would perform worse then clojure's built in destructuring |
| 01:58 | hiredman | ,(doc destructure) |
| 01:58 | clojurebot | "([bindings]); " |
| 01:58 | hiredman | ... |
| 01:58 | Cark | ~def destructure |
| 01:58 | hiredman | ,(destructure '[[a b] [c d]]) |
| 01:58 | clojurebot | [vec__2292 [c d] a (clojure.core/nth vec__2292 0 nil) b (clojure.core/nth vec__2292 1 nil)] |
| 02:00 | Cark | uses nth with lists too =/ |
| 02:01 | Cark | anyways ...good night ! |
| 02:02 | replaca | goodnight! |
| 04:04 | liwp | how do I get the length of a sequence? I can't seem to find a length function in the core API... |
| 04:09 | cgrand | liwp: count |
| 04:09 | liwp | ahh, didn't think of that name. I tried to look for length and size. Thanks |
| 04:10 | liwp | How does one create a Java byte array in clojure? |
| 04:10 | liwp | I tried (into-array Byte/TYPE ...) but that didn't work |
| 04:12 | liwp | I'm trying to use the Java 2d API from clojure and dealing with primitive type arrays is turning out to be painful |
| 04:15 | liwp | For example, the pixels in this case are represented by signed bytes, but the values are really between 0 and 255. Java code deals with this by using ints to manipulate the pixels and then getting the byte value with byte b = i & 0xFF. |
| 04:40 | hoeck | liwp: try (into-array Byte/TYPE (map byte [1 2 3 4])) |
| 05:10 | liwp | hoeck: excellent, that works! |
| 05:12 | liwp | it seems that using (byte) I'm also able to force a 128-255 value into a signed byte, which is exactly what I wanted: (byte 255) -> -1 |
| 05:12 | liwp | thansk |
| 06:32 | jdz | count |
| 06:32 | jdz | (make-array Byte/TYPE 4096) |
| 06:32 | jdz | ,(make-array Byte/TYPE 4096) |
| 06:32 | jdz | clojurebot: are you there? |
| 06:32 | clojurebot | #<byte[] [B@bed64> |
| 06:32 | jdz | silence... |
| 06:32 | clojurebot | excusez-moi |
| 07:04 | cemerick | This comment by GvR on side effects really shocked me: http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html?showComment=1240451280000#c1726520516547497765 |
| 07:07 | cemerick | Sure, he's the python guy, so avoiding side effects isn't going to be a priority for him. But I expected at least an acknowledgement that doing so is really, really good (necessary?) in a *lot* of domains (if not all of them in a pervasively multicore world). |
| 07:14 | eevar2 | +1 to gvr for correcting the lisp-worlds use of "persistent" |
| 07:16 | cemerick | I'll take Okasaki over GvR w.r.t. data structure terminology. |
| 07:17 | cemerick | and I presume it was originally an ML term, given his usage of it.... |
| 07:20 | eevar2 | okies, "fp-world" then |
| 08:23 | gnuvince | Good morning |
| 08:35 | cgrand | gnuvince: hello |
| 08:37 | gnuvince | Quiet today |
| 08:58 | cgrand | ~seen dnolen |
| 08:58 | clojurebot | dnolen was last seen quiting IRC, 376 minutes ago |
| 10:27 | cgrand | dnolen: I think it's better to rename the conflicting CSS predicates |
| 10:27 | cgrand | (CSS not is enlive/but) |
| 10:28 | dnolen | cool! I wasn't sure if that was a compromise you were willing to make |
| 10:29 | cgrand | are you tracking the master branch now? |
| 10:29 | dnolen | yes |
| 10:29 | cgrand | fine. I already renamed empty to void and put complement into another ns |
| 10:30 | dnolen | great |
| 10:31 | dnolen | cgrand: enlive is moving along at light speed, a tutorial and everything ;) |
| 10:32 | Chousuke | it's really neat though. |
| 10:33 | cgrand | thanks again to Adrian (are you here?) for the tutorial |
| 13:15 | noidi | is there a way to import all the statics from a java class? |
| 13:16 | noidi | I'm trying to get rid of the extra gl's in the moronic JOGL API :P |
| 13:16 | noidi | (let [gl (.getGL drawable)] (.glHint gl GL/GL_PERSPECTIVE_CORRECTION_HINT GL/GL_NICEST)) |
| 13:16 | noidi | seriously, who comes up with an API like that > |
| 13:16 | noidi | :D |
| 13:16 | leafw | noidi: clojure discourages namespace pollution with imports you don't need. That said, there may be a way :) |
| 13:17 | kotarak | there was a contrib.import-static... |
| 13:18 | noidi | kotarak, yeah, I thought I remembered something like that mentioned here |
| 13:18 | noidi | thanks :) |
| 13:19 | noidi | hmm, it still requires all the statics to be named explicitly |
| 13:20 | noidi | I guess I'll just write a few macros, so I can do (gl Hint (GL PERSPECTIVE_CORRECTION_HINT) (GL NICEST)) instead of the monstrosity above |
| 13:20 | noidi | it's possible to rewrite symbols in a macro, right? |
| 13:21 | leafw | noidi: still reads quite verbose, and you lose the ability of any java programmer to understand the code |
| 13:22 | noidi | but it's closer to the original API, in which the command would be glHint(GL_PERSPECTIVE_CORRECTION_HINT, GL_NICEST); |
| 13:24 | technomancy | maybe it was written by a python programmer who was used to self.repeating self.self all the self.time. =) |
| 13:26 | rsynnott | a lot of C libraries do that sort of thing, as an attempt to be vaguely OO |
| 13:27 | noidi | opengl's not really OO, that's just making up for the lack of namespaces in C |
| 13:34 | danlarkin | yeah it has nothing to do with OO |
| 13:44 | pjstadig | ~def keys |
| 14:18 | durka42 | auto-documentation? |
| 14:19 | hiredman | replaca write something to auto generate docs in the google code wiki |
| 14:19 | hiredman | wrote |
| 14:20 | hiredman | http://code.google.com/p/clojure-contrib/wiki/OverviewOfContrib |
| 14:21 | durka42 | oh, that's cool |
| 14:21 | durka42 | makes contrib a lot more discoverable |
| 14:21 | jwinter_ | that is cool, e.g. http://code.google.com/p/clojure-contrib/wiki/ZipFilterApiDoc |
| 14:22 | cads | clojure clojure clo jure bannana fanna fo fojure.... I've got a clojure environment using rlwrap to provide tab completion on symbols, but is there a function that gives me the symbols that are mapped in a namespace, allong with their doc strings, perhaps formatted the same way (doc aSymbol) does it? |
| 14:23 | durka42 | there is ns-publics |
| 14:23 | hiredman | cads: clojure.org/namespaces |
| 14:23 | durka42 | also perhaps find-doc |
| 14:23 | kotarak | cads: the repl of vimclojure does that, but it's only interesting if you are a vim user... |
| 14:23 | replaca | glad to help! please ignore spurious checkin messages - developing with the google wiki isn't so great |
| 14:23 | replaca | but it's almost all there |
| 14:24 | cads | (doc 'clojure.org/namespace) doesn't work? why not? |
| 14:24 | clojurebot | Excuse me? |
| 14:25 | hiredman | cads: website |
| 14:25 | hiredman | http://clojure.org/namespaces |
| 14:36 | te | technomancy: i just saw your bludgeon repo |
| 14:36 | te | brilliant, sir |
| 14:37 | te | technomancy: i have another idea for bludgeon -- could you crush a human skull with the total weight of floppy disks the library occupies |
| 14:38 | te | or perhaps -- could a sock full of floppy disks representative of the library size, be used to beat someone to death? |
| 14:39 | cemerick | what's the deal with twibes? Way offtopic, but I just saw cgrand join up, so... |
| 14:39 | technomancy | te: floppy disks... interesting |
| 14:40 | te | technomancy: im not sure how big rspec's library is, but i mean, i think a good 10 or so floppies in a sock could effectively be used to kill someone |
| 14:40 | te | 20, certainly |
| 14:40 | te | 10 could at least provide a serious beating |
| 14:43 | technomancy | te: the main problem I had with that library was integration testing. let's just say there were some serious side-effects that I wanted to avoid at test-time. =) |
| 14:44 | cads | does clojure have a standard that defines it, in terms of a formal grammar definition? |
| 14:45 | cads | one thing I'll be willing to wager on, if such a thing does not exist yet, it should be easier to produce that in a language such as ruby |
| 14:45 | hiredman | well, it's a lisp |
| 14:46 | cads | true, we can find personal axioms to understand it by :D |
| 14:46 | hiredman | lisp grammars are easy |
| 14:46 | cads | they are, I've made my own notes :) |
| 14:48 | cads | who would make a standards document, if it came to that? |
| 15:10 | Chouser | it's likely the clojure reader will eventually be re-written in clojure. |
| 15:11 | Chouser | at that point, if done carefully, the code could act as a spec |
| 15:12 | hiredman | or you could use fnparse |
| 15:27 | replaca | I've been thinking about a modified reader myself, so that we could pretty print files of coode |
| 15:27 | replaca | *code |
| 15:27 | replaca | but it hasn't gotten past the idea stage |
| 15:27 | replaca | cause the regular reader loses comments and metadata annotations |
| 15:40 | Lau_of_DK | Java guys - I have questions! |
| 15:40 | Lau_of_DK | 1) Which classes will best solve this: I need to download a website, just get the raw bytes, and the reponse code. |
| 15:44 | Cark | i beleive the url class can give you a stream |
| 15:44 | Lau_of_DK | Ok, I'll look into it |
| 15:44 | kotarak | aren't duck-streams also handling URL? |
| 15:44 | Cark | but i don't know about the response code |
| 15:44 | Lau_of_DK | Hmm |
| 15:44 | leafw | yes, it can: URL getStream |
| 15:45 | Lau_of_DK | Actually - I remember seeing a http client in contrib way back when |
| 15:47 | replaca | Lau_of_DK: doesn't seem to be there now |
| 15:47 | Lau_of_DK | Thats true |
| 15:50 | Lau_of_DK | Anybody else here had some performance problems with jetty servlets ? |
| 15:50 | rsynnott | a http client, as opposed to a wrapper for the java one, is probably not something that you'd actually want to write |
| 15:50 | rsynnott | all the nasty stuff is already done for you, after all :) |
| 15:51 | Lau_of_DK | Or rather - My second question of the night - Is there a neat way to schedule a load test? Lets say I want 1000 hits per hour, and I want these even distributed - how would I most elegantly set that up ? |
| 16:01 | replaca | rsynnott, Cark: yeah, I'd just use the java stuff for that and wrap it in a clj function that does just what you want. |
| 16:09 | gnuvince | Cark: I ran more tests in my VMWare machine with an "heated up" JVM, but the results are largely the same. Like I said, I figure that the speed of IO in VMWare is the cause of the bottleneck. |
| 16:11 | Cark | gnuvince : allright ... i managed to knock off another second off ...but that's meaningless |
| 16:13 | gnuvince | I get home at around 7:30-8:00 (math homeworks :(, I'll check it out then. |
| 16:14 | Cark | i'llo give you the latest code |
| 16:14 | Cark | just let me know you're back |
| 16:53 | eevar_ | Lau_of_DK: httperf? |
| 16:53 | eevar_ | with --rate |
| 16:59 | Lau_of_DK | I tried http_load with -rate, but it doesnt support less than 1 second, which I need |
| 16:59 | eevar_ | 500 = 500 request per second -- or something like that |
| 17:01 | eevar_ | or, well.. doesn't seem to be that, but higher number = more load |
| 17:01 | eevar_ | --period gives more control |
| 17:06 | danlarkin | Lau! I have a sortof-http client library if you want it |
| 17:07 | danlarkin | that was an oddly placed "sortof"... it is not sortof-http, it is http |
| 17:07 | rsynnott | sort-of library, then? ;) |
| 17:09 | danlarkin | correct :) |
| 17:10 | danlarkin | I will post it to the mailing list as a submission for contrib once I work out the api more fully |
| 17:17 | Lau_of_DK | danlarkin: Send me an email on it? I'd really appreciate it |
| 17:17 | Lau_of_DK | I was fiddling with apache's, but since we done have import org.apache. * - it was just a mess |
| 17:17 | danlarkin | http://gist.github.com/98612 |
| 17:18 | Lau_of_DK | Sanks |
| 17:25 | hiredman | clojurebot: what is the most terrible thing? |
| 17:25 | clojurebot | In Ordnung |
| 17:25 | hiredman | clojurebot: the most terrible thing? |
| 17:25 | clojurebot | excusez-moi |
| 17:25 | hiredman | clojurebot: the most horrible thing? |
| 17:25 | clojurebot | most horrible thing is http://tinyurl.com/b65o8e |
| 19:18 | Drakeson | Do you know a powerful plot library that is not too hard to use from clojure? |
| 19:20 | Drakeson | something similar to matplotlib for python |
| 19:23 | eee | hello |
| 19:23 | dliebke | jfreechart is an excellent java library, I've wrapped parts of it for my Incanter project. Here's some samples: http://wiki.github.com/liebke/incanter/sample-plots-in-incanter |
| 19:23 | eee | is there an easy way to get access to the whole contrib namespace? |
| 19:24 | Drakeson | eee: me too :) |
| 19:25 | eee | i'm using clojure-dev, and finding the namespace browser awesome |
| 19:25 | Drakeson | dliebke: thanks a lot. that's what I was looking for |
| 19:25 | eee | but it only shows what's in your namespace now |
| 19:25 | dliebke | good luck |
| 19:26 | eee | but specifically I'm looking for the fastest merge, meld, union type implementations |
| 19:26 | eee | maybe seq-utils |
| 19:30 | eee | i also forgot how you use some new namespace |
| 19:30 | eee | require I guess |
| 19:39 | eee | now i remember. it's (use) |
| 19:51 | Drakeson | how can I build and use clojure using maven? Do I start by "mvn install" ? |
| 19:53 | Drakeson | man mvn is not informative |
| 19:56 | Drakeson | I did too, but it seems I miss a lot if I don't use mvn (on the java side) |
| 19:57 | eee | are you forking clojure? |
| 19:57 | Drakeson | god! no! |
| 19:58 | eee | nice reaction :) |
| 19:58 | Drakeson | is using/trying to use mvn imply that? |
| 19:59 | Drakeson | s/is/does |
| 20:01 | Drakeson | I said on the java side. downloading .jar files manually in no fun. |
| 20:02 | eee | not the maven part. I'm just trying to learn what the usefulness is. Either you had to make a change to try something out, or you want to fork, or you want the latest snapshot that isn't built (and so why don't the distributors have a continuous build system upon checkin) or you want it on some little phone device . . . or I am just nosey :) |
| 20:03 | Drakeson | oh, I just don't know how maven works. I am still new to java. |
| 20:04 | eee | why do you need to build clojure? |
| 20:04 | eee | why does one |
| 20:04 | clojurebot | why not? |
| 20:04 | eee | etc |
| 20:04 | Drakeson | I want the latest clojure. |
| 20:05 | eee | and they don't have automated build |
| 20:05 | Drakeson | can I get it without building? |
| 20:05 | eee | i wonder |
| 20:05 | Cark | buildin is just type "ant <enter>" |
| 20:06 | eee | making me think about a git-hub or google repos-like thing that always builds whenever someone does a checkin |
| 20:06 | Drakeson | Carl: then you have to worry about where the .jar goes. |
| 20:06 | eee | if they don't, that's an opportunity |
| 20:06 | eee | java-only of course |
| 20:08 | eee | i have a question to ask anyone who is following the google groups discussions for clojure |
| 20:09 | arohner | eee: shoot |
| 20:09 | eee | is that anyone here right now? |
| 20:09 | eee | cool |
| 20:09 | arohner | a lot of us here are also on the groups |
| 20:09 | eee | i'm posting results about this heap |
| 20:09 | eee | is it annoying? |
| 20:09 | eee | or passively interesting |
| 20:09 | arohner | which post is that? |
| 20:10 | arohner | oh, priority queue: some results |
| 20:10 | eee | latest is this: best way to compete against meld? |
| 20:10 | eee | yes |
| 20:10 | eee | i just got another result |
| 20:10 | eee | best of all |
| 20:10 | eee | and thinking of posting |
| 20:11 | eee | is it ok? |
| 20:11 | felzix | Is there a way to eval def's first argument? |
| 20:11 | arohner | eee: yeah, keep posting |
| 20:11 | eee | cool |
| 20:11 | arohner | I know it's discouraging to not get any responses |
| 20:11 | arohner | it's happened to me several times |
| 20:11 | eee | i just merges two sorted sets |
| 20:12 | eee | and then two heaps |
| 20:12 | eee | check this out |
| 20:12 | eee | performing union of two sorted sets "Elapsed time: 18881.81 msecs" making another heap performing meld of two heaps "Elapsed time: 0.146 msecs" |
| 20:12 | arohner | nice |
| 20:12 | eee | ahhhhh |
| 20:12 | eee | feedback |
| 20:12 | eee | :) |
| 20:12 | arohner | one piece of advice is that it's slightly hard to follow the topic when you have several different threads |
| 20:12 | eee | oh |
| 20:12 | arohner | reply to yourself in one thread just to keep the context around |
| 20:12 | eee | ok |
| 20:13 | eee | i'll add to the last results email then |
| 20:13 | felzix | like using set instead of setq in CL |
| 20:13 | eee | no |
| 20:13 | eee | set means a uniquified list like thing |
| 20:13 | eee | noun |
| 20:14 | eee | not verb |
| 20:14 | arohner | felzix: I don't know enough CL to know what you're asking |
| 20:14 | eee | setq |
| 20:14 | eee | means def |
| 20:14 | arohner | the first argument to def is the symbol name you want to point at the new var |
| 20:14 | eee | or something like that |
| 20:14 | eee | yeah |
| 20:14 | eee | so he thinks of "set" the verb |
| 20:14 | eee | to set |
| 20:15 | arohner | so I don't understand what you mean by eval'ing it |
| 20:15 | eee | we mean the datastructure |
| 20:15 | eee | who said eval? |
| 20:15 | felzix | say, (let [a 'b] (def a 9)) resulting in b == 9 |
| 20:16 | eee | oh I missed it |
| 20:16 | arohner | ah, ok |
| 20:16 | eee | i see |
| 20:16 | arohner | you could do that with a macro pretty easily |
| 20:17 | arohner | actually, you might not even need the defmacro, just the backticks |
| 20:17 | arohner | though, why do you want to def inside of a let? that creates a new global |
| 20:17 | unlink | How do I serialize my Clojure objects efficiently? |
| 20:17 | Raynes | `` |
| 20:18 | felzix | arohner: Ah, you're right, extremely easy to make. |
| 20:18 | unlink | Like protobuf, cPickle, or memcpying structs in C. |
| 20:19 | arohner | felzix: though be careful with that. It's generally frowned upon to change the value of a var using def in running code |
| 20:19 | unlink | Did I just answer my own question? protobuf supports Java. |
| 20:19 | arohner | really the only reason you're allowed to re-def a var is for development purposes |
| 20:20 | felzix | arohner: I'm using it in a define-class macro to make boilerplate functions. |
| 20:21 | arohner | felzix: that sounds appropriate then |
| 20:21 | felzix | cool. Thanks for the help! |
| 20:22 | eee | k, made my new post |
| 20:22 | eee | thanks for the encouragement |
| 20:23 | gnuvince_ | Doe all aset functions go through the reflection framework? |
| 20:24 | eee | i don't know what aset is |
| 20:24 | eee | so I can't help |
| 20:24 | rhickey_ | eee: I don't think sorted collections negate the value of heaps in any way, heaps serve some unique purposes |
| 20:25 | eee | thanks rich |
| 20:25 | gnuvince_ | eee: setting values to an array |
| 20:25 | eee | did you see the last result? |
| 20:25 | eee | awesome |
| 20:26 | eee | i just need to figure out decreaseKey() |
| 20:26 | eee | in functional setting |
| 20:26 | unlink | gnuvince_: http://code.google.com/p/clojure/source/browse/trunk/src/jvm/clojure/lang/RT.java |
| 20:26 | eee | without backpointers |
| 20:27 | eee | oh yeah gnu |
| 20:27 | eee | I forgot about aset |
| 20:28 | rhickey_ | eee: I'm sorry I haven't had time to look at your stuff yet. One word of advice I'd have, is that you'll find papers on purely functional implementations, but you are not limited to that in making a functional persistent data structure for Clojure. Mutation of temporaries, or one-time setup during insertion is a critical component to the speed of Clojure's maps/set/vectors. |
| 20:29 | eee | ok |
| 20:29 | eee | I was thinking about that |
| 20:29 | rhickey_ | no backpointers though :) |
| 20:29 | eee | yeah |
| 20:29 | rhickey_ | and no mutation after init |
| 20:29 | eee | ok |
| 20:30 | eee | can you explain that with one more sentence. the init meaning what happens at 'new' time, right? |
| 20:30 | eee | when the type is established |
| 20:30 | rhickey_ | but if you look at PeristentHashMap et al you'll see that new arrays are created and mucked with on inserts/deletes |
| 20:31 | rhickey_ | eee: creating any new version, you can create some *new* component of the data structure, mutate it, then weave it into the result, but once returned never to change again |
| 20:31 | eee | yeah |
| 20:31 | eee | i do that a lot |
| 20:31 | eee | well |
| 20:31 | eee | minimum needed |
| 20:32 | eee | that I can tell |
| 20:32 | eee | so I think I'm following the rules |
| 20:32 | eee | will look at PHashMap though |
| 20:33 | eee | thanks for the pointers |
| 20:33 | eee | no pun intended |
| 20:33 | eee | :) |
| 20:38 | eee | the PeristentHashMap looks somewhat like what I had one or two versions ago with all the static functions in the implementation file. But I shaved of a little time consolidating. maybe I should put it back since it was negligable, hmmmmm |
| 20:38 | unlink | gnuvince_: here is the implementation of evens I was trying to accomplish yesterday: http://gist.github.com/100253 |
| 20:38 | unlink | evens2 |
| 20:40 | eee | unlink: intersting |
| 20:40 | Drakeson | I am getting: Could not find clojure.lang.Compile. is that gone? |
| 20:41 | dnolen | nope, Drakeson are you trying to compile clojure-contrib? |
| 20:41 | unlink | exercise for the reader: use recur |
| 20:41 | Drakeson | no, incanter |
| 20:41 | eee | unlink: would look almost the same, right? |
| 20:42 | dnolen | perhaps you need to explicitly pass the path to clojure.jar to ant? you have to do this contrib. |
| 20:43 | unlink | eee: well, evens2 is not in tail position |
| 20:43 | Drakeson | like -Dclojure.jar=... ? |
| 20:43 | eee | does this help with compiling? http://www.lithinos.net/Compiling-Clojure-applications-using-Ant.html |
| 20:44 | dnolen | ant -Dclojure.jar ../clojure/clojure.jar |
| 20:44 | dnolen | with whatever your path is tho. |
| 20:46 | gnuvince_ | unlink: |
| 20:46 | gnuvince_ | user=> (take 3 (evens2 (iterate inc 1))) |
| 20:46 | gnuvince_ | () |
| 20:48 | unlink | oh looks like I wasn't actually testing the function. |
| 20:49 | eee | rhickey_: I actually wondered if there could be a drastic speedup as multi-core computers come on line. The way there's a separate thread for GC, maybe there should be a separate thread for object pools. so the *new's* could be predicted and created in advance in another thread. |
| 20:49 | clojurebot | for is not a loop |
| 20:49 | eee | gnuvince_: I think it's even items in the list |
| 20:50 | eee | oh |
| 20:50 | eee | you cakked his evens2 |
| 20:50 | eee | i didn't see you define it |
| 20:50 | eee | i thought you used clojurebot |
| 20:51 | cads | do you guys think I could embed the semantics for simple PIC microcontroller C code (simple loops, even gotos (eww), very shallow recursion, lookup tables), into a clojure DSL, for a simple code generation framework using CLJ syntax? |
| 20:52 | eee | i wonder if that relates to something I saw, cads. I'll remember in a sec |
| 20:52 | unlink | gnuvince_: you have to do (apply evens2 (take 3 (iterate inc 1))) |
| 20:52 | eee | nestedvm |
| 20:53 | eee | http://nestedvm.ibex.org/ |
| 20:53 | gnuvince_ | unlink: you got a stack overflow too |
| 20:54 | unlink | gnuvince_: if you try to apply iterate you will |
| 20:54 | arohner | cads: why not? |
| 20:55 | arohner | I was looking at the mini-VM from the ICFP from a previous year, and it didn't seem that bad to do it in clojure |
| 20:56 | lisppaste8 | gnuvince pasted "Lazy evens" at http://paste.lisp.org/display/79106 |
| 20:58 | arohner | unlink: it's a neat trick, but what is the point? |
| 21:01 | unlink | arohner: I find it to be the most natural way of expressing it |
| 21:01 | unlink | like haskell/sml's pattern matching |
| 21:01 | gnuvince_ | Except Clojure has no pattern matching, so it's kind of futile to try and replicate that style. |
| 21:02 | unlink | It has arity overloading, so no, it isn't. |
| 21:02 | arohner | oh that reminds me, why isn't there a function for the sequence of ints? |
| 21:02 | arohner | doing (iterate inc 0) all over the place bugs me |
| 21:03 | dnolen | well not totally true, between multimethods, multiple arity, and destructuring bind you have quite a few good ideas from pattern matching. |
| 21:03 | gnuvince_ | unlink: but you need to use apply to call the function instead of the normal form. |
| 21:03 | gnuvince_ | arohner: not that I know of. |
| 21:03 | arohner | gnuvince_: I know there isn't a function for that. That's the problem :-) |
| 21:04 | gnuvince_ | arohner: define a natural functioN? |
| 21:05 | dreish | ,(map first (partition 2 [0 1 2 3 4 5 6 7 8])) |
| 21:05 | clojurebot | (0 2 4 6) |
| 21:06 | gnuvince_ | ,(take-nth 2 (rest [0 1 2 3 4 5 6 7 8])) |
| 21:06 | clojurebot | (1 3 5 7) |
| 21:06 | eee | wait, is this a function to find the even valued things? or even position things? |
| 21:06 | dreish | Positioned |
| 21:07 | gnuvince_ | It's a function to extract the even-indexed elements in a 1-indexed collection. |
| 21:08 | eee | ,(map first (partition 2 [1 0 3 4 2 5 6 7 9 11 13])) |
| 21:08 | clojurebot | (1 3 2 6 9) |
| 21:08 | eee | nice |
| 21:08 | eee | how's it work |
| 21:08 | dreish | partition 1 2 avoids dropping the last one if there are an odd number. Or you could just use take-nth |
| 21:09 | dreish | ,(partition 2 (range 10)) |
| 21:09 | clojurebot | ((0 1) (2 3) (4 5) (6 7) (8 9)) |
| 21:10 | eee | handy function |
| 21:11 | dreish | ,(partition 3 1 (range 10)) |
| 21:11 | clojurebot | ((0 1 2) (1 2 3) (2 3 4) (3 4 5) (4 5 6) (5 6 7) (6 7 8) (7 8 9)) |
| 21:12 | eee | cool |
| 21:13 | eee | ,(partition 3 3 (range 10)) |
| 21:13 | eee | ,(partition 3 3 (range 10)) |
| 21:13 | clojurebot | ((0 1 2) (3 4 5) (6 7 8)) |
| 21:13 | eee | that's power |
| 21:20 | eee | i think I found the decreaseKey() answer! |
| 21:20 | eee | i'd forgotten about it |
| 21:20 | eee | Eurika |
| 21:21 | Jedi_Stannis | what was the question? |
| 21:22 | eee | making a heap/priority queue ... functional |
| 21:22 | eee | in java |
| 21:23 | eee | meld, insert, findMin, deleteMin ... ok |
| 21:23 | eee | but |
| 21:23 | eee | can't do things like Branch and bound, A-Star, shortest path, Prim's alg . . .without decreaseKey |
| 21:24 | eee | end of soliloquy |
| 21:25 | Jedi_Stannis | I see |
| 21:26 | Jedi_Stannis | code online anywhere? |
| 21:26 | eee | yeah |
| 21:26 | eee | one sec |
| 21:26 | eee | http://code.google.com/p/jc-pheap/ |
| 21:26 | eee | http://code.google.com/p/jc-pheap/source/browse/#svn/trunk/jc-pheap/src |
| 21:28 | eee | well now I see a problem with what I was just thinking. false Eurika |
| 21:29 | Jedi_Stannis | so is the idea to be able to use this data structure from within clojure? |
| 21:29 | eee | yup |
| 21:29 | eee | there;s a clojure test in there |
| 21:29 | Jedi_Stannis | any reason you wrote in java instead of directly in clojure? |
| 21:29 | eee | haven't tried that yed |
| 21:29 | eee | yet |
| 21:29 | eee | but i have a paper somewhere on treaps |
| 21:30 | eee | that maybe will work like that |
| 21:30 | eee | figured it would be faster |
| 21:30 | eee | and Rich suggested it, too |
| 21:30 | eee | be back in a few |
| 21:33 | eee | back |
| 21:36 | eee | i think the trick is |
| 21:36 | eee | that somehow you leave the old value where it was |
| 21:36 | eee | and clone the object inserting it anew |
| 21:37 | eee | when the deleteMin gets to the old one |
| 21:37 | eee | it skips it |
| 21:37 | eee | but . . .one problem is that that sounds amortized |
| 21:37 | eee | and another problem is that the clone messes with "identity" |
| 21:38 | eee | so at the very lease you gotta do a secret mutable swap |
| 21:38 | eee | but no |
| 21:38 | eee | depends on if two clients can have a handle to the same node |
| 21:38 | eee | but they can't so maybe it will work. |
| 21:38 | eee | end of soliloquiy 2 |
| 21:39 | eee | :) |
| 21:47 | Jedi_Stannis | interesting |
| 21:47 | Jedi_Stannis | I don't think I know enough about priority queues to fully appreciate all of this |
| 21:47 | eee | the brodal paper is in the code repos |
| 21:48 | eee | WAY easier than his imperative version |
| 21:48 | eee | i had all that straight at one time |
| 21:48 | eee | i like data structures a lot |
| 21:49 | Jedi_Stannis | yeah, I haven't explored data structures too deeply |
| 21:49 | eee | know what a splay tree is? That's awesome. so is disjoint set |
| 21:49 | Jedi_Stannis | nope |
| 21:50 | Jedi_Stannis | main advantage of these is their running time for certain operations? |
| 21:50 | eee | in some shops, for what they are doing, machines are fast enough just to use vectors everywhere, sadly |
| 21:50 | Jedi_Stannis | yeah |
| 21:50 | eee | run time and organization |
| 21:51 | eee | disjoint set is an easy example to appreciate |
| 21:51 | eee | if you are interested I could try |
| 21:51 | Jedi_Stannis | if you had functional versions of other collections that have different trade offs that could all be used in clojure, that would be pretty cool |
| 21:51 | eee | be back in a sec |
| 21:52 | eee | back |
| 21:53 | eee | so with disjoint set. you may start with 300 sets each with one element |
| 21:53 | eee | at some point, you may decide that two such elements should be in the same set |
| 21:54 | eee | but only if they aren't already in the same set |
| 21:54 | eee | or you just might want to ask if two elements are in the same set |
| 21:55 | eee | or what set is an element in and have some sort of VALUE that distinguishes that set |
| 21:55 | eee | if you try to do that with linked lists |
| 21:55 | eee | your done |
| 21:55 | eee | you'll spend so many cycles updating links |
| 21:56 | eee | under lots of join operations, the identities of two sets have to meld into one |
| 21:56 | eee | Tarjan solved it |
| 21:56 | eee | disjoint sets |
| 21:56 | eee | good stuff |
| 21:56 | eee | smallest algorithm/data structure ever, too |
| 21:56 | Jedi_Stannis | sounds interesting |
| 21:57 | Drakeson | is there a mechanism to unpack jars and "install" them in a local or system-wide (/usr/lib/...) place (plus updating some index) and have a classloader that uses the extracted jars and the index? |
| 21:58 | eee | you mean in java? |
| 21:58 | eee | jar -xvf some.jar |
| 21:58 | gnuvince_ | ~seen Cark |
| 21:58 | clojurebot | Cark was last seen in #clojure, 113 minutes ago saying: buildin is just type "ant <enter>" |
| 21:59 | eee | but it won't make stuff know about them like libs . . . unless you have a CLASSPATH environment variable set |
| 21:59 | eee | and in that case, no need to unpack them |
| 22:00 | Drakeson | I don't understand why java unpacks jars everytime it wants to use them. |
| 22:00 | Jedi_Stannis | is there a list of all the clojurebot commands somewhere? |
| 22:01 | durka42 | there is his source code :) |
| 22:01 | Jedi_Stannis | where's that at? |
| 22:01 | Drakeson | Jedi_Stannis: look at http://github.com/hiredman/clojurebot |
| 22:01 | eee | oh I didn't know the source was bundled, cool |
| 22:02 | eee | oh |
| 22:02 | eee | i missunderstood again |
| 22:02 | eee | :) |
| 22:04 | eee | the other reason to do data structures in java I just realized is to give them to non-clojure people, too |
| 22:04 | eee | like scala, I guess |
| 22:04 | durka42 | clojurebot: where do you live? |
| 22:04 | clojurebot | Titim gan �ir� ort. |
| 22:05 | durka42 | clojurebot: where are you? |
| 22:05 | clojurebot | http://github.com/hiredman/clojurebot/tree/master |
| 22:05 | Jedi_Stannis | lol |
| 22:05 | eee | clojurebot: hello |
| 22:05 | clojurebot | BUENOS DING DONG DIDDLY DIOS, fRaUline eee |
| 22:05 | Jedi_Stannis | wow |
| 22:05 | eee | lol |
| 22:18 | eee | i'm confusing myself |
| 22:18 | eee | in a purely functional world |
| 22:19 | eee | what would it mean to decrease the value of something, anyway? |
| 22:19 | chessguy | return the successor of it |
| 22:19 | chessguy | err, predecessor |
| 22:19 | chessguy | decrease 2 == 1 |
| 22:19 | eee | but, like from java it would be a new object, right? |
| 22:20 | eee | since Integers are immutable |
| 22:20 | chessguy | if you want immutability, yes |
| 22:20 | eee | you'd just get a new Integer |
| 22:20 | eee | that you would think of as the old integer |
| 22:20 | eee | so |
| 22:20 | chessguy | well no |
| 22:20 | chessguy | you'd probably call it something else |
| 22:20 | eee | well, in a priority queue |
| 22:21 | eee | you stick something in |
| 22:21 | eee | and later |
| 22:21 | eee | you decide |
| 22:21 | eee | no, I got the value wrong |
| 22:21 | eee | I want to udate it |
| 22:21 | eee | let it bubble up the queue |
| 22:21 | eee | but "it" |
| 22:21 | eee | is fuzzy |
| 22:21 | chessguy | you would return a new queue then |
| 22:21 | eee | yes |
| 22:21 | Jedi_Stannis | ,(-> {} (assoc :a 10) (assoc :a 1)) |
| 22:21 | clojurebot | {:a 1} |
| 22:21 | eee | but the user needs a handle to their object |
| 22:22 | eee | so they can mess with the value |
| 22:22 | eee | besides a handle to te queue |
| 22:22 | eee | the idea of a handle is fuzzy |
| 22:22 | chessguy | well if they can only mess with the value, and it changes in the queue, then you're breaking referential transparency |
| 22:22 | eee | in an immutable world |
| 22:23 | eee | anyone else seing queue, I realize still needs the old queue |
| 22:23 | eee | but the notion of a position where the value this guy is tracking needs to be there some how |
| 22:23 | eee | in his new view |
| 22:23 | chessguy | perhaps what you want is a zipper? |
| 22:24 | eee | hmmm |
| 22:26 | eee | when you stick something in the heap, you need the new heap and some sort of way to refer to your inserted item |
| 22:26 | chessguy | a zipper would do that |
| 22:27 | Jedi_Stannis | is it possible to have the same value in the heap multiple times? |
| 22:27 | eee | if you stick 5 2's in . . . only one of those 5's is yours, but I wonder if it even matters which one you decrease. I think it does matter if you have other data hanging off it that isn't part of the comparison |
| 22:28 | eee | yes |
| 22:28 | chessguy | are you only ever going to be updating the one you last put in? |
| 22:29 | eee | if I figure it out. by the way, this code is in java . . .for clojure use |
| 22:29 | Jedi_Stannis | can you specify the old priority also? |
| 22:30 | eee | good question |
| 22:30 | eee | i guess in an immutable world, you could have both handles |
| 22:30 | eee | which means that you should have the version of the queue that goes with it |
| 22:30 | Jedi_Stannis | then even if there were multiple values, as long as you change the one with the right priorirty your good |
| 22:30 | eee | sounds reasonable |
| 22:31 | eee | the "as long as you" part is the worrysome part tho |
| 22:31 | eee | you've got your item and you've got a snapshot of the queue |
| 22:31 | eee | you do decreaseKey and get a new item and a new queue? |
| 22:32 | eee | so you need a unique handle/key to the item as a receipt |
| 22:32 | eee | and maybe that key is only valid in one snapshot of the queue |
| 22:33 | eee | i shouldn't say key |
| 22:33 | Jedi_Stannis | I don't think you need a unique key |
| 22:33 | eee | that's the comparator . . i mean ID |
| 22:33 | Jedi_Stannis | think of it in terms of the current clojure data items |
| 22:33 | eee | you need a unique ID only if you have objects |
| 22:33 | eee | those objects could have many fields |
| 22:34 | eee | besides your comparison field |
| 22:34 | eee | you don't want to decrease the wrong object |
| 22:34 | eee | just because the comparison field matches right? |
| 22:34 | Jedi_Stannis | hmm |
| 22:34 | Jedi_Stannis | way not just use clojures data type semantics |
| 22:34 | Jedi_Stannis | the value is the identity |
| 22:34 | eee | i see |
| 22:34 | Jedi_Stannis | the entire value is the "comparison field" |
| 22:34 | Jedi_Stannis | don't use identity anywhere |
| 22:34 | Jedi_Stannis | only use value |
| 22:35 | Jedi_Stannis | if the value is the same, they are equal |
| 22:35 | eee | Rich has an essay on that |
| 22:35 | Jedi_Stannis | cache hashes to make comparisons fast |
| 22:35 | eee | well |
| 22:35 | eee | equal and less than are two different things |
| 22:35 | Jedi_Stannis | do priorities have to be intergers? |
| 22:35 | eee | ill-defined situation one thing could be not less than and not greater than . . . and STILL not equal either |
| 22:36 | Jedi_Stannis | or priorities can be any object? |
| 22:36 | eee | no, anything with an order |
| 22:36 | eee | has to have less than defined |
| 22:36 | eee | it's not a priority . . .it's a heap . . or a priority queue |
| 22:37 | Jedi_Stannis | so the collection has values in it, which each have a priority associated with them |
| 22:37 | eee | right |
| 22:37 | Jedi_Stannis | or the priority is inherit to the value itself? |
| 22:37 | eee | first thing |
| 22:37 | Jedi_Stannis | ok |
| 22:37 | eee | they implement java comparable |
| 22:38 | eee | compareTo() is implemented |
| 22:38 | Jedi_Stannis | on the value or on the priority? |
| 22:38 | eee | i think your questions are good tho . . .making me think |
| 22:38 | Jedi_Stannis | I think you need to decouple the priority and the value |
| 22:38 | Jedi_Stannis | let me give an example |
| 22:39 | Jedi_Stannis | say your using this for a scheduler |
| 22:39 | Jedi_Stannis | and you have 3 processes |
| 22:39 | eee | a heap/priorityQueue has THINGS in it, that can be compared to each other in an order |
| 22:39 | eee | ok |
| 22:39 | Jedi_Stannis | process a,b,c |
| 22:39 | rlb | eee: wouldn't an immutable priorty queue just be like any other clojure data structure, i.e. it only makes sense to talk about the "state" that's currently bound to an identity? |
| 22:40 | Jedi_Stannis | and we stick them all in the priority queue with different priorities |
| 22:40 | Jedi_Stannis | <(a,1), (b,2), (c,3)> |
| 22:40 | Jedi_Stannis | now we want to downgrade a's priority |
| 22:40 | rlb | s/wouldn't/couldn't/ |
| 22:41 | eee | the state of the queue is no problem to understand rlb |
| 22:41 | Jedi_Stannis | (decreaseKey 'a 1 4 *1) --> <(a,4),(b,2),(c,3)> |
| 22:41 | eee | the queue is defined by what's in it |
| 22:42 | Jedi_Stannis | you can't have the objects in the prioirty queue have the priority be part of their value |
| 22:42 | Jedi_Stannis | because they can't be mutable |
| 22:42 | eee | ok |
| 22:42 | eee | that's fine |
| 22:42 | eee | but that's all blowing my mind how hard that is |
| 22:42 | eee | I almost need a map and a queue |
| 22:43 | eee | s/all/almost |
| 22:43 | eee | Jedi |
| 22:43 | eee | so |
| 22:44 | eee | in java terms, I'd have an object with two fields |
| 22:44 | eee | in clojure I'd have two objects |
| 22:44 | eee | the thing, and it's priority? |
| 22:44 | Jedi_Stannis | yeah |
| 22:44 | eee | but |
| 22:44 | eee | what TYPE could that be? |
| 22:45 | Jedi_Stannis | the thing can be anything |
| 22:45 | Jedi_Stannis | no restrictions |
| 22:45 | Jedi_Stannis | the priority needs to be comparable |
| 22:45 | eee | um |
| 22:45 | eee | then it could be an object like in java |
| 22:45 | eee | with two fields |
| 22:45 | eee | recursive argument |
| 22:45 | Jedi_Stannis | would you want that for a reason? |
| 22:46 | eee | you mean just define that the priority part is considered equal whenever it is not less and not greater |
| 22:46 | eee | hey, I've enjoyed this , . . . but I gotta go at least for a bit |
| 22:47 | Jedi_Stannis | ok no problem |
| 22:47 | eee | i'm at eviertel@gmail.com for more cool ideas |
| 22:47 | eee | thanks |
| 22:47 | Jedi_Stannis | hopefully that helps you at |
| 22:47 | Jedi_Stannis | out* |
| 22:47 | eee | yup |
| 22:47 | eee | thanks |
| 23:10 | eee | yo |
| 23:22 | rlb | eee: FWIW, I think Jedi_Stannis said something like what I was thinking... |
| 23:24 | eee | i think I get it |
| 23:24 | eee | still an odd conflict to me |
| 23:24 | eee | because most structures |
| 23:24 | eee | are for search |
| 23:24 | eee | like a map |
| 23:24 | eee | or set |
| 23:25 | eee | so you can 'find' your element |
| 23:25 | eee | by matching on value |
| 23:25 | eee | and define identity that wat |
| 23:25 | eee | way |
| 23:25 | eee | but, classically |
| 23:25 | eee | in a heap |
| 23:25 | eee | you don't search |
| 23:25 | eee | you stick your element in |
| 23:25 | eee | it's yours |
| 23:25 | eee | you still know where 'it' is |
| 23:26 | eee | it's yours because it's yours . . .not because the value matches |
| 23:26 | eee | you never lose it. you always have your finger on it |
| 23:26 | eee | but that's really suited for imperative environment |
| 23:26 | rlb | eee: you mean if you keep the pointer to it? Otherwise, you still have to find it again. |
| 23:27 | eee | exactly |
| 23:27 | eee | so the return from insert right now is a new heap |
| 23:28 | eee | but it perhaps needs to be a new heap and a little box for your object |
| 23:28 | eee | now's the tough part |
| 23:28 | eee | no backpointers up the tree |
| 23:28 | eee | change the value in the box |
| 23:28 | eee | means you need a new heap |
| 23:28 | clojurebot | new Class(x) is (Class. x) |
| 23:29 | eee | that has that value in the right place. so you need a new heap and a new box |
| 23:29 | eee | but same value? |
| 23:29 | eee | or new value |
| 23:29 | rlb | I suppose it depends on how often you really need to keep track of the pointer. You don't in cases where all you really want the queue for is to hand you the next item when you ask for it. |
| 23:29 | eee | well, that alone is pretty cool |
| 23:30 | eee | lazy sort |
| 23:30 | eee | but |
| 23:30 | eee | decreaseKey is the real story |
| 23:30 | eee | so many nice algorithms get fast with that |
| 23:30 | eee | like Djikstra's shortest path |
| 23:30 | eee | depends on updating the value |
| 23:32 | eee | i think java's priority queue as I'm seeing has notion of equality |
| 23:32 | eee | like clojure |
| 23:32 | eee | so |
| 23:32 | eee | i'll start with that idea |
| 23:32 | rlb | eee: does it have to, or rather, for clojure, I would think you might want a special queue (like the existing collections) that makes altered copies cheap. |
| 23:32 | eee | that you can get any value that matches yours . . .decrese the first one that 'equals' yours |
| 23:32 | rlb | though how hard that might be to do right for a priority queue, I don't know offhand -- haven't really thought about it. |
| 23:33 | eee | i have it working where altered copies are cheap |
| 23:33 | eee | for everything but decreaseKey |
| 23:33 | eee | thinkingn out loud about that one |
| 23:34 | eee | thinking I need a map and a heap |
| 23:34 | eee | a persistentMap from clojure's java code |
| 23:34 | rlb | to make decreaseKey efficient? |
| 23:34 | eee | to find an equal element |
| 23:34 | eee | without traversing |
| 23:34 | eee | a hashmap |
| 23:35 | eee | that points to it |
| 23:35 | eee | hashmap that points to a linked list that points to all the equal elements |
| 23:35 | eee | that solves the easy part :) |
| 23:35 | eee | of having a handle |
| 23:36 | eee | next, you insert a new element |
| 23:36 | eee | representing the lesser value |
| 23:36 | eee | and in that clients copy |
| 23:36 | eee | you remove the entry from the list |
| 23:36 | eee | now, if that client ever bubbles up the dead node |
| 23:37 | eee | that need to be able to tell that it's not in their version of the map |
| 23:37 | eee | s/that/they |
| 23:39 | eee | make sense? |
| 23:42 | rlb | eee: I'm not sure -- do you need handles (again haven't thought about it much)? |
| 23:42 | eee | looks like someone did it in haskell withought, too |
| 23:42 | eee | without |
| 23:43 | eee | they mess with values that match a predicate |
| 23:43 | eee | that's kinda cool |
| 23:43 | eee | wonder if it's O(1) though |
| 23:43 | eee | that's what I was going for |
| 23:43 | eee | decreaseKey() in O(1) |
| 23:48 | eee | i think i found another paper |
| 23:55 | eee | they did something just like I said. auxilliary data structure |
| 23:55 | eee | runtime dominated by that structure and by cleanup of dead nodes |
| 23:55 | eee | I think this may be an open problem in computer science |
| 23:56 | eee | functional decreaseKey in O(1) time |