Anonymous user
Talk:Closest-pair problem: Difference between revisions
→Comment on Algorithms Given: it can't be there the problem: yP/xP values are ok to index P
No edit summary |
(→Comment on Algorithms Given: it can't be there the problem: yP/xP values are ok to index P) |
||
Line 39:
yP[i] returns 7099, when N is 5000.
: Hm interesting... I'll take a look when I'll have more time. In my tests it did not crash, but it does not mean necessarily that it does not write outside the heap... I must do some deeper check. --[[User:ShinTakezou|ShinTakezou]] 10:16, 13 October 2009 (UTC)
: I've overbloated the code with extra assertions in indexes and everything seemed to go fine. About the part you show, N is just the number of element in yP and xP, so the constrain < N (5000) is for <tt>i</tt>, not for yP[i] or xP[i]; these two are indexes on P, which can go from 0 to 10000-1 in your example so the results 6041 and 7099 are ok. I can't reproduce the error, and assertions I've added seem to say it's ok, but of course I will continue to test it; maybe there are some problem related to the random distribution; you can send me the random numbers your computer generated (archived with zip or gzip please); or try this change to the code:
xm = (P[xP[midx]].x + P[xP[midx+1]].x) / 2.0;
if ( P[yP[i]].x < xm ) {
: If the problem disappears, it was the problem... Sincerely I can't see why it should be, maybe the latter is better from certain point of view, but to me it should behave the same... (Indeed, I've not checked even "mathematically" if it is true, but I will do... for now, just intuition at work!) --[[User:ShinTakezou|ShinTakezou]] 20:20, 18 October 2009 (UTC)
| |||