Mailing List Archive: 49091 messages
  • Home
  • Script library
  • AltME Archive
  • Mailing list
  • Articles Index
  • Site search

[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: