On Thu, 18 Jul 2013 15:09:22 -0400, John Gilmore wrote: >Paul Gilmartin wrote: > ><begin extract> >Which might be the proper implementation if the cases are sparse. >Best to start with the median case value and bisect recursively. >Storage is cheap nowadays, particularly if it's not accessed. But a >large and sparse branch table is an invitation to page faults. ></end extract> > >I must admit that I am not quite sure what this means. The obvious >interpretation is precluded. Compilers--unlike, say, RDBMs--are not >ordinarily provided with frequency statistics for case values. If >instead it means that a BST can be used to replace a polynomial-time >linear-search scheme with an exponential-time binary-search one, I >agree. > >Where it can be used, a branch table is nevertheless a very much >better alternative. > By "sparse" I was suggesting a hundred distinct entries among a million "otherwise" values. At some low density, the nested "if" becomes preferable. (The nested "if" can be considered a compiled version of the BST/)
I'm glad I said "median", rather than "mode". For the latter frequency statistics would be required. And in Shmuel mode, I would have said "logarithmic" rather than "exponential". -- gil ---------------------------------------------------------------------- For IBM-MAIN subscribe / signoff / archive access instructions, send email to lists...@listserv.ua.edu with the message: INFO IBM-MAIN
