Mailing List Archive: 49091 messages

# Interleaving of strings question

### [1/7] from: grantwparks:ya:hoo at: 25-Sep-2000 4:04

I was thinking about the earlier postings about sorting coordinates by interleaving digits of the 2 axis values. The interleaving, it would seem, is to make the longitude as significant as the latitude, in terms of distance from other points. Ignoring the need to have the lat/long pairs stored that way for later processing, and ignoring stated expected values for the coordinates I thought: 1. Wouldn't it be more precise to interleave each digit? 2. In terms of a regular x,y system, even that would be incorrect sometimes. E.G.: [ 0,0 1,5 2,2 5,1 ] (a sorted set of simplified coordinates) isn't correct. 2,2 is closer to 0,0; 1,5 and 5,1 are the same distance from 0,0. 3. Could pairs or tuples be used? Answer: pairs didn't sort that way and I have no reason to assume sort would think of tuples as coordinates. 4. Wouldn't it be the least convoluted to have a /compare function for sort that understood that all components of the coordinate were equally significant? That way there's no manipulating the coordinates, and it should be the most precise. Would a Pythagorean type thing work, because it looks like simply summing the absolute differences between each coordinate component isn't right: 1,1 to 1,5 = 4 ((1-1)+(5-1)) 1,1 to 2,4 = 4 ((2-1)+(4-1)) yet 2,4 is closer to 1,1 than is 1,5. Until the real distance is needed, I don't think you'd have to take the square root of the sum (and how do you do that for 3-dimensions, does it become cubed and cube root - aha) (ABS(x1-x2) to the nth) + (ABS(y1-y2) to the nth) ... + (ABS(n1-n2) to the nth) Comments? Is this right?

### [2/7] from: grantwparks:y:ahoo at: 25-Sep-2000 5:33

Since we want them sorted, we're talking about their relative distance from an origin ( 0,0,... ). So it became (x1 to the nth + y1 to the nth) < (x2 to the nth + y2 to the nth)... If one of you great REBOLs would show how to do this using all the niceties of series! traversal I would appreciate it; I know my version is a pretty sad procedural version: coord-sort: func [ a b /local sum1 sum2 ] [ sum1: 0 sum2: 0 dimension: length? a while [ not tail? a ] [ sum1: add sum1 power first a dimension a: next a ] while [ not tail? b ] [ sum2: add sum2 power first b dimension b: next b ] sum1 < sum2 ] --- [grantwparks--yahoo--com] wrote:

### [3/7] 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:

### [4/7] from: grantwparks::yahoo::com at: 25-Sep-2000 6:42

