`

[珠玑之椟]估算的应用与Little定律 - 五岳

阅读更多
原帖地址:http://www.cnblogs.com/wuyuegb2312/p/3133633.html

  估算的数据主要依赖于所能获得的数据和常识,有时还包括实践而不仅仅是理论。它常常作为一个大问题中的子问题,恰当地估算可以省去精确计算的时间和开销。在计算机领域,所谓常识的内容很宽泛,比如硬盘的传输速度、CPU每秒能执行多少指令、各种数据结构的大小甚至每分钟录入的单词数。有些数据是能够从各种资料中查得的,但仅仅靠记忆总难免遗漏;如果有经过学习而建立起的系统的知识结构,那便能很方便地把这些常识组织起来,除此以外,还可以靠平时经验的积累和一些面试题上的启发了。这里将进行一个收集,随时更新。

  Little定律深入了估算所依赖的法则的细节:总花费等于各个部分的花费再乘以总的部分数,它在计算机系统方面的一些计算中十分有用。


 

  计算机方面的估算问题:

  1.硬盘文件读写速度的小问题:是否能超过10MB/s?(笔者某次面试中被问到的的一个关于服务器的问题的子问题)

  分析:根据以往拷贝文件的经验,对于不是多个零散小文件的情况,读写速度比这个值要快得多,因此做出了肯定的答案。

 

  2.确定一个空循环for(i=0;i<n;i++)在一秒钟执行的次数n,使其为CPU在1秒钟内执行总指令数目的一半(《编程之美》第一章的子问题)

分析:先把空循环化为汇编指令:

loop:
mov dx i
inc dx
mov i dx
cmp i n
jl loop

一共5条指令,假设使用的CPU是单核2.4GHz即每秒2.4G个时钟周期,(常识)现代CPU每个时钟周期执行两条以上的代码,那么一秒钟可以执行空循环(2 400 000 000 *2)/5 = 960 000 000次。

(为了提高精度而进行降低数量级的优化不再讨论)

 

  3.struct node {int i; struct node *p}是否可以将这样的2 000 000个结点装入128MB内存的计算机中?(《编程珠玑》7.2性能估计)

分析:为了简化讨论,假定在32位机上int和指针都是32位的,共用了8B,直接计算的结果是只需16MB空间,而《编程珠玑》作者的128MB的计算机通常有85MB空闲,看上去是够用的。然而使用malloc()为结点分配空间时会额外占用空间(原因:malloc的机制,Linux的malloc()有一个每次分配的最小大小,小于这个值也会分配这么多;struct的对齐),这个值在作者计算机上是40B,导致了一共占用了96MB空间,事实上是不够用的。

 

  4.运算的实际消耗时间:使用for(i=0;i<n;i++) fa =sqrt(10.0);计算单次sqrt()的运行时间是否准确?(《编程珠玑》7.2性能估计)

实际的单次运算时间可能慢得多,因为sqrt()可能保存了最近参数作为起始值。

  (更多待补充……)


 

  估算常用法则:

1.“72法则”:以年利率r%进行投资y年,如果r * y = 72,那么投资差不多会翻倍。

如果以t = (1+r/100)y,并把r代换成72/y,即t = (1+72/(100y))y,进行作图,会发现这一段t的值都在2附近,符合这条法则。

应用:假设一个指数程序解决n=40的问题需要10s,且n每增加1运行时间就增加12%,那么根据72法则,n每增加6,运行时间就加倍。进一步地,n每增加60,运行时间就为原来的1000倍(210的近似数)。

 

2.(记忆常识)π秒是一个纳世纪。

注:一年有3.155 * 107秒,而π取3.14、纳世纪为100年 * 10-9 ,这时两者的积与这个值近似。

 

3.Little定律:队列中物体的平均数量为进入速率与平均停留时间的乘积。

注:显而易见的法则是,总开销等于每个开销乘以单元的个数;而Litte定律描述的是一个动态系统。如果想了解定律的证明,需要随机过程与排队论的相关知识。

应用:多用户系统的响应时间公式,思考时间z的n个用户登录到响应时间r的系统,每个用户周期都为用户的思考和系统响应,即z+r;作业总数为n,那么对一个时间点来看,平均负荷为n、平均响应时间为z+r,吞吐量为x(每个时间单位处理的作业数),根据Little定律,n = x*(z+r),这样就可以求解r = n/x -z。

例1:(编程珠玑(续),7.4节)一个计算机系统,包括磁盘、处理器、操作系统和20个思考时间为20秒的终端,通过观察,它的磁盘每处理一个作业就要处理100个数据请求,而磁盘每秒钟可以处理25个请求。那么系统的吞吐量和响应时间各为多少?

解答:吞吐量直接计算,为25/100=0.25个作业/秒,响应时间r = 20/0.25 -20 = 60秒。这在流平衡下就是精确解。

例2:(编程珠玑(续),习题7.8)假设一个作业在某机器上执行时间是20秒,该机器一次可能同时执行10个作业,而你的作业是100等待执行的作业中的最后一个,作业以先进先出方式执行。大概需要等多久才能等到作业执行结束?

解答:这里要考虑两个排队系统:待执行任务队列和计算机系统本身。根据Little定律,第二个系统任务输出率X=L/R,L=10个任务,R=20秒,因此X=0.5个任务/秒。这也是第二个系统的任务到达率。因此最后一个任务会在前99个任务在198秒后完成时进入,再加上20秒的执行时间,总的时间是218秒。

 

往期回顾:

 

“珠玑之椟”系列简介与索引

位向量/位图的定义和应用

 


本文链接:http://www.cnblogs.com/wuyuegb2312/p/3133633.html,转载请注明。

分享到:
评论

相关推荐

    编程珠玑 编程珠玑 编程珠玑 编程

    编程珠玑的核心概念之一是数据结构与算法的选择和设计。书中的例子多以实际问题为背景,通过分析和比较不同的解决方案,展示了如何在特定情境下选择最合适的算法和数据结构。例如,如何有效地搜索和排序数据,以及...

    编程珠玑习题集锦

    《编程珠玑》是计算机科学领域的一本经典之作,作者Jon Bentley通过一系列实际问题的探讨,引导读者理解和掌握编程中的高效解题技巧。书中的问题和解决方案涵盖了算法设计、数据结构优化以及问题解决策略等多个方面...

    编程珠玑.pdf

    7.3 Little定律 64 7.4 原理 65 7.5 习题 66 7.6 深入阅读 67 7.7 日常速算(边栏) 67 第8章 人员备忘录 69 8.1 备忘录 69 8.2 原理 71 8.3 深入阅读 71 第三部分 人性化I/O 第9章 小语言 75 9.1 Pic语言 76 9.2 ...

    编程珠玑源码下载编程珠玑书后源代码

    《编程珠玑》是计算机科学领域的一本经典之作,由Jon Bentley 编著,它以其深入浅出的方式探讨了程序设计的问题和解决方案,尤其在数据结构、算法优化以及问题解决策略方面有着独到的见解。这本书的源代码是作者为了...

    编程珠玑2

    ### 编程珠玑2:经典算法之作 《编程珠玑2》是计算机科学领域的一本经典著作,由Jon Bentley撰写,Addison-Wesley出版社于2000年出版。该书是一系列关于编程技巧与算法设计的文章集合,不仅为初学者提供了深入浅出...

    编程珠玑-第2版-修订版

    《编程珠玑(第 2版·修订版)》是计算机科学方面的经典名著。书的内容围绕程序设计人员面对的一系列实际问题展开。作者JonBentley以其独有的洞察力和创造力,引导读者理解这些问题并学会解决方法,而这些正是程序员...

    编程珠玑 第2版(修订版)_编程珠玑修订_资料_

    《编程珠玑 第2版(修订版)》是一本深受程序员喜爱的经典著作,它不仅提供了丰富的编程实践经验,还深入探讨了程序设计的艺术与智慧。这本书的修订版更是在原版基础上进行了更新和完善,旨在帮助程序员提升编程技能,...

    编程珠玑 算法 数据结构

    ### 编程珠玑:算法与数据结构精要 #### 核心概念解析 在《编程珠玑》这本书中,作者深入浅出地探讨了算法和数据结构的重要性及其实际应用。该书被认为是学习计算机科学基础知识不可或缺的经典之作。下面将根据...

    编程珠玑pdf

    《编程珠玑》第二版,由Jon Bentley撰写,是一本被众多顶级大师推荐的经典之作,深入探讨了软件工程中令人着迷的一面——编程技巧与创新思维。本书不仅为学生提供了宝贵的指导,也对经验丰富的程序员有着重要的启示...

    编程珠玑(Programming Pearls)

    本书不仅为初学者提供了宝贵的编程指导,也为经验丰富的程序员们提供了一系列深入思考编程问题的方法与技巧。接下来将对这本书的一些核心章节进行详细介绍,并提炼出其中的重要知识点。 ### 一、概述 #### 书籍...

    编程珠玑 编程珠玑续

    《编程珠玑》和其续篇是两部深受程序员喜爱的经典著作,主要涵盖了程序设计、算法分析和数据结构等核心编程领域。这两本书以其深入浅出的讲解方式和丰富的实例,帮助读者提升编程技巧和解决问题的能力。 在《编程...

    编程珠玑(中文版+英文版)

    编程珠玑--软件开发者阅读计划-入门级 书目之一,内含中文版和英文版。

    编程珠玑(第二版)答案

    根据提供的标题“编程珠玑(第二版)答案”和描述“编程珠玑(第二版)答案”,我们可以推测出这是关于《编程珠玑》这本书的相关解答资料。《编程珠玑》是一本经典的计算机科学书籍,作者为Jon Bentley。本书旨在...

    编程珠玑--算法

    编程中的一本关于算法的好书。

    ASP.NET.2.0.编程-------珠玑

    ### ASP.NET 2.0 编程——珠玑 #### 第1章:窍门程序回顾 在本章中,作者回顾了ASP.NET以往版本中的一些关键窍门程序,并且探讨了这些技巧如何演变并影响了ASP.NET 2.0的技术栈。其中特别提到的是ASP.NET v1.1中的...

    编程珠玑(续)

    《编程珠玑(续)》是计算机科学方面的经典名著《编程珠玑》的姊妹篇,讲述了对于程序员有共性的知识。书中涵盖了程序员操纵程序的技术、程序员取舍的技巧、输入和输出设计以及算法示例,这些内容组成一个有机的整体,...

    ASP.NET\ASP.NET 2.0编程珠玑--来自MVP 2.0编程珠玑--来自MVP的权威开发指南

    《ASP.NET 2.0编程珠玑--来自MVP的权威开发指南》一书深入探讨了ASP.NET 2.0的核心概念和技术,旨在帮助开发者熟练掌握这一平台。 在ASP.NET 2.0中,控件是构建用户界面的关键组件。它们包括服务器控件和HTML控件,...

    编程珠玑(含源码)

    《编程珠玑》是一本经典的计算机科学图书,其主要内容涵盖了算法设计、问题解决以及程序优化等多个方面的知识。这本书以其深入浅出的讲解方式,深受程序员和计算机科学家的喜爱,被誉为编程界的"智慧结晶"。源码的...

    编程珠玑番外篇-G. 程序员心底的小声音

    【编程珠玑番外篇-G. 程序员心底的小声音】这篇文章主要探讨了程序员在编程学习和成长过程中的不同阶段以及如何从中级水平晋升到高级水平的问题。作者将程序员分为新手、高手和中手三个层次,并指出,中手程序员通常...

    编程珠玑-[美]乔恩美特利.mobi

    编程珠玑-[美]乔恩美特利.mobi、kindle文档、第二版修订版

Global site tag (gtag.js) - Google Analytics