📄 ch04_09.htm
字号:
<HTML><HEAD><TITLE>Recipe 4.8. Computing Union, Intersection, or Difference of Unique Lists (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:31:46Z"><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_08.htm"TITLE="4.7. Finding Elements in One Array but Not Another"><LINKREL="next"HREF="ch04_10.htm"TITLE="4.9. Appending One Array to Another"></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_08.htm"TITLE="4.7. Finding Elements in One Array but Not Another"><IMGSRC="../gifs/txtpreva.gif"ALT="Previous: 4.7. Finding Elements in One Array but Not Another"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_10.htm"TITLE="4.9. Appending One Array to Another"><IMGSRC="../gifs/txtnexta.gif"ALT="Next: 4.9. Appending One Array to Another"BORDER="0"></A></TD></TR></TABLE></DIV><DIVCLASS="sect1"><H2CLASS="sect1"><ACLASS="title"NAME="ch04-13496">4.8. Computing Union, Intersection, or Difference of Unique Lists</A></H2><DIVCLASS="sect2"><H3CLASS="sect2"><ACLASS="title"NAME="ch04-pgfId-777">Problem</A></H3><PCLASS="para">You have a pair of lists, each having unduplicated items. You'd like to find out which items are in both lists (<ICLASS="firstterm">intersection</I>), one but not the other (<ICLASS="firstterm">difference</I>), or either (<ICLASS="firstterm">union</I>).</P></DIV><DIVCLASS="sect2"><H3CLASS="sect2"><ACLASS="title"NAME="ch04-pgfId-783">Solution</A></H3><PCLASS="para">The following solutions need the listed initializations:</P><PRECLASS="programlisting">@a = (1, 3, 5, 6, 7, 8);@b = (2, 3, 5, 7, 9);@union = @isect = @diff = ();%union = %isect = ();%count = ();</PRE><DIVCLASS="sect3"><H4CLASS="sect3"><ACLASS="title"NAME="ch04-pgfId-1000005746">Simple solution for union and intersection</A></H4><PRECLASS="programlisting">foreach $e (@a) { $union{$e} = 1 }foreach $e (@b) { if ( $union{$e} ) { $isect{$e} = 1 } $union{$e} = 1;}@union = keys %union;@isect = keys %isect;</PRE></DIV><DIVCLASS="sect3"><H4CLASS="sect3"><ACLASS="title"NAME="ch04-29528">More idiomatic version</A></H4><PRECLASS="programlisting">foreach $e (@a, @b) { $union{$e}++ && $isect{$e}++ }@union = keys %union;@isect = keys %isect;</PRE></DIV><DIVCLASS="sect3"><H4CLASS="sect3"><ACLASS="title"NAME="ch04-pgfId-1000005764">Union, intersection, and symmetric difference<ACLASS="indexterm"NAME="ch04-idx-1000006686-0"></A></A></H4><PRECLASS="programlisting">foreach $e (@a, @b) { $count{$e}++ }foreach $e (keys %count) { push(@union, $e); if ($count{$e} == 2) { push @isect, $e; } else { push @diff, $e; }}</PRE></DIV><DIVCLASS="sect3"><H4CLASS="sect3"><ACLASS="title"NAME="ch04-pgfId-1000005777">Indirect solution</A></H4><PRECLASS="programlisting">@isect = @diff = @union = ();foreach $e (@a, @b) { $count{$e}++ }foreach $e (keys %count) { push(@union, $e); push @{ $count{$e} == 2 ? \@isect : \@diff }, $e;}</PRE></DIV></DIV><DIVCLASS="sect2"><H3CLASS="sect2"><ACLASS="title"NAME="ch04-pgfId-801">Discussion</A></H3><PCLASS="para">The first solution most directly computes the union and intersection of two lists, neither containing duplicates. Two different hashes are used to record whether a particular item goes in the union or the intersection. We first put every element of the first array in the union hash, giving it a true value. Then processing each element of the second array, we check whether that element is already present in the union. If it is, then we put it in the intersection as well. In any event, it is put into the union. When we're done, we extract the keys of both the union and intersection hashes. The values aren't needed.</P><PCLASS="para">The second solution (<ACLASS="xref"HREF="ch04_09.htm#ch04-29528"TITLE="More idiomatic version">"More idiomatic version</A>") is essentially the same but relies on familiarity with the Perl (and <EMCLASS="emphasis">awk</EM>, C, C++, and Java) <CODECLASS="literal">++</CODE> and <CODECLASS="literal">&&</CODE> operators. By placing the <CODECLASS="literal">++</CODE> after the variable, we first look at its old value before incrementing it. The first time through it won't be in the union, which makes the first part of the <CODECLASS="literal">&&</CODE> false, and the second part is consequently ignored. The second time that we encounter the same element, it's already present in the union, so we put it in the intersection as well.</P><PCLASS="para">The third solution uses just one hash to track how many times each element has been seen. Once both arrays have their elements recorded in the hash, we process those hash keys one at a time. If it's there, it goes in the union array. Keys whose values are 2 were in both arrays, so they are put in the intersection array. Keys whose values are 1 were in just one of the two arrays, so they are put in the difference array. The elements of the output arrays are not in the same order as the elements in the input arrays.</P><PCLASS="para">The last solution, like the previous one, uses just one hash to count how many times each element has been encountered. However, this time we choose the array within the <CODECLASS="literal">@{</CODE> <CODECLASS="literal">....</CODE> <CODECLASS="literal">}</CODE> block.</P><PCLASS="para">We compute the symmetric difference here, not the simple difference. These are set theoretic terms. A <ICLASS="firstterm">symmetric</I> difference is the set of all the elements that are members of either <CODECLASS="literal">@A</CODE> or <CODECLASS="literal">@B</CODE>, but not of both. A <ICLASS="filename">simple difference</I> is the set of members of <CODECLASS="literal">@A</CODE> but not of <CODECLASS="literal">@B</CODE>, which we calculated in <ACLASS="xref"HREF="ch04_08.htm"TITLE="Finding Elements in One Array but Not Another">Recipe 4.7</A>.<ACLASS="indexterm"NAME="ch04-idx-1000007368-0"></A><ACLASS="indexterm"NAME="ch04-idx-1000007368-1"></A></P></DIV><DIVCLASS="sect2"><H3CLASS="sect2"><ACLASS="title"NAME="ch04-pgfId-1000007370">See Also</A></H3><PCLASS="para">The <ACLASS="olink"HREF="../prog/ch02_03.htm#PERL2-CH-2-SECT-3.5">"Hashes (Associative Arrays)"</A> section of <ACLASS="olink"HREF="../prog/ch02_01.htm">Chapter 2</A> of <ACLASS="citetitle"HREF="../prog/index.htm"TITLE="Programming Perl"><CITECLASS="citetitle">Programming Perl</CITE></A>; <ACLASS="xref"HREF="ch05_01.htm"TITLE="Hashes">Chapter 5</A>; we use hashes in a similar fashion in <ACLASS="xref"HREF="ch04_07.htm"TITLE="Extracting Unique Elements from a List">Recipe 4.6</A> and <ACLASS="xref"HREF="ch04_08.htm"TITLE="Finding Elements in One Array but Not Another">Recipe 4.7</A> <ACLASS="indexterm"NAME="ch04-idx-1000007377-0"></A><ACLASS="indexterm"NAME="ch04-idx-1000007377-1"></A><ACLASS="indexterm"NAME="ch04-idx-1000007377-2"></A><ACLASS="indexterm"NAME="ch04-idx-1000007377-3"></A><ACLASS="indexterm"NAME="ch04-idx-1000007377-4"></A><ACLASS="indexterm"NAME="ch04-idx-1000007377-5"></A></P></DIV></DIV><DIVCLASS="htmlnav"><P></P><HRALIGN="LEFT"WIDTH="684"TITLE="footer"><TABLEWIDTH="684"BORDER="0"CELLSPACING="0"CELLPADDING="0"><TR><TDALIGN="LEFT"VALIGN="TOP"WIDTH="228"><ACLASS="sect1"HREF="ch04_08.htm"TITLE="4.7. Finding Elements in One Array but Not Another"><IMGSRC="../gifs/txtpreva.gif"ALT="Previous: 4.7. Finding Elements in One Array but Not Another"BORDER="0"></A></TD><TDALIGN="CENTER"VALIGN="TOP"WIDTH="228"><ACLASS="book"HREF="index.htm"TITLE="Perl Cookbook"><IMGSRC="../gifs/txthome.gif"ALT="Perl Cookbook"BORDER="0"></A></TD><TDALIGN="RIGHT"VALIGN="TOP"WIDTH="228"><ACLASS="sect1"HREF="ch04_10.htm"TITLE="4.9. Appending One Array to Another"><IMGSRC="../gifs/txtnexta.gif"ALT="Next: 4.9. Appending One Array to Another"BORDER="0"></A></TD></TR><TR><TDALIGN="LEFT"VALIGN="TOP"WIDTH="228">4.7. Finding Elements in One Array but Not Another</TD><TDALIGN="CENTER"VALIGN="TOP"WIDTH="228"><ACLASS="index"HREF="index/index.htm"TITLE="Book Index"><IMGSRC="../gifs/index.gif"ALT="Book Index"BORDER="0"></A></TD><TDALIGN="RIGHT"VALIGN="TOP"WIDTH="228">4.9. Appending One Array to Another</TD></TR></TABLE><HRALIGN="LEFT"WIDTH="684"TITLE="footer"><FONTSIZE="-1"></DIV<!-- LIBRARY NAV BAR --> <img src="../gifs/smnavbar.gif" usemap="#library-map" border="0" alt="Library Navigation Links"><p> <a href="copyrght.htm">Copyright © 2002</a> O'Reilly & Associates. All rights reserved.</font> </p> <map name="library-map"> <area shape="rect" coords="1,0,85,94" href="../index.htm"><area shape="rect" coords="86,1,178,103" href="../lwp/index.htm"><area shape="rect" coords="180,0,265,103" href="../lperl/index.htm"><area shape="rect" coords="267,0,353,105" href="../perlnut/index.htm"><area shape="rect" coords="354,1,446,115" href="../prog/index.htm"><area shape="rect" coords="448,0,526,132" href="../tk/index.htm"><area shape="rect" coords="528,1,615,119" href="../cookbook/index.htm"><area shape="rect" coords="617,0,690,135" href="../pxml/index.htm"></map> </BODY></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -