No I did not try the binary search. It is worthwhile to try it. I'll do. It should be possible to do so by a macro that first sorts the clauses and then builds the binary if tree without having to wrap the bodies in procedures. Jos
-----Original Message----- From: Matthew Flatt [mailto:[email protected]] Sent: jueves, 29 de septiembre de 2011 15:08 To: Jos Koot Cc: 'Racket-users' Subject: RE: [racket] case form implemented with a hash I don't see Clinger's technique as useful only for a small number of clauses. Although I'm not sure that 86 clauses is enough to tell the difference, just to double-check: did you try a binary search instead of a hash table? That is, instead of (if (= x 0) e0 (if (= x 1) e1 (if (= x 2) e2 e3))) using (if (x . < . 2) (if (x . < . 1) e0 e1) (if (x . < . 3) e2 e3)) ? At Thu, 29 Sep 2011 12:25:16 +0200, "Jos Koot" wrote: > Thanks Matthew. > I read the paper. > In my case I have a case form which dispatches on a character, 86 different > ones. Therefore I can dispatch by means of a vector. However, almost every > character has its own clause and therefore dispatching on the index of the > character would give no speed up. I already tried a hash-table and a vector > (making sure it is computed once only) The values in the table/vector are > procedures that run the body of a clause. The vector is used as follows: > > (define (parse-fmt-instr parser-state) ; Parses one single instruction. > (skip-white-fmt-and-commas parser-state) > (let ((char (pop-fmt-char parser-state #f))) > (and char > (if (char=? char #\λ) call-proc-instr > (let ((i (char->integer char))) > (if (< i 128) > ((vector-ref parser-table i) parser-state char) > (fmt-error parser-state))))))) > > However, as you predicted, I found no speed up. With a hash table in some > cases even a slow down. > The gain in speed of dispatching seems to be destroyed by the extra > procedure call. > I think Clinger's paper is particularly useful for case forms wih many keys > but few clauses. > Thanks for your help. > Jos > > -----Original Message----- > From: Matthew Flatt [mailto:[email protected]] > Sent: miércoles, 28 de septiembre de 2011 22:59 > To: Jos Koot > Cc: 'Racket-users' > Subject: RE: [racket] case form implemented with a hash > > I had in mind the comment on page 64, bottom right, but I see that it's > a smaller comment than in my memory. > > Overall, I think it will work better to use a hash table to go from a > value to an index, and then use a binary search on the index as in > Clinger's paper. Indirect dispatch via thunks in a hash table will most > likely be slower. > > At Wed, 28 Sep 2011 22:55:08 +0200, "Jos Koot" wrote: > > Hi Hatthew, > > I am still trying to implement 'case' by means of a hash. > > Can you give me a more specific pointer. I followed your pointer but did > not > > see anything relevant to my question. > > Jos > > > > -----Original Message----- > > From: Matthew Flatt [mailto:[email protected]] > > Sent: miércoles, 28 de septiembre de 2011 22:20 > > To: Jos Koot > > Cc: 'Racket-users' > > Subject: Re: [racket] case form implemented with a hash > > > > At Wed, 28 Sep 2011 22:08:44 +0200, "Jos Koot" wrote: > > > By inspection with the macro stepper I found that case forms are > expanded > > to > > > nested if-forms. For case forms with many clauses, this may be > > inefficient. > > > I have tried to prepare a hash-case form using a hash table in order to > > > select the desired clause more efficiently. So far my attempts failed. I > > am > > > still trying. However, has anybody else on this list thought of using a > > hash > > > for case forms with many clauses? Does it exist? If not, would anyone be > > > interested in a hash-case form that has the same shape as a case-form, > but > > > uses a hash-table to select the appropriate clause? The hash table > should > > be > > > a map onto thunks and macro hash-case simply would have to retrieve the > > > thunk and call it. > > > > See "Rapid Case Dispatch in Scheme", Clinger, Scheme'06. > > > > If you implement a revised `case' that consistently works better, then > > I'd be happy to use it as a replacement for the current `case'.
_________________________________________________ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/users
