[Jprogramming] Squared Euclidean distance matrix calculation

[Henry Rich]

(+/"1)@:*:@:(-"1)

Henry Rich

On 2/20/2021 2:40 PM, Emir U wrote:
> Regarding the efficient computation of a squared Euclidean distance matrix. There wasn't very much on the topic so far as I could find. In previous discussion this formulation was suggested:
>
> +/ @: *:@:-"1
>
> You might use it like this to find the distance between the row vector x and the row vectors in y:
>
> (1 2) ed/ (3 4,. 5 6)
>
> It is very elegant, but it is in effect a Cartesian join and even for moderately sized distance matrices ends up being inefficient since all computation is performed at a cell level.
>
> In my code, I replaced it with this:
>
> ed=: 4 : 0
>
> row=. 4 : '+/ *: (x - (|: y))'
>
>> (row & y) each < "1 x
> )
>
> Used like this:
>
> (1 2) ed (3 4,. 5 6)
>
> It lacks the elegance, but it is general (although size of x should be <= y) and several orders of magnitude faster than the tabled solution because it operates on a row at a time so presumably benefits from SIMD and the like.
>
> Emir
>
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm


-- 
This email has been checked for viruses by AVG.
https://www.avg.com