📄 ch04_16.htm
字号:
<HTML><HEAD><TITLE>Recipe 4.15. Sorting a List by Computable Field (Perl Cookbook)</TITLE><METANAME="DC.title"CONTENT="Perl Cookbook"><METANAME="DC.creator"CONTENT="Tom Christiansen & Nathan Torkington"><METANAME="DC.publisher"CONTENT="O'Reilly & Associates, Inc."><METANAME="DC.date"CONTENT="1999-07-02T01:32:11Z"><METANAME="DC.type"CONTENT="Text.Monograph"><METANAME="DC.format"CONTENT="text/html"SCHEME="MIME"><METANAME="DC.source"CONTENT="1-56592-243-3"SCHEME="ISBN"><METANAME="DC.language"CONTENT="en-US"><METANAME="generator"CONTENT="Jade 1.1/O'Reilly DocBook 3.0 to HTML 4.0"><LINKREV="made"HREF="mailto:online-books@oreilly.com"TITLE="Online Books Comments"><LINKREL="up"HREF="ch04_01.htm"TITLE="4. Arrays"><LINKREL="prev"HREF="ch04_15.htm"TITLE="4.14. Sorting an Array Numerically"><LINKREL="next"HREF="ch04_17.htm"TITLE="4.16. Implementing a Circular List"></HEAD><BODYBGCOLOR="#FFFFFF"><img alt="Book Home" border="0" src="gifs/smbanner.gif" usemap="#banner-map" /><map name="banner-map"><area shape="rect" coords="1,-2,616,66" href="index.htm" alt="Perl Cookbook"><area shape="rect" coords="629,-11,726,25" href="jobjects/fsearch.htm" alt="Search this book" /></map><div class="navbar"><p><TABLEWIDTH="684"BORDER="0"CELLSPACING="0"CELLPADDING="0"><TR><TDALIGN="LEFT"VALIGN="TOP"WIDTH="228"><ACLASS="sect1"HREF="ch04_15.htm"TITLE="4.14. Sorting an Array Numerically"><IMGSRC="../gifs/txtpreva.gif"ALT="Previous: 4.14. Sorting an Array Numerically"BORDER="0"></A></TD><TDALIGN="CENTER"VALIGN="TOP"WIDTH="228"><B><FONTFACE="ARIEL,HELVETICA,HELV,SANSERIF"SIZE="-1"><ACLASS="chapter"REL="up"HREF="ch04_01.htm"TITLE="4. Arrays"></A></FONT></B></TD><TDALIGN="RIGHT"VALIGN="TOP"WIDTH="228"><ACLASS="sect1"HREF="ch04_17.htm"TITLE="4.16. Implementing a Circular List"><IMGSRC="../gifs/txtnexta.gif"ALT="Next: 4.16. Implementing a Circular List"BORDER="0"></A></TD></TR></TABLE></DIV><DIVCLASS="sect1"><H2CLASS="sect1"><ACLASS="title"NAME="ch04-20687">4.15. Sorting a List by Computable Field</A></H2><DIVCLASS="sect2"><H3CLASS="sect2"><ACLASS="title"NAME="ch04-pgfId-1299">Problem</A></H3><PCLASS="para">You want to sort a list by something more complex than a simple string or numeric comparison.</P><PCLASS="para">This is common when working with objects ("sort by the employee's salary") or complex data structures ("sort by the third element in the array that this is a reference to"). It's also applicable when you want to sort by more than one key, for instance, sorting by birthday and then by name when multiple people have the same birthday.</P></DIV><DIVCLASS="sect2"><H3CLASS="sect2"><ACLASS="title"NAME="ch04-pgfId-1307">Solution</A></H3><PCLASS="para">Use the customizable comparison routine in <CODECLASS="literal">sort</CODE>:</P><PRECLASS="programlisting">@ordered = sort { compare() } @unordered;</PRE><PCLASS="para">You can speed this up by precomputing the field.</P><PRECLASS="programlisting">@precomputed = map { [compute(),$_] } @unordered;@ordered_precomputed = sort { $a->[0] <=> $b->[0] } @precomputed;@ordered = map { $_->[1] } @ordered_precomputed;</PRE><PCLASS="para">And, finally, you can combine the three steps:</P><PRECLASS="programlisting">@ordered = map { $_->[1] } sort { $a->[0] <=> $b->[0] } map { [compute(), $_] } @unordered;</PRE></DIV><DIVCLASS="sect2"><H3CLASS="sect2"><ACLASS="title"NAME="ch04-pgfId-1335">Discussion</A></H3><PCLASS="para">The use of a comparison routine was explained in <ACLASS="xref"HREF="ch04_15.htm"TITLE="Sorting an Array Numerically">Recipe 4.14</A>. As well as using built-in operators like <=>, you can construct more complex tests:</P><PRECLASS="programlisting">@ordered = sort { $a->name cmp $b->name } @employees;</PRE><PCLASS="para">You often see <CODECLASS="literal">sort</CODE> used like this in part of a <CODECLASS="literal">foreach</CODE> loop:</P><PRECLASS="programlisting">foreach $employee (sort { $a->name cmp $b->name } @employees) { print $employee->name, " earns \$", $employee->salary, "\n";}</PRE><PCLASS="para">If you're going to do a lot of work with elements in a particular order, it's more efficient to sort it once and work from that:</P><PRECLASS="programlisting">@sorted_employees = sort { $a->name cmp $b->name } @employees;foreach $employee (@sorted_employees) { print $employee->name, " earns \$", $employee->salary, "\n";}# load %bonusforeach $employee (@sorted_employees) { if ( $bonus{ $employee->ssn } ) { print $employee->name, " got a bonus!\n"; }}</PRE><PCLASS="para">We can put multiple comparisons in the routine and separate them with <CODECLASS="literal">||</CODE>. <CODECLASS="literal">||</CODE> is a short-circuit operator: it returns the first true (non-zero) value it finds. This means we can sort by one kind of comparison, but if the elements are equal (the comparison returns 0) we can sort by another. This has the effect of a sort within a sort:</P><PRECLASS="programlisting">@sorted = sort { $a->name cmp $b->name || $b->age <=> $a->age } @employees;</PRE><PCLASS="para">This first considers the names of the two employees to be compared. If they're not equal, <CODECLASS="literal">||</CODE> stops and returns the result of the <CODECLASS="literal">cmp</CODE> (effectively sorting them in ascending order by name). If the names are equal, though, <CODECLASS="literal">||</CODE> keeps testing and returns the result of the <=> (sorting them in descending order by age). The result is a list that is sorted by name and by age within groups of the same name.</P><PCLASS="para">Let's look at a real-life example of sorting. Here we fetch all users, as User::pwent objects. Then we sort them by name and print the sorted list:</P><PRECLASS="programlisting">use User::pwent qw(getpwent);@users = ();# fetch all userswhile (defined($user = getpwent)) { push(@users, $user);} @users = sort { $a->name cmp $b->name } @users;foreach $user (@users) { print $user->name, "\n";}</PRE><PCLASS="para">We can have more than simple comparisons, or combinations of simple comparisons. This code sorts a list of names by comparing the <EMCLASS="emphasis">second</EM> letters of the names. It gets the second letters by using <CODECLASS="literal">substr</CODE>:</P><PRECLASS="programlisting">@sorted = sort { substr($a,1,1) cmp substr($b,1,1) } @names;</PRE><PCLASS="para">and here we sort by length of the strings:</P><PRECLASS="programlisting">@sorted = sort { length $a <=> length $b } @strings;</PRE><PCLASS="para">The <CODECLASS="literal">sort</CODE> function calls the code block each time it needs to compare two elements, and the number of comparisons grows dramatically with the number of elements we're sorting. Sorting 10 elements requires (on average) 46 comparisons, but sorting 1,000 elements requires 14,000 comparisons. A time-consuming operation like a <CODECLASS="literal">split</CODE> or a subroutine call for each comparison can easily make your program crawl.</P><PCLASS="para">Fortunately, we can remove this bottleneck by running the operation once per element prior to the sort. Use <ACLASS="indexterm"NAME="ch04-idx-1000006770-0"></A><CODECLASS="literal">map</CODE> to store the results of the operation in an array whose elements are anonymous arrays containing both the computed field and the original field. Then we <CODECLASS="literal">sort</CODE> this array of arrays on the precomputed field, and use <CODECLASS="literal">map</CODE> to get the sorted original data. This <CODECLASS="literal">map</CODE>-<CODECLASS="literal">sort</CODE>-<CODECLASS="literal">map</CODE> concept is useful and common, so let's look at it in more depth.</P><PCLASS="para">Let's apply <CODECLASS="literal">map</CODE>-<CODECLASS="literal">sort</CODE>-<CODECLASS="literal">map</CODE> to the sorting by string length example:</P><PRECLASS="programlisting">@temp = map { [ length $_, $_ ] } @strings;@temp = sort { $a->[0] <=> $b->[0] } @temp;@sorted = map { $_->[1] } @temp;</PRE><PCLASS="para">The first line creates a temporary array of strings and their lengths, using <CODECLASS="literal">map</CODE>. The second line sorts the temporary array by comparing the precomputed lengths. The third line turns the sorted temporary array of strings and lengths back into a sorted array of strings. This way we calculated the length of each string only once.</P><PCLASS="para">Because the input to each line is the output of the previous line (the <CODECLASS="literal">@temp</CODE> array we make in line 1 is fed to <CODECLASS="literal">sort</CODE> in line 2, and that output is fed to <CODECLASS="literal">map</CODE> in line 3), we can combine it into one statement and eliminate the temporary array:</P><PRE⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -