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

Reply via email to