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
