page219.html

来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 85 行

HTML
85 行
字号 
<HTML><HEAD><TITLE>Floating-Point Keys</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="tex2html3727" HREF="page220.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3725" HREF="page217.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3719" HREF="page218.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html3729" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION008320000000000000000">Floating-Point Keys</A></H2><P>Dealing with floating-point number involves a little more work.In Python the floating-point numbers are representedusing the IEEE double-precision format (64 bits).We seek a function <I>f</I> which maps a floating-point valueinto a non-negative integer.A characteristic of floating-point numbers that must be dealt withis the extremely wide range of values which can be represented.For example, when using IEEE floating-point,the smallest double precision quantity that can be represented is <IMG WIDTH=72 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline61969" SRC="img877.gif"  >and the largest is  <IMG WIDTH=98 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline61971" SRC="img878.gif"  >.Somehow we need to map values in this large domaininto the range of an <tt>int</tt>.<P>Every non-zero floating-point quantity <I>x</I> can be written uniquely as<P> <IMG WIDTH=321 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath61965" SRC="img879.gif"  ><P>where  <IMG WIDTH=64 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61975" SRC="img880.gif"  >,  <IMG WIDTH=84 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61977" SRC="img881.gif"  > and  <IMG WIDTH=125 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61979" SRC="img882.gif"  >.The quantity <I>s</I> is called the <em>sign</em><A NAME=10777>&#160;</A>,<I>m</I> is called the <em>mantissa</em><A NAME=10779>&#160;</A>or <em>significant</em><A NAME=10781>&#160;</A>and <I>e</I> is called the <em>exponent</em><A NAME=10783>&#160;</A>.This suggests the following definition for the function <I>f</I>:<P><A NAME="eqnhashingfp">&#160;</A> <IMG WIDTH=500 HEIGHT=48 ALIGN=BOTTOM ALT="equation10784" SRC="img883.gif"  ><P>where  <IMG WIDTH=57 HEIGHT=15 ALIGN=BOTTOM ALT="tex2html_wrap_inline61989" SRC="img884.gif"  >.<P>This hashing method is best understood by consideringthe conditions under which a collision occursbetween two distinct floating-point numbers <I>x</I> and <I>y</I>.Let  <IMG WIDTH=20 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline61995" SRC="img885.gif"  > and  <IMG WIDTH=20 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline61997" SRC="img886.gif"  > be the mantissas of <I>x</I> and <I>y</I>, respectively.The collision occurs when <I>f</I>(<I>x</I>)=<I>f</I>(<I>y</I>).<P> <IMG WIDTH=500 HEIGHT=105 ALIGN=BOTTOM ALT="eqnarray10792" SRC="img887.gif"  ><P>Thus, <I>x</I> and <I>y</I> collide if their mantissas differ by less than 1/2<I>W</I>.Notice that the sign of the number is not considered.Thus, <I>x</I> and -<I>x</I> collideAlso, the exponent is not considered.Therefore, if <I>x</I> and <I>y</I> collide,then so too do <I>x</I> and  <IMG WIDTH=42 HEIGHT=30 ALIGN=MIDDLE ALT="tex2html_wrap_inline62021" SRC="img888.gif"  > for all permissible values of <I>k</I>.<P>Program&nbsp;<A HREF="page219.html#progfloata"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> introduces the class <tt>Float</tt>which extends the built-in <tt>float</tt> classas well as the abstract <tt>Object</tt> classintroduced in Program&nbsp;<A HREF="page116.html#progobjecta"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.In this case,the <tt>__hash__</tt> method computes thehash function defined in Equation&nbsp;<A HREF="page219.html#eqnhashingfp"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<P><P><A NAME="11095">&#160;</A><A NAME="progfloata">&#160;</A> <IMG WIDTH=575 HEIGHT=161 ALIGN=BOTTOM ALT="program10803" SRC="img889.gif"  ><BR><STRONG>Program:</STRONG> <tt>Float</tt> class <tt>__hash__</tt> method.<BR><P><P>This implementation uses the <tt>frexp</tt> functionprovided in the standard Python <tt>math</tt> module.This function returns the mantissa, <tt>m</tt>,and the exponent, <tt>e</tt>,of a given floating-point number.In the IEEE standard floating-point formatthe least-significant 52 bits of a 64-bit floating-point numberrepresent the quantity  <IMG WIDTH=135 HEIGHT=29 ALIGN=MIDDLE ALT="tex2html_wrap_inline62025" SRC="img890.gif"  >.Since  <IMG WIDTH=57 HEIGHT=15 ALIGN=BOTTOM ALT="tex2html_wrap_inline61989" SRC="img884.gif"  >,we can rewrite Equation&nbsp;<A HREF="page219.html#eqnhashingfp"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> as follows:<P> <IMG WIDTH=500 HEIGHT=70 ALIGN=BOTTOM ALT="eqnarray10821" SRC="img891.gif"  ><P>Thus, we can compute the hash function by computing the integer <I>m</I>'and then shifting the binary representation of that integer20 bits to the right as shown in Program&nbsp;<A HREF="page219.html#progfloata"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.Clearly the running time of the <tt>__hash__</tt> method is <I>O</I>(1).<P><HR><A NAME="tex2html3727" HREF="page220.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3725" HREF="page217.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3719" HREF="page218.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html3729" 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 &#169; 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a>  All rights reserved.</ADDRESS></BODY></HTML>

page219.html - 源码说明

本页面展示了「Data Structures And Algorithms With Object-Oriented Design Patterns In Python (2003) source code and」中的 page219.html 源码文件，采用 HTML 编程语言编写，共 85 行代码。您可以在线阅读完整代码内容，也可以返回资源详情页下载完整源码包进行本地学习和开发。

虫虫下载站收录了大量与Object-Oriented相关的技术资源，包括源代码、技术文档、电路图等，是电子工程师和嵌入式开发者的专业学习平台。

⌨️ 快捷键说明

复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?