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 <[email protected]> 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
