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
