Talk:Closest-pair problem: Difference between revisions

Since we only compare distances and the actual smallest distance never needs to be reported, could the calculation be sped up by not using a square root in the distance calculation? I'm not sure how the current examples are calculating the distance, but they may be optimized by calculating the square of the distance (d^2 = (x2-x1)^2+(y2-y1)^2). I don't think there is any use for the actual distance anywhere in the pseudocode, but I may be wrong. --[[User:Mwn3d|Mwn3d]] 19:03, 9 May 2009 (UTC)

:I think the actual distance is meant to be the result of the function. Still, that would let you optimize to reduce the number of square root operations performed. (I do question whether we're doing a “how fast can we go” exercise though; clarity is better here, yes?) — [[User:Dkf|Dkf]] 21:10, 9 May 2009 (UTC)

 

::I believe it would be a reasonable optimization. It would be enough to compute sqrt on the return value (we need a "non recursive front-end" function anyway). But maybe this is up to implementors. Pseudocode should not think about it. --[[User:ShinTakezou|ShinTakezou]] 09:21, 11 May 2009 (UTC)

 

== About this task ==

::I found [http://www.cs.iupui.edu/~xkzou/teaching/CS580/Divide-and-conquer-closestPair.ppt This reference] helped me with my Python example, which seems to work. --[[User:Paddy3118|Paddy3118]] 21:56, 11 May 2009 (UTC)

:::C and Perl and also Smalltalk (updated), based now on the '''new''' pseudocode, '''work''', so I suppose the algorithm now is correct! (What written before referred to the previous pseudocode and first Smalltalk implementation) --[[User:ShinTakezou|ShinTakezou]] 09:09, 12 May 2009 (UTC)

 

==Comment on Algorithms Given==

[http://paddy3118.blogspot.com/2009/05/critique-of-pseudocode-explanations-of_12.html Critique of pseudocode explanations of the Closest Pair Algorithm] --[[User:Paddy3118|Paddy3118]] 05:39, 12 May 2009 (UTC)

: The new code (id est, as it is now) '''works'''. The code that had problems was the previous one (in your blog you report the most recent version, that, as said, works). Maybe I've chosen a not so communicative pseudolanguage... but I thought we were familiar with such notation like "ceil" or "floor", or the meaning of {elements...} (which resembles a set; here we intend an ordered, indexable, "set"); and it seemed to me intuitive that a P(i)_x refers to the point i-th, x coordinate, even though it would be better to write (P(i))_x maybe. I would have used P_i,x but at the end I preferred the P(index) form in general; I could have written P_x(index) instead... maybe it is clearer? Using the last reference, I've corrected the last part of the pseudocode (and in fact the while loop is fundamentally the one you can see there). The syntax I am dissatisfied with is the last I've added to explicitly take care of the points' coordinates, e.g. <code>(closest, closestPair)</code>... but it is the faster modification I was able to think to add that without too many efforts.