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
