Before I forget again, I should point out what you might have already
noticed. The expression (#~ Yi={&sorted) works but could be
inefficient on large arrays with mostly equal values.
That said, this expression could also be transformed to use binary
search, since the value named 'sorted' is sorted. (When the list of
indices is large, perform a bin search for the exact value, then on
each side another bin search using the tolerant = test). This pulls
the tolerant equality test out of the loop (when the thi index is a
lot larger than the tlo index).
(You still have to iterate over indices to untangle large clumps of
numbers which are mostly tolerantly equal to each other. But that
doesn't need to burden everything else so much.)
--
Raul
On Wed, Aug 30, 2023 at 12:11 PM Raul Miller <rauldmil...@gmail.com> wrote:
>
> The issue of the cost/benefit function to choose between an O(m*n)
> approach and an O((m+n)*log m) approach is difficult, and probably
> does not have a perfect solution.
>
> Still, designing an approach which has better worse case behavior
> seems relatively straightforward. For example:
>
> minpos=: _2{-:^:a:1
>
> tiota=: {{
> tlo=. %thi=. 1 2 p.9!:18''
> grade=. /: x
> sorted=. grade { x
> result=. y #&# x
> for_i. i.#y do.
> Yi=. i{y
> select. *Yi
> case. _1 do. 'jlo jhi'=. sorted I.Yi*thi,tlo
> case. 0 do. 'jlo jhi'=. sorted I.0,minpos
> case. 1 do. 'jlo jhi'=. sorted I.Yi*tlo,thi
> end.
> j=. {&grade (#~ Yi={&sorted) jlo+i.jhi-jlo
> result=. result i}~ <./(i{result),j
> end.
> }}
>
> assert (i.~ -: tiota~) T=: (,-)1+(0.1*9!:18'')*?100#1000
> assert T (i. -: tiota) T1=: (,-)1+(0.1*9!:18'')*?100#1000
> assert (i.~ -: tiota~) T=: ({~ ?~@#)0 0 0,(,-)1+(0.1*9!:18'')*?100#1000
> assert T (i. -: tiota) T1=: ({~ ?~@#)0 0 0,(,-)1+(0.1*9!:18'')*?100#1000
>
> --
> Raul
>
> On Wed, Aug 30, 2023 at 9:02 AM Henry Rich <henryhr...@gmail.com> wrote:
> >
> > 1. For lists, sort-then-search is more expensive than the hashtable
> > usually. Also, the order of inputs matters, as tolerant-equals is not
> > transitive.
> >
> > 2. For tables, which we were discussing, sort (always intolerant)
> > doesn't get the job done. The entire first column might be tolerantly
> > equal and provide no help toward indexing later columns.
> >
> > It's a hard problem, which has defeated me and Roger before me. Any
> > progress would be much welcomed.
> >
> > Henry Rich
> >
> > On 8/30/2023 7:43 AM, Raul Miller wrote:
> > > Shouldn't tolerant i.~ use grade, sort and a binary search?
> > >
> > > Thanks,
> > >
> >
> > ----------------------------------------------------------------------
> > For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
