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 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
