Path: utzoo!attcan!uunet!cs.utexas.edu!samsung!brutus.cs.uiuc.edu!jarthur!elroy.jpl.nasa.gov!jpl-devvax!lwall
From: lwall@jpl-devvax.JPL.NASA.GOV (Larry Wall)
Newsgroups: comp.lang.perl
Subject: Re: Ordering one array by another
Message-ID: <7561@jpl-devvax.JPL.NASA.GOV>
Date: 27 Mar 90 18:13:21 GMT
References: <8251@ogicse.ogi.edu>
Reply-To: lwall@jpl-devvax.JPL.NASA.GOV (Larry Wall)
Organization: Jet Propulsion Laboratory, Pasadena, CA
Lines: 45

In article <8251@ogicse.ogi.edu> schaefer@ogicse.ogi.edu (Barton E. Schaefer) writes:
: I have a sorted list of keywords, and a file (well, stdin actually, but
: no matter) consisting of lines each of which contains at most one of the
: keywords.  There may be keywords not in the file, and lines with zero
: keywords (which are ignored), but no pair of lines both contain the same
: keyword.  What I want to do is reorder the input lines to match the order
: in the list of keywords.

We really don't have enough info to decide the fastest algorithm, because
we'd need to know the number of keywords, the relative number of lines not
containing any keyword, and the usual location of the keyword in each line,
and the frequency distribution of characters in the keys and lines.

However, on the assumption that pattern compilation and matching is going
to dominate the timing, I'd suspect the following of being QUITE fast:

$prog = <<EOF;
				    while (<STDIN>) { study;
EOF

foreach $key (@keys) {
    $prog .= <<EOF;
				        \$found{'$key'} = \$_ if ?\\b$key\\b?;
EOF
}

$prog .= <<EOF;
				    }
EOF

print $prog if $verbose;
eval $prog; die $@ if $@;
print grep($_,@found{@keys});

Several things to note.  First, it turns your algorithm inside out so that
it can study each line.  (This also avoids the "whomp" overhead.)  Second,
it generates a complete loop with the pattern matches so that it avoids
unnecessary evals or runtime pattern compilation inside the loop.  Third,
it uses the ?? search because each key only wants to match once, and there's
no point in looking for the key again once it has matched.

On the other hand, the associative array costs you something in storage and
efficiency.  Try it, and see if it's faster.

Larry