[REBOL] Interleaving of strings question Re:(2)
From: joel:neely:fedex at: 25-Sep-2000 8:23
Hi, Grant!
1) A couple of minor tweaks to coord-sort yields (*WARNING*
*UNTESTED CODE FOLLOWS* *TEST BEFORE USING*)
coord-sort: func [a b /local val dim sum] [
dim: length? a
sum: 0
foreach val a [sum: sum + power val dim]
foreach val b [sum: sum - power val dim]
sum > 0
]
2) Your generalization over dimensionality appeals to me as a
mathematician, but as a "software engineer" I am compelled
to point out that if you're dealing with a performance bottle-
neck, the following is faster:
coord-sort-2d: func [a b /local val dim sum] [
dim: length? a
sum: 0
foreach val a [sum: sum + (val * val)]
foreach val b [sum: sum - (val * val)]
sum > 0
]
3) Putting my mathematics hat back on, I am compelled to
point out that if these are really lat/lon coordinates,
then both the taxicab metric (absolute deltas) and squared
Euclidean metric (sum squared deltas) can give wrong answers
to the general case of "which points are nearest to a specific
target point".
Near the poles, lattitude deltas make MUCH more difference
than comparable longitude deltas. For small deltas, a GREAT
improvement in accuracy results from weighting longitude
delta by cos avg lat in the sum. Some additional fiddling
may be required due to the singularites at the poles, but
pole crossings involve large longitude deltas anyway...
4) Putting my s/w eng'ing hat back on, I should add that the
performance of the whole search issue (assuming you might
need to search for a "nearest point" as in the previous
comment) is dominated by the number of points in the entire
search space. If the space is large, with substantial
dispersion of points, consider using the following speedup trick:
The maximum error of the taxicab metric vs. the Euclidean
metric is the square root of two (e.g., the point at (1,1)
has a taxicab metric of 2, instead of the Euclidean metric
of 1.141... -- it's too large by a factor of sqrt 2. Ergo...
Make a prepass across the search space using the taxicab
metric, retaining only those points whose distance from the
target is at most 1.414... times the least distance-
from-target found thusfar. Then make a second pass across
only the set collected in the prepass, using the correct-
but-more-expensive real metric.
Hope some of this is helpful!
-jn-
[grantwparks--yahoo--com] wrote:
