Differences between revisions 10 and 11
 ⇤ ← Revision 10 as of 2008-12-08 10:45:45 → Size: 1972 Editor: anonymous Comment: converted to 1.6 markup ← Revision 11 as of 2013-04-16 16:47:25 → ⇥ Size: 2077 Editor: RogerHui Comment: Deletions are marked like this. Additions are marked like this. Line 79: Line 79: * [[http://www.jsoftware.com/pipermail/programming/2013-April/032329.html|An application, 2013-04-16]]

(~.y)i.y  finds the indices of y in the nub of y . Can you do it faster?

```   timer=: 6!:2

y=: 1e6 ?@\$ 2e9           NB. integers
timer '(~.y)i.y'
1.08679
timer '(~.i.]) i.~ y'
0.437234

y=: 1e6 ?@\$ 0             NB. floating point numbers
timer '(~.y)i.y'
2.62438
timer '(~.i.]) i.~ y'
1.29647

y=: ":&.> 1e6 ?@\$ 1e5     NB. boxed strings
timer '(~.y)i.y'
3.00702
timer '(~.i.]) i.~ y'
1.54582

y=: 1e6 4 ?@\$ 2e9         NB. integer matrix
timer '(~.y)i.y'
1.52394
timer '(~.i.]) i.~ y'
0.50255

y=: 1e6 ?@\$ 100           NB. counterexample, not faster
timer '(~.y)i.y'
0.0264034
timer '(~.i.]) i.~ y'
0.0321949```

## Explanation

~. (nub) is in the same family as the dyad i. and is implemented using the same underlying code. (Others in the family are the monad ~: and the dyads e. -. i: .) The dyad x i. y is not equally fast on all arguments. Listed from faster to slower:

• boolean and literal
• small-range integers, where small means about the size of #x

• general (machine word) integers
• floating point numbers
• etc.

When y is not one of the fast ones, (~.y)i.y requires two slow operations, one for ~.y and another for the i. , because ~.y and y have the same classification. In contrast, (~.i.])i.~y (same as (~.t)i.t=.i.~y ) uses one slow operation to do i.~y , producing a list of small-range integers, whence (~.i.]) is computed using two fast operations.

i.~y , even when "slow", is supported by special code, as the following benchmark demonstrates:

```   y=: 1e6 ?@\$ 2e9
y0=: y+0

timer 'i.~ y'
0.357208
timer 'y i. y'
0.355987
timer 'y i. y0'
0.624246```

Contributed by RogerHui.

Essays/Index in Nub (last edited 2013-04-16 16:47:25 by RogerHui)