Pascal Jasmin's findxth benefits greatly from this tweak:
findxtha =: 4 : 0
'x m' =. xm x NB. m is sorted list of find indexes. x is match value.
if. 0 = #m do. m =. 0 end.
acc =. i.0
oset =. 0
for_i. i. >./ m do.
idx =. x i.~ oset }. y NB. WAS idx =. x i.~ y
if. idx = oset -~ # y do. acc return. end.
if. i e. m do. acc =. acc , oset + idx end.
oset =. oset + >: idx
NB. y =. (>: idx) }. y NB. Better NOT to do this!
end.
acc , oset + x i.~ oset }. y
)
(100; 0 2) (findxth -: findxtha) A
1
100 find2 A NB. (One of) Raul's original suggestions
1599
(100; 0 1 2) ( findxtha) A
990 1599 2797
NB. These comparisons partly reproduce/endorse Devon's findings
NB. but also look at findxth and a couple of variants...
ts =:6!:2 , 7!:2@]
ts'100 (1{I.@E.) A NB. Fails if there’s no (second) 100 in A' NB.
My early offering!
0.512366 8.39904e6
ts'100 find2 A' NB. (One of) Raul's original suggestions
4.1e_6 1280
ts'(100;0 1 2) findxth A'
0.708966 2.14749e9
ts'(100;0 1 2) findxtha A'
2.46e_5 2304
ts'0 1 2 findxthdg 100; A' NB. Don's proposal (renamed here)
0.232047 1.35533e8
(All these in J904 under Windows 11 on this laptop.)
Not surprisingly, (100; 99494) findxth A is really slow - I interrupted
it!
So it looks as if Raul's best to stick to one of his original methods,
especially since he points out that the Pritchard sieve only requires
an index of the second instance.
Cheers,
Mike
On 30/08/2022 15:04, Don Guinn wrote:
Oops! should have been
timespacex '100 findxth 1;A'
0.0925588 1.35533e8
On Tue, Aug 30, 2022 at 8:02 AM Don Guinn<[email protected]> wrote:
NB. Find the index of some instance of a value
findxth=:4 : 0
'value list'=.y
try. x{,4$.$.value=list
catch. _1
end.
)
_20,\z=:?.100#10
4 6 8 6 5 8 6 6 6 9 3 2 3 1 9 2 7 0 9 5
7 7 9 7 4 8 7 4 2 1 1 0 4 3 9 3 2 7 4 4
0 3 7 5 9 6 3 2 8 2 0 3 5 4 0 0 3 1 5 0
4 0 2 9 2 4 0 0 7 7 5 7 3 1 6 3 1 5 8 9
8 5 3 9 9 8 9 5 1 1 0 4 1 7 3 2 3 4 0 4
NB. Find index of the second occurence of 2
1 findxth 2;z
15
NB. Find index of the third from last of 7
_3 findxth 7;z
69
NB. Try to find index of the tenth of 5 but does not exist
9 findxth 5;z
_1
NB. find the index of the middle or next to middle 8
({~<.@-:@#),4$.$.8=z
48
A=. ?. 1e8#1e3
100 (2 i.~ +/\)@:E. A
1599
timespacex '100 (2 i.~ +/\)@:E. A'
0.213069 1.20796e9
timespacex '100 findxth 2;A'
0.0890775 1.35533e8
On Mon, Aug 29, 2022 at 6:32 PM 'Pascal Jasmin' via General <
[email protected]> wrote:
I thought that perhaps this could be fast:
A=. ?. 1e8#1e3
timespacex '100 (2 i.~ +/\)@:E. A' NB. or = instead of E.
0.460527 1.20796e9
This application happens to everyone at least once, if
(u { I.@E.)
had special code where the result of u (or simply m) is presumed (for
speed optimization) to be a list/atom of top (rather than last) occurrences
of matches.
Here is a dyad that returns the xth occurrences (indexes) of x in y if
they exist. where x is in format x (, or ;) m where m is the list of
indexes requested.
It is a bit slow due to the y =. n }. y step.
xm =: {. ,&boxopen }. NB. split arguments as head ; tail. assignment as
'h t' =. xm y
findxth =: 4 : 0
'x m' =. xm x NB. m is sorted list of find indexes. x is match value.
if. 0 = #m do. m =. 0 end.
acc =. i.0
oset =. 0
for_i. i. >./ m do.
idx =. x i.~ y
if. idx = # y do. acc return. end.
if. i e. m do. acc =. acc , oset + idx end.
oset =. oset + >: idx
y =. (>: idx) }. y
end.
acc , oset + x i.~ y
)
1 1 3 4 6 findxth 0 1 0 0 1 0 1 1 1
4 7 8
(1 ; 1 3 4 6) findxth 0 1 0 0 1 0 1 1 1
4 7 8
1 findxth 0 1 0 0 1 0 1 1 1
1 NB. m is 0 (first item) if omitted.
5 {. 100 I.@E. A
990 1599 2797 4550 5073
100 0 1 4 findxth A
990 1599 5073
On Friday, August 26, 2022 at 05:27:46 p.m. EDT, Devon McCormick <
[email protected]> wrote:
I get these timings on J 9.04:
A=. ?1e8#1e3
ts '100 find2 A'
2.4e_6 1536
ts '100 (1{I.@E.) A'
0.19722 8.39853e6
ts '100 ({.@}.@(I.@E.)) A'
0.200139 8.39866e6
(100 find2 A) -: 100 (1{I.@E.) A
1
find2
([: >: i.~) + [ i.~ ] }.~ [: >: i.~
On Fri, Aug 26, 2022 at 3:53 PM 'Mike Day' via General <
[email protected]> wrote:
Does that include drop, }. ? I suppose it can, since we only need to
move the pointer to the start... I’ll check on the laptop, once I’ve
done
my Listener xwd.
(Last week’s was the quarterly numeric puzzle, an ingenious
construction
including among all the digits a few decimal points and solidus ( / )
for
rationals!)
Cheers,
Mike
Sent from my iPad
On 26 Aug 2022, at 20:36, Raul Miller<[email protected]> wrote:
Updating arrays without generating a new copy was introduce in J805 --
https://code.jsoftware.com/wiki/System/ReleaseNotes/J805
So in J701, that approach would indeed be slower (since it's creating
a complete copy of the array).
Also, virtual blocks (which speed up the }. approach) were introduced
in J807. I guess I need to roll up my sleeves and do some
benchmarking...
Thanks,
--
Raul
On Fri, Aug 26, 2022 at 3:20 PM 'Mike Day' via General
<[email protected]> wrote:
These seem simpler and are possibly quicker, at least in J701 on
this
oldish iPad:
100 (1{I.@E.) A NB. Fails if there’s no (second) 100 in A
719
100 ({.@}.@(I.@E.)) A NB. Returns 0 in that case
719
Easy to correct for such errors, of course.
I tried
A =. ?1000000#1000
find2 =: 13 : 'F + ((F=.>:y i. x) }. y) i. x' NB. No direct defs in
J701
ts'100 find2 A'
0.020555 8.39091e6
ts'100 (1{I.@E.) A'
0.011503 76160
ts'100 ({.@}.@(I.@E.)) A'
0.007626 84864
Speed a bit better, space quite a lot, if happy with time & space
tests.
Only you know if it’s wise to overwrite the first occurrence of V in
A!
Cheers,
Mike
Sent from my iPad
On 26 Aug 2022, at 19:36, Raul Miller<[email protected]>
wrote:
i. returns the index of the first occurrence of a value within an
array.
So, when implementing an algorithm which needs the index of the
second
occurrence of the value within a (large) array, we need to do some
additional work.
let's say that our array is A, the value is V
F=: A i. V NB. the index of the first occurrence of V
What's the most efficient way of finding the second occurrence?
One possibility is
S=: (1+F) + ((1+F) }. A) i. V
Another possibility, assuming that V is numeric and not zero, would
be
S=: (0 F} A) i. V
But A is large, so perhaps a faster approach would be:
S=: {{ while. V~:y{A do. y=. y+1 end. y }} F
(Which has me wishing that S=: A i.!.F V would do the job, though
I'm
not sure that that's completely appropriate...)
But, we can probably eliminate the need to generate a copy of A
with a
little extra work:
A=: 0 F} A
S=: A i. V
A=: V F} A
It seems to me that this is probably going to be the fastest
approach.
Can anyone think of a faster approach (or something with comparable
speed which isn't quite so unwieldy?)
Thanks,
--
Raul
----------------------------------------------------------------------
For information about J forums see
http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see
http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see
http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums seehttp://www.jsoftware.com/forums.htm
--
Devon McCormick, CFA
Quantitative Consultant
----------------------------------------------------------------------
For information about J forums seehttp://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums seehttp://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums seehttp://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
