On Tue, Jan 17, 2012 at 1:41 PM, John Gilmore <[email protected]> wrote: > Rob, > > My point was the truism that if pointer chasing is cheap and > comparisons are not cheap then pointer chasing is advantageous. > > Let n be the number of elements in a list and m = 1 + n /2 be the > serial number of a middling element. Then chasing pointers (without > making comparisons) to find the m-th list element and making the > search-argument-to-key comparison there permits one to then proceed in > an obvious way as in traditional binary search.
Ok, I see... Imagine we have an efficient operation that can run M pointers. You'd run to N/2, do your compare and use the result to optionally reset to the start again, and then run for N/4. That would give us (N-1) * cost(P) + log(N) * cost(C) rather than (N/2) * ( cost(C) + cost(P) ) with cost(C) and cost(P) the cost for key comparison and following a pointer respectively. Really depends on the ratio between those two. Interesting... > The list is treated as a species of array with pointer chasing > replacing addressing arithmetic. Some APL implementations do things > like this in managing their arrays, which are really lists. > > The trick here (as elsewhere) is to work with pointers to pointers, so > that one always has access to both the location and value of a > chaining pointer. > > John Gilmore, Ashland, MA 01721 - USA
