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
