page392.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 63 行
HTML
63 行
<HTML><HEAD><TITLE>Comparing Sets</TITLE></HEAD><BODY bgcolor="#FFFFFF"> <a href="../index.html" target="_top"><img src="../icons/usins.gif" alt="Logo" align=right></a><b>Data Structures and Algorithms with Object-Oriented Design Patterns in Python</b><br><A NAME="tex2html5702" HREF="page393.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5700" HREF="page389.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5696" HREF="page391.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5704" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION0012203000000000000000">Comparing Sets</A></H3><P>There is a special family of operators for comparing sets.Consider two sets, say <I>S</I> and <I>T</I>.We say that <I>S</I> is a <em>subset</em><A NAME=27794> </A> of <I>T</I>,written <IMG WIDTH=42 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline62735" SRC="img1034.gif" >,if every element of <I>S</I> is also an element of <I>T</I>.If there is at least one element of <I>T</I> that is not also an element of <I>S</I>,we say that <I>S</I> is a<em>proper subset</em><A NAME=27796> </A><A NAME=27797> </A> of <I>T</I>,written <IMG WIDTH=42 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline66739" SRC="img1564.gif" >.We can also reverse the order in which the expressions are writtento get <IMG WIDTH=43 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline66741" SRC="img1565.gif" > or <IMG WIDTH=43 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline66743" SRC="img1566.gif" >,which indicates that <I>T</I> is a(proper) <em>superset</em><A NAME=27799> </A><A NAME=27800> </A><A NAME=27801> </A>of <I>S</I>.<P>The set comparison operators follow the rule that if <IMG WIDTH=42 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline62735" SRC="img1034.gif" >and <IMG WIDTH=43 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline62737" SRC="img1035.gif" > then <IMG WIDTH=42 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline66753" SRC="img1567.gif" >,which is analogous to a similar property of numbers: <IMG WIDTH=171 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline66755" SRC="img1568.gif" >.However, set comparison is unlike numeric comparison in that thereexist sets <I>S</I> and <I>T</I> for which neither <IMG WIDTH=42 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline62735" SRC="img1034.gif" > nor <IMG WIDTH=43 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline62737" SRC="img1035.gif" >!For example, clearly this is the case for <IMG WIDTH=70 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66765" SRC="img1569.gif" > and <IMG WIDTH=71 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66767" SRC="img1570.gif" >.Mathematically, the relation <IMG WIDTH=10 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline66769" SRC="img1571.gif" > is calleda <em>partial order</em><A NAME=27803> </A>because there exist some pairs of sets for which neither <IMG WIDTH=42 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline62735" SRC="img1034.gif" >nor <IMG WIDTH=43 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline62737" SRC="img1035.gif" > holds;whereas the relation <IMG WIDTH=10 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline59297" SRC="img394.gif" > (among integers, say) is a total order.<P>Program <A HREF="page392.html#progsetAsArrayd"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> defines the methods <tt>__eq__</tt> and <tt>__lt__</tt>.The former tests for equalityand the latter determines whether the relation <IMG WIDTH=10 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline66769" SRC="img1571.gif" > holdsbetween <tt>self</tt> and <tt>set</tt>.Both operators return a <tt>bool</tt> result.The worst-case running time of each of these operations is clearly <I>O</I>(<I>N</I>).<P><P><A NAME="28219"> </A><A NAME="progsetAsArrayd"> </A> <IMG WIDTH=575 HEIGHT=371 ALIGN=BOTTOM ALT="program27810" SRC="img1572.gif" ><BR><STRONG>Program:</STRONG> <tt>SetAsArray</tt> class <tt>__eq__</tt> and <tt>__lt__</tt> methods.<BR><P><P>A complete repertoire of comparison methods would also includemethods to compute <IMG WIDTH=10 HEIGHT=19 ALIGN=MIDDLE ALT="tex2html_wrap_inline66781" SRC="img1573.gif" >, <IMG WIDTH=10 HEIGHT=19 ALIGN=MIDDLE ALT="tex2html_wrap_inline66783" SRC="img1574.gif" >, <IMG WIDTH=10 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline66785" SRC="img1575.gif" >, and <IMG WIDTH=11 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline61127" SRC="img760.gif" >.These operations follow directly from the implementationshown in Program <A HREF="page392.html#progsetAsArrayd"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (Exercise <A HREF="page413.html#exercisesetscomparison"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>).<P><HR><A NAME="tex2html5702" HREF="page393.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5700" HREF="page389.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5696" HREF="page391.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5704" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS><img src="../icons/bruno.gif" alt="Bruno" align=right><a href="../copyright.html">Copyright © 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.</ADDRESS></BODY></HTML>⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?