I'm running it on input size of 100 points. amd platform might make a difference.
----- Original Message ----- From: Jose Mario Quintana <[email protected]> To: Programming forum <[email protected]> Cc: Sent: Thursday, September 17, 2015 1:01 PM Subject: Re: [Jprogramming] An adverb for a loopy algorithm Are you running your timings comparison many times to make sure? I do (666 times). Alternatively, are the relative timings affected significantly by the platform? JVERSION Installer: j602a_win.exe Engine: j803/2014-10-19-11:11:11 Library: 6.02.023 666 st&> 'closest P' ; 'close2 P' ; 'nnf P' ┌─────────┬─────┬──────────┬────────┐ │closest P│23296│2.87491e_5│0.669738│ ├─────────┼─────┼──────────┼────────┤ │close2 P │15104│4.55035e_5│0.687284│ ├─────────┼─────┼──────────┼────────┤ │nnf P │10240│7.21532e_5│0.738849│ └─────────┴─────┴──────────┴────────┘ closest #~ +/@(= <./@:(0 -.~ ,))@:|@:(-/~)@:(1 0j1 +/ .*~ ]) close2 #~ +/@(= ([: <./ 0 -.~ ,))@:([: | -/~)@:(j./"1) nnf {~ ((0 1 + ] , i.) (#~ (<: i.@:#)))@:([: ; (i.L:0 <./@:;))@:([: }. <@:|@:({: - }:)\&:(j./"1)) On Thu, Sep 17, 2015 at 11:40 AM, 'Pascal Jasmin' via Programming < [email protected]> wrote: > A variation on your version with the same speed (actually slightly slower > at 5th decimal) but smaller space > > close2 =: (#~ +/@(= [: <./ 0-.~,)@:([: | -/~)@:(j./"1)) > > > > > > ----- Original Message ----- > From: Jose Mario Quintana <[email protected]> > To: Programming forum <[email protected]> > Cc: > Sent: Thursday, September 17, 2015 10:23 AM > Subject: Re: [Jprogramming] An adverb for a loopy algorithm > > Let us compare the two siblings, closest and nearest_neighbors together > with its fixed version: > > nnf=. nearest_neighbors f. NB. Fixed version > > closest > ] #~ +/@(= <./@:(0 -.~ ,))@:|@:(-/~)@:(1 0j1 +/ .*~ ]) > nnf > {~ ((0 1 + ] , i.) (#~ (<: i.@:#)))@:([: ; (i.L:0 <./@:;))@:([: }. > <@:|@:({: - }:)\&:(j./"1)) > > 666 st&> 'closest P' ; 'nearest_neighbors P' ; 'nnf P' > ┌───────────────────┬─────┬─────────────┬───────────┐ > │closest P │23296│3.27532288e_5│0.763019217│ > ├───────────────────┼─────┼─────────────┼───────────┤ > │nearest_neighbors P│10624│7.30659274e_5│0.776252412│ > ├───────────────────┼─────┼─────────────┼───────────┤ > │nnf P │10240│7.20269787e_5│0.737556262│ > └───────────────────┴─────┴─────────────┴───────────┘ > > The nearest_neighbors verbs are leaner but closest runs twice as fast on my > PC. > > They seem to produce the same results as long as there are no ties and > no repetitions; otherwise there are issues: > > Q=. 0 ". every cutLF 0 : 0 NB. Tie > _1 _1 > 0 1 > 1 0 > 1 1 > ) > > R=. 0 ". every cutLF 0 : 0 NB. Repetition > _1 _1 > _1 _1 > 0 0 > ) > > (closest ; nearest_neighbors ; nnf) P > ┌───────────────┬───────────────┬───────────────┐ > │6.42201 5.83321│6.42201 5.83321│6.42201 5.83321│ > │6.62593 6.08499│6.62593 6.08499│6.62593 6.08499│ > └───────────────┴───────────────┴───────────────┘ > (closest ; nearest_neighbors ; nnf) Q > ┌───┬───┬───┐ > │0 1│0 1│0 1│ > │1 0│0 1│0 1│ > │1 1│ │ │ > │1 1│ │ │ > └───┴───┴───┘ > (closest ; nearest_neighbors ; nnf) R > ┌─────┬─────┬─────┐ > │_1 _1│_1 _1│_1 _1│ > │_1 _1│_1 _1│_1 _1│ > │ 0 0│ │ │ > │ 0 0│ │ │ > └─────┴─────┴─────┘ > > > On Thu, Sep 17, 2015 at 1:38 AM, David Lambert <[email protected]> > wrote: > > > If your task is actually 2D, consider complex numbers. This version > > performs better on the sample data P=:p > > > > nearest_neighbors =: {~ convert_to_index@:identify_minimum@:separation > > > > separation =: [: }. <@:|@:({: - }:)\&:(j./"1) > > identify_minimum =: [: ; (i.L:0 <./@:;) > > convert_to_index=:(0 1 + ] , i.) (#~ (<: i.@:#)) > > > > NB. examples by part > > boxdraw_j_ 1 > > > > separation 4{.P > > +-------+---------------+-----------------------+ > > |3.71611|6.01287 6.83522|1.30641 4.14391 7.31405| > > +-------+---------------+-----------------------+ > > > > identify_minimum separation 4{.P > > 1 2 0 > > convert_to_index identify_minimum separation 4{.P > > 0 3 > > nearest_neighbors 4{.P > > 6.42201 5.83321 > > 6.00479 7.07121 > > nearest_neighbors P > > 6.42201 5.83321 > > 6.62593 6.08499 > > > > > > NB. time & space > > close=: 3 :'y #~ +/@(= [: <./ 0-.~,)+/"1 *: -"1/~y' NB. RDM > > flose=:nearest_neighbors f. > > 999 timespacex"0 1 'close P',:'flose P' > > 9.15946e_5 39680 > > 5.26036e_5 10240 > > > > Date: Wed, 16 Sep 2015 19:49:56 +0000 (UTC) > >> From: "'Pascal Jasmin' via Programming"<[email protected]> > >> To: Programming Forum<[email protected]> > >> Subject: [Jprogramming] An adverb for a loopy algorithm > >> Message-ID: > >> <[email protected]> > >> Content-Type: text/plain; charset=UTF-8 > >> > >> finding the 2 closest points in a set, has a loopy algorithm of "for > each > >> point, compare it with all of the points to its right" > >> > >> p =: 0 ". every cutLF 0 : 0 > >> 6.42201 5.83321 > >> 3.15448 4.06327 > >> 8.89456 0.352235 > >> 6.00479 7.07121 > >> 8.10462 9.19487 > >> 9.63448 4.00534 > >> 6.74378 0.791349 > >> 5.56034 9.27039 > >> 4.67282 8.45993 > >> 0.301042 9.4069 > >> 6.62593 6.08499 > >> 9.0307 2.37372 > >> 9.36324 1.80147 > >> 2.67396 1.62207 > >> 4.76667 1.94554 > >> 7.43839 6.05369 > >> ) > >> > > > > ---------------------------------------------------------------------- > > 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 see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
