Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
PerlMonks  

Re: Advanced Sorting - GRT - Guttman Rosler Transform

by dws (Chancellor)
on Feb 15, 2002 at 21:14 UTC ( #145767=note: print w/ replies, xml ) Need Help??


in reply to Advanced Sorting - GRT - Guttman Rosler Transform

The basic idea is to encode the precomputed keys into a string, usually using pack() such that perl can sort them lexicographically

This is a key point. I've seen it overlooked in two cases, both leading to subtle sorting problems of the "well, this stuff sorts most of the time" variety.

A naive read of Guttman-Rosler is "hey, let's cram the key parts together in a way we can uncram them later." That's necessary, but not sufficient. Simple concatenation won't do. You must pack(), or concatenate in such a way that the keys are aligned for a lexicographic sort. If you see someone use join in a Guttman-Rosler search, watch out!

Consider the difference between

Naive join Aligned keys foo 47 foo 47 foo 103 foo 103
If you don't align the keys (typically via pack or a carefully crafted sprintf), you risk getting composite keys that sort correctly most of the time. A variant of the problem can occur with non-numeric strings when joining them with a character like '|'.


Comment on Re: Advanced Sorting - GRT - Guttman Rosler Transform
Select or Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://145767]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (11)
As of 2015-07-06 22:28 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (84 votes), past polls