You can use ": as part of the hashing function and yes you do have to hash x*1-t and x%1-t .
On Mon, Jan 16, 2012 at 11:19 AM, Raul Miller <rauldmil...@gmail.com> wrote: > If hashing would work, then keying on ": would work. I expect though > that I would need to hash at least twice (adding epsilon before the > second hash) and I expect that I would need to do something similar if > I used ": > > -- > Raul > > On Mon, Jan 16, 2012 at 2:14 PM, Roger Hui <rogerhui.can...@gmail.com> > wrote: > > Hashing has expected O(n) time. > > > > > > > > On Mon, Jan 16, 2012 at 11:11 AM, Raul Miller <rauldmil...@gmail.com> > wrote: > > > >> I think that the "monster case" would be a case where all values are > >> similar enough that they all map to the same index but different > >> enough that they cannot be recognized as literal equivalents. > >> > >> In the case I am currently interested in, the original values would be > >> 32 bit floating point numbers and only a relatively few bits of the > >> available precision would allow values to be treated as "tolerantly > >> equal". This would suggest that the size of the "monster case" is > >> limited based on the number of bits being ignored. > >> > >> So, in principle at least, this should limit the size of the > >> "quadratic part" of the problem, for the cases I am trying to address. > >> > >> -- > >> Raul > >> > >> On Mon, Jan 16, 2012 at 12:04 PM, Roger Hui <rogerhui.can...@gmail.com> > >> wrote: > >> > The paper I cited, *Hashing for Tolerant > >> > Index-Of<http://www.jsoftware.com/papers/Hashing.htm> > >> > * , presents a "monster" that defeats a sorting algorithm. (Defeat > in > >> the > >> > sense of causing it take quadratic time.) > >> > > >> > > >> > > >> > On Mon, Jan 16, 2012 at 8:07 AM, Henry Rich <henryhr...@nc.rr.com> > >> wrote: > >> > > >> >> You can sort the lists and then compare adjacent values; find > >> >> superfluous ones; then i.!.0 to find them in the original list. > >> >> > >> >> A tricky part is that proximity is not a transitive property. If the > >> >> tolerance is 2, and the data is > >> >> > >> >> 1 2 3 4 5 6 7 > >> >> > >> >> what should the result of the i.~ be? > >> >> > >> >> Henry Rich > >> >> > >> >> On 1/16/2012 10:06 AM, Raul Miller wrote: > >> >> > First: I like Roger Hui's response. And, in essence, it's doing > >> >> > exactly what you suggest. However, this requires comparing every > >> >> > number in the left list with every number in the right list. I am > >> >> > currently pondering algorithms which rely on I. so that when the > lists > >> >> > are long computation times are still reasonable (perhaps with > 100000 > >> >> > members in each list). > >> >> > > >> >> > Second: I would want the three PI values in my original message > to be > >> >> > treated as equal. I want to be able to specify a magnitude of > >> >> > acceptable difference which is greater than any of the differences > in > >> >> > that data sample. > >> >> > > >> >> > FYI, > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
