Re: converting a R code to fortran

e p chandler wrote:
On Feb 27, 3:40 am, Michel Olagnon <molag...@xxxxxxxxxxxxxxxxx> wrote:

e p chandler wrote:


Here's my idea on solving this problem, which I suspect must be
O(N*N). Ignore the effect of duplicate values in X1 and X2. Compute
the ranks of the original entries in X1 and X2. Given the ranks,
ignore the numerical values. Consider the points in rank space, say on
a chess board with (1,1) at lower left and (N+1,N+1) at upper right.
Put the points (chess pieces) (x1(i),x2(i)) on the board. Starting at
the lower left work to the upper right either by traversing one file
at a time or by considering the boundary of an expanding square.
Compute the count of points to the left and below from those in
adjacent "kitty corner" cells. The only way a count rises is if you go
both up and right from a square which contains a piece.

If you are looking for an O(N*N) algorithm, then you need only to rank
one dimension, this is the algorithm that I gave.


Thank you. You understand the problem domain, which helps to 1) make
sense of the OPs problem and 2) write a good program to solve the
problem.


Indeed, if we rank also in the second dimension, we can make use of your
remark, but it still is O(N*N), the number of comparisons is just divided
by 2.

!
call mrgrnk (x1e, j1e)
call mrgrnk (y2e, j2e)
!
ksh = 0.0
j1 = j1e(1)
j2 = j2e(1)
ksl = -ns*x1e(j1)*y2e(j2)
do m1 = 2, N+1
j1 = j1e(m1)
xd = 0.0
x1j = x1e(j1)
xns1 = ns*x1j
j2 = j2e (1)
do m2 = 2, N+1
j20 = j2
j2 = j2e (m2)
if (x1e(j20)< x1j) then
ksl = min(ksl, xd-xns1*y2e(j20))
xd = xd + 1.0
ksh = max(ksh, xd-xns1*y2e(j2))
endif
enddo
enddo
!
ks= max (ksh, -ksl) / sqrt (ns)

.