📄 ch04_08.htm
字号:
<HTML><HEAD><TITLE>Recipe 4.7. Finding Elements in One Array but Not Another (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:34Z"><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_07.htm"TITLE="4.6. Extracting Unique Elements from a List"><LINKREL="next"HREF="ch04_09.htm"TITLE="4.8. Computing Union, Intersection, or Difference of Unique Lists"></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_07.htm"TITLE="4.6. Extracting Unique Elements from a List"><IMGSRC="../gifs/txtpreva.gif"ALT="Previous: 4.6. Extracting Unique Elements from a List"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_09.htm"TITLE="4.8. Computing Union, Intersection, or Difference of Unique Lists"><IMGSRC="../gifs/txtnexta.gif"ALT="Next: 4.8. Computing Union, Intersection, or Difference of Unique Lists"BORDER="0"></A></TD></TR></TABLE></DIV><DIVCLASS="sect1"><H2CLASS="sect1"><ACLASS="title"NAME="ch04-29725">4.7. Finding Elements in One Array but Not Another</A></H2><DIVCLASS="sect2"><H3CLASS="sect2"><ACLASS="title"NAME="ch04-pgfId-721">Problem <ACLASS="indexterm"NAME="ch04-idx-1000006659-0"></A><ACLASS="indexterm"NAME="ch04-idx-1000006659-1"></A><ACLASS="indexterm"NAME="ch04-idx-1000006659-2"></A><ACLASS="indexterm"NAME="ch04-idx-1000006659-3"></A><ACLASS="indexterm"NAME="ch04-idx-1000006659-4"></A><ACLASS="indexterm"NAME="ch04-idx-1000006659-5"></A></A></H3><PCLASS="para">You want to find elements that are in one array but not another.</P></DIV><DIVCLASS="sect2"><H3CLASS="sect2"><ACLASS="title"NAME="ch04-pgfId-727">Solution</A></H3><PCLASS="para">You want to find elements in <CODECLASS="literal">@A</CODE> that aren't in <CODECLASS="literal">@B</CODE>. Build a hash of the keys of <CODECLASS="literal">@B</CODE> to use as a lookup table. Then check each element in <CODECLASS="literal">@A</CODE> to see if it is in <CODECLASS="literal">@B</CODE>.</P><DIVCLASS="sect3"><H4CLASS="sect3"><ACLASS="title"NAME="ch04-pgfId-1000006463">Straightforward implementation</A></H4><PRECLASS="programlisting"># assume @A and @B are already loaded%seen = (); # lookup table to test membership of B@aonly = (); # answer# build lookup tableforeach $item (@B) { $seen{$item} = 1 }# find only elements in @A and not in @Bforeach $item (@A) { unless ($seen{$item}) { # it's not in %seen, so add to @aonly push(@aonly, $item); }}</PRE></DIV><DIVCLASS="sect3"><H4CLASS="sect3"><ACLASS="title"NAME="ch04-pgfId-1000006484">More idiomatic version</A></H4><PRECLASS="programlisting">my %seen; # lookup tablemy @aonly;# answer# build lookup table@seen{@B} = ();foreach $item (@A) { push(@aonly, $item) unless exists $seen{$item};}</PRE></DIV></DIV><DIVCLASS="sect2"><H3CLASS="sect2"><ACLASS="title"NAME="ch04-pgfId-733">Discussion</A></H3><PCLASS="para"><ACLASS="indexterm"NAME="ch04-idx-1000006682-0"></A>As with nearly any problem in Perl that asks whether a scalar is in one list or another, this one uses a hash. First, process <CODECLASS="literal">@B</CODE> so that the <CODECLASS="literal">%seen</CODE> hash records each element from <CODECLASS="literal">@B</CODE> by setting its value to 1. Then process <CODECLASS="literal">@A</CODE> one element at a time, checking whether that particular element had been in <CODECLASS="literal">@B</CODE> by consulting the <CODECLASS="literal">%seen</CODE> hash.</P><PCLASS="para">The given code retains duplicate elements in <CODECLASS="literal">@A </CODE>. This can be easily fixed by adding the elements of <CODECLASS="literal">@A</CODE> to <CODECLASS="literal">%seen</CODE> as they are processed:</P><PRECLASS="programlisting">foreach $item (@A) { push(@aonly, $item) unless $seen{$item}; $seen{$item} = 1; # mark as seen}</PRE><PCLASS="para">The two solutions differ mainly in how they build the hash. The first iterates through <CODECLASS="literal">@B</CODE>. The second uses a <EMCLASS="emphasis">hash slice</EM> to initialize the hash. A <ACLASS="indexterm"NAME="ch04-idx-1000006665-0"></A>hash slice is easiest illustrated by example:</P><PRECLASS="programlisting">$hash{"key1"} = 1;$hash{"key2"} = 2;</PRE><PCLASS="para">is equivalent to:</P><PRECLASS="programlisting">@hash{"key1", "key2"} = (1,2);</PRE><PCLASS="para">The list in the curly braces holds the keys; the list on the right holds the values. We initialize <CODECLASS="literal">%seen</CODE> in the first solution by looping over each element in <CODECLASS="literal">@B</CODE> and setting the appropriate value of <CODECLASS="literal">%seen</CODE> to 1. In the second, we simply say:</P><PRECLASS="programlisting">@seen{@B} = ();</PRE><PCLASS="para">This uses items in <CODECLASS="literal">@B</CODE> as keys for <CODECLASS="literal">%seen</CODE>, setting each corresponding value to <CODECLASS="literal">undef</CODE>, because there are fewer values on the right than places to put them. This works out here because we check for existence of the key, not logical truth or <CODECLASS="literal">defined</CODE>ness of the value. If we needed true values, a slice could still shorten our code:</P><PRECLASS="programlisting">@seen{@B} = (1) x @B;</PRE></DIV><DIVCLASS="sect2"><H3CLASS="sect2"><ACLASS="title"NAME="ch04-pgfId-767">See Also</A></H3><PCLASS="para">Hash slices are explained in <ICLASS="filename">perldata </I>(1) and the <ACLASS="olink"HREF="../prog/ch02_03.htm#PERL2-CH-2-SECT-3.1">"Variables"</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_09.htm"TITLE="Computing Union, Intersection, or Difference of Unique Lists">Recipe 4.8</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_07.htm"TITLE="4.6. Extracting Unique Elements from a List"><IMGSRC="../gifs/txtpreva.gif"ALT="Previous: 4.6. Extracting Unique Elements from a List"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_09.htm"TITLE="4.8. Computing Union, Intersection, or Difference of Unique Lists"><IMGSRC="../gifs/txtnexta.gif"ALT="Next: 4.8. Computing Union, Intersection, or Difference of Unique Lists"BORDER="0"></A></TD></TR><TR><TDALIGN="LEFT"VALIGN="TOP"WIDTH="228">4.6. Extracting Unique Elements from a List</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.8. Computing Union, Intersection, or Difference of Unique Lists</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 + -