tag:blogger.com,1999:blog-786333285568106173.post6206324333305787070..comments2024-01-25T01:05:59.968-05:00Comments on WebDiarios de Motocicleta: Prefix-Free CodesMihaihttp://www.blogger.com/profile/11599372864611039927noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-786333285568106173.post-8974439380284150542010-06-04T09:55:40.111-04:002010-06-04T09:55:40.111-04:00Mihai: Doubling Search is optimal in the number of...Mihai: Doubling Search is optimal in the number of comparisons, but its access pattern is very cache unfriendly (you end up comparing one element in each block on long runs). The obvious theoretical answer is to replace it with some finger search in a B-Tree, but somehow, nobody I know does this in practice.<br /><br />When I tried to optimize (experimentally) the running time (as opposed to the number of comparisons performed) of doubling search (in the context of intersection algorithms for sorted arrays), some cache-oblivious techniques did yield some improvements, but only for some of the biggest (intersection) instances. Had I considered cache-aware improvements, I think I would have used some blocking looking a bit like your larger alphabet.dothttps://www.blogger.com/profile/14825435867493579983noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-66639441585788458782010-06-03T21:28:07.386-04:002010-06-03T21:28:07.386-04:00Jeremy: I didn't think about this. What would ...Jeremy: I didn't think about this. What would you hope to achieve? Doubling search is optimal, at least within constant factors...Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-995630811485244122010-06-03T09:00:22.719-04:002010-06-03T09:00:22.719-04:00Elias codes correspond to algorithms for the unbou...Elias codes correspond to algorithms for the unbounded search problem, your code 2 corresponding to doubling search [Bentley and Yao, 1976], and any adaptive search algorithm yields a (compressed) prefix free code. Did you ponder what search algorithm corresponds to this new code, and what the cryptographic property of the code corresponds to for the search problem? <br /><br />Thinking about it quickly, the search algorithm looks like a cache-friendly version of doubling search, in a cache-aware model, but I did not dig more into it, since you probably already explored this avenue?<br /><br />Pa!<br /><br />Jeremydothttps://www.blogger.com/profile/14825435867493579983noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-29769713048981960562010-06-02T19:16:45.360-04:002010-06-02T19:16:45.360-04:00Rasmus, I like your idea of doing B and B+2 using ...Rasmus, I like your idea of doing B and B+2 using no consecutive EOFs, but it will only work for the first double block. For the second, we will need (B-2)(B+4) = B^2 + 2B - 8 >= (B+1)^2 - 1 = B^2 - 2B, which is false.<br /><br />Ironically, replacing 3 by 4 is actually better :).<br /><br />Yevgeniyzaumkahttps://www.blogger.com/profile/04810392740674199906noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-43193046377138623482010-06-02T18:33:30.106-04:002010-06-02T18:33:30.106-04:00This is very neat. I believe that if you exploit t...This is very neat. I believe that if you exploit that there can be no two eofs in a row, you can replace the constant 3 by 2, and lose nothing in the splitting step.<br /><br />Blog request: At some point you gave a talk about a combinatorial view of FFT. Any chance you could blog about that?Rasmus Paghhttps://www.blogger.com/profile/05722627403861422993noreply@blogger.com