Yow! I guess it's a lot safer to play in the theoretical space ;) I was wondering tho' if you imagine a 3-dimensional space, does changing the power to 3 from 2 work for Pythagoras? I recently talked to some GIS guys who pointed out the inherent errors in GPS because the tectonic plates move up to 51 cm / year, or something. They got a big kick out of that, but somehow I missed the punchline. I did think, though, that this was a definitively more accurate method than the original discussion (don't know if you saw it) that was going to interleave the long digits into the latitude... --- [joel--neely--fedex--com] wrote:

### [5/7] from: joel:neely:fedex at: 25-Sep-2000 10:18

[grantwparks--yahoo--com] wrote:
> Yow! I guess it's a lot safer to play in the > theoretical space ;) I was wondering tho' if you > imagine a 3-dimensional space, does changing the power > to 3 from 2 work for Pythagoras? >
Yes, if your 3-space is Euclidean.
> I recently talked to some GIS guys who pointed out the > inherent errors in GPS because the tectonic plates > move up to 51 cm / year, or something. They got a big > kick out of that, but somehow I missed the punchline. >
ROTFL! You should respond, "Yeah, but they more than compensated for that when they turned of SA!"
> I did think, though, that this was a definitively more > accurate method than the original discussion (don't > know if you saw it) that was going to interleave the > long digits into the latitude... >
Well, I saw it, but didn't understand what problem was being solved (and still don't). Is the task is to: 1) take a given target location and return the point in the database that is geographically nearest; 2) take a given target location and return a list of all points from the database that are "near enough"; 3) sort a collection of points and present a human- readable display based on nearest-to-farthest; or 4) something else? In addition, I'm unclear as to whether: 1) the target is an arbitrary point or is constrained to be one of the points in the database; 2) how many points are in the database; 3) what resolution is required; and 4) the dispersion of the points in the database: 4a) how wide an area is covered, and 4b) how "clumpy" the distribution is. All of these would influence my choice of strategy. For example, if the task is (1) or (2), and the points are fairly uniformly distributed over a large range of lat/lon values, I'd consider a two-level strategy of partitioning the data into coarse-grained lat/lon cells (one-time, front-end work), then searching only the cell that should contain the target point (or nearby cells as needed for near enough or "empty cell" constraints). For example -- assuming two-degree cells for the sake of illustration -- to locate the point 37.4968N x 89.9935W, look first in the cell containing 36-37N x 88-89W. As needed, expand the search into the neighboring cells: ...... ...... ...... ...... ...... ...... ...... ...... ...... ...... ...... 38-39N 36-37N 34-35N ...... ...... 90-91W 90-91W 90-91W ...... ...... 38-39N 36-37N 34-35N ...... ...... 88-89W 88-89W 88-89W ...... ...... 38-39N 36-37N 34-35N ...... ...... 86-87W 86-87W 86-87W ...... ...... ...... ...... ...... ...... ...... ...... ...... ...... ...... This strategy lets you "zoom in" quickly to the area of relevance, then do the more complex calculations only for a small subset of the space. Another strategy would be to pre-compute the true distance-from-origin for each point (storing that value with each point), then use that as a figure of merit for limiting the search space. Points near the target will obviously have a similar distance-from-origin to the target's value. Of course, the converse is not true (90Nx0W is the same distance from 0Nx0W as 0Wx90N), but the point of this trick is just to reduce the nunber of points that must be individually evaluated. Working with real data on real computers with real memory and performance limits can DEFINITELY get hairy! Have fun! -jn-

### [6/7] from: lmecir:geocities at: 26-Sep-2000 0:21

Hi, although your question has a little in common with Rebol, my answers are as follows: 1. It would be more precise to interleave each bit - ie. each binary digit - as the smallest unit of information 2. in that case the bit - sort yields: [0,0 2,2 1,5 5,1] 3. as you pointed out, the result of the sort doesn't depend on the representation, but on the comparison function, any suitable representation can do 4. your suggestion doesn't work, because you need close things in the terms of distance to remain close in the terms of sort. Your suggestion works only in the neighborhood of the 0,0 point Best regards Ladislav

### [7/7] from: grantwparks:y:ahoo at: 26-Sep-2000 13:33

I think it is an interesting programming topic (and I did not mean my earlier comments to be absolute - it was directed at the seemingly unresolvable debates about whether or not do such and such). Most sorting is done, it seems, on some sort of scalar level, and I was interested in the idea of using each sort item as a description of something else, in this case a point on a plane. (I'm not sure why your #4 comment means my function is wrong. Unless you mean that the resulting sorted list is in order according to "its distance from a point 0,0 that defines the most 'lower-left' point of an arbitrary plane". I.E. it only works in quadrant II of that old x-y graph. Please explain, if not. Maybe what's more useful would be the function sorting in terms of distance from any point, where I think the deltas come back in.) To me it could relate to some sort of abstraction on sort (using objects, blocks whatever) that might be useful. I guess I knew I was opening myself up to a "look who's talking" attitude, but I was thinking about a real-world problem in terms of some abstraction and trying to really understand what the original poster's interleave method was getting at. Often that leads to a cool generalization that can be used elsewhere. That's why I considered it to be a programming topic. You could argue it belonged in a different list, but this is where the original post was, and I'm trying to learn REBOL, so it's where I posted. Is that the same as a thread discussing why MS is successful, or why they suck? Again, on some level you could argue it is. Up to you, I guess. --- [lmecir--geocities--com] wrote: