📄 unit 4-62%.htm
字号:
mso-fareast-font-family:Symbol;mso-bidi-font-family:Symbol;color:black;
mso-font-kerning:0pt;mso-ansi-language:EN-US'><span style='mso-list:Ignore'>·<span
style='font:7.0pt "Times New Roman"'>
</span></span></span><![endif]><span lang=EN-US style='font-size:12.0pt;
color:black;mso-font-kerning:0pt;mso-ansi-language:EN-US'><a
href="javascript:AssessmentByName('assm-qz-mc-performance-improvement');">Multiple-Choice
Quiz 4</a> <o:p></o:p></span></p>
<p class=MsoNormal align=left style='mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;margin-left:36.1pt;text-align:left;text-indent:-18.0pt;mso-pagination:
widow-orphan;mso-list:l3 level1 lfo4;tab-stops:list 36.0pt'><![if !supportLists]><span
lang=EN-US style='font-size:10.0pt;mso-bidi-font-size:12.0pt;font-family:Symbol;
mso-fareast-font-family:Symbol;mso-bidi-font-family:Symbol;color:black;
mso-font-kerning:0pt;mso-ansi-language:EN-US'><span style='mso-list:Ignore'>·<span
style='font:7.0pt "Times New Roman"'>
</span></span></span><![endif]><span lang=EN-US style='font-size:12.0pt;
color:black;mso-font-kerning:0pt;mso-ansi-language:EN-US'><a
href="javascript:AssessmentByName('assm-exer-performance-improvement');">Exercise
4</a> <o:p></o:p></span></p>
<p class=MsoNormal align=left style='mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan'><span lang=EN-US
style='font-size:12.0pt;color:black;mso-font-kerning:0pt;mso-ansi-language:
EN-US'>This unit is about making programs run fast. Before we get started, it
should be mentioned that speed is usually not the most important attribute of a
program. The professional programmer is usually most concerned with making a
program that is easy to write, debug, and maintain.<o:p></o:p></span></p>
<p class=MsoNormal align=left style='mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan'><span lang=EN-US
style='font-size:12.0pt;color:black;mso-font-kerning:0pt;mso-ansi-language:
EN-US'>There are a number of good reasons for this concern:<o:p></o:p></span></p>
<p class=MsoNormal align=left style='mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;margin-left:36.1pt;text-align:left;text-indent:-18.0pt;mso-pagination:
widow-orphan;mso-list:l0 level1 lfo6;tab-stops:list 36.0pt'><![if !supportLists]><span
lang=EN-US style='font-size:10.0pt;mso-bidi-font-size:12.0pt;font-family:Symbol;
mso-fareast-font-family:Symbol;mso-bidi-font-family:Symbol;color:black;
mso-font-kerning:0pt;mso-ansi-language:EN-US'><span style='mso-list:Ignore'>·<span
style='font:7.0pt "Times New Roman"'>
</span></span></span><![endif]><span lang=EN-US style='font-size:12.0pt;
color:black;mso-font-kerning:0pt;mso-ansi-language:EN-US'>A correct program,
even if slow, computes right answers much faster than a program that isn't! It
is often better to use a simple but slow algorithm if it makes your program
more reliable. <o:p></o:p></span></p>
<p class=MsoNormal align=left style='mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;margin-left:36.1pt;text-align:left;text-indent:-18.0pt;mso-pagination:
widow-orphan;mso-list:l0 level1 lfo6;tab-stops:list 36.0pt'><![if !supportLists]><span
lang=EN-US style='font-size:10.0pt;mso-bidi-font-size:12.0pt;font-family:Symbol;
mso-fareast-font-family:Symbol;mso-bidi-font-family:Symbol;color:black;
mso-font-kerning:0pt;mso-ansi-language:EN-US'><span style='mso-list:Ignore'>·<span
style='font:7.0pt "Times New Roman"'>
</span></span></span><![endif]><span lang=EN-US style='font-size:12.0pt;
color:black;mso-font-kerning:0pt;mso-ansi-language:EN-US'>A program that is
finished computes right answers much faster than a program that isn't! Fast
programs often take much more time to develop, and they are useless until they
are finished. <o:p></o:p></span></p>
<p class=MsoNormal align=left style='mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;margin-left:36.1pt;text-align:left;text-indent:-18.0pt;mso-pagination:
widow-orphan;mso-list:l0 level1 lfo6;tab-stops:list 36.0pt'><![if !supportLists]><span
lang=EN-US style='font-size:10.0pt;mso-bidi-font-size:12.0pt;font-family:Symbol;
mso-fareast-font-family:Symbol;mso-bidi-font-family:Symbol;color:black;
mso-font-kerning:0pt;mso-ansi-language:EN-US'><span style='mso-list:Ignore'>·<span
style='font:7.0pt "Times New Roman"'>
</span></span></span><![endif]><span lang=EN-US style='font-size:12.0pt;
color:black;mso-font-kerning:0pt;mso-ansi-language:EN-US'>Computers double in
speed every 18 months. Computer technology changes so fast that improvements in
speed can often be obtained simply by waiting for the next generation of
hardware. Also, speed improvements of less than a factor of two are barely
noticeable to users in an interactive setting. <o:p></o:p></span></p>
<p class=MsoNormal align=left style='mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan'><span lang=EN-US
style='font-size:12.0pt;color:black;mso-font-kerning:0pt;mso-ansi-language:
EN-US'>Having said all that, there are still many occasions to make a program
run faster. Perhaps you have created a clear, simple, and maintainable program,
but its performance is just not acceptable. What do you do now?<o:p></o:p></span></p>
<p class=MsoNormal align=left style='mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan'><span lang=EN-US
style='font-size:12.0pt;color:black;mso-font-kerning:0pt;mso-ansi-language:
EN-US'>I once had a student who worked for a bank in <st1:State w:st="on"><st1:place
w:st="on">New York</st1:place></st1:State>. Every weekend, the bank flew him
to <st1:State w:st="on"><st1:place w:st="on">New York</st1:place></st1:State>
to write software. It turned out the bank had a program that updated accounts
by the simple algorithm that follows:<o:p></o:p></span></p>
<p class=MsoNormal align=left style='text-align:left;mso-pagination:widow-orphan;
tab-stops:45.8pt 91.6pt 137.4pt 183.2pt 229.0pt 274.8pt 320.6pt 366.4pt 412.2pt 458.0pt 503.8pt 549.6pt 595.4pt 641.2pt 687.0pt 732.8pt'><span
lang=EN-US style='font-size:12.0pt;color:black;mso-font-kerning:0pt;mso-ansi-language:
EN-US'>loop<o:p></o:p></span></p>
<p class=MsoNormal align=left style='text-align:left;mso-pagination:widow-orphan;
tab-stops:45.8pt 91.6pt 137.4pt 183.2pt 229.0pt 274.8pt 320.6pt 366.4pt 412.2pt 458.0pt 503.8pt 549.6pt 595.4pt 641.2pt 687.0pt 732.8pt'><span
lang=EN-US style='font-size:12.0pt;color:black;mso-font-kerning:0pt;mso-ansi-language:
EN-US'><o:p> </o:p></span></p>
<p class=MsoNormal align=left style='text-align:left;mso-pagination:widow-orphan;
tab-stops:45.8pt 91.6pt 137.4pt 183.2pt 229.0pt 274.8pt 320.6pt 366.4pt 412.2pt 458.0pt 503.8pt 549.6pt 595.4pt 641.2pt 687.0pt 732.8pt'><span
lang=EN-US style='font-size:12.0pt;color:black;mso-font-kerning:0pt;mso-ansi-language:
EN-US'><span style='mso-spacerun:yes'> </span>read update<o:p></o:p></span></p>
<p class=MsoNormal align=left style='text-align:left;mso-pagination:widow-orphan;
tab-stops:45.8pt 91.6pt 137.4pt 183.2pt 229.0pt 274.8pt 320.6pt 366.4pt 412.2pt 458.0pt 503.8pt 549.6pt 595.4pt 641.2pt 687.0pt 732.8pt'><span
lang=EN-US style='font-size:12.0pt;color:black;mso-font-kerning:0pt;mso-ansi-language:
EN-US'><o:p> </o:p></span></p>
<p class=MsoNormal align=left style='text-align:left;mso-pagination:widow-orphan;
tab-stops:45.8pt 91.6pt 137.4pt 183.2pt 229.0pt 274.8pt 320.6pt 366.4pt 412.2pt 458.0pt 503.8pt 549.6pt 595.4pt 641.2pt 687.0pt 732.8pt'><span
lang=EN-US style='font-size:12.0pt;color:black;mso-font-kerning:0pt;mso-ansi-language:
EN-US'><span style='mso-spacerun:yes'> </span>find account
data<o:p></o:p></span></p>
<p class=MsoNormal align=left style='text-align:left;mso-pagination:widow-orphan;
tab-stops:45.8pt 91.6pt 137.4pt 183.2pt 229.0pt 274.8pt 320.6pt 366.4pt 412.2pt 458.0pt 503.8pt 549.6pt 595.4pt 641.2pt 687.0pt 732.8pt'><span
lang=EN-US style='font-size:12.0pt;color:black;mso-font-kerning:0pt;mso-ansi-language:
EN-US'><o:p> </o:p></span></p>
<p class=MsoNormal align=left style='text-align:left;mso-pagination:widow-orphan;
tab-stops:45.8pt 91.6pt 137.4pt 183.2pt 229.0pt 274.8pt 320.6pt 366.4pt 412.2pt 458.0pt 503.8pt 549.6pt 595.4pt 641.2pt 687.0pt 732.8pt'><span
lang=EN-US style='font-size:12.0pt;color:black;mso-font-kerning:0pt;mso-ansi-language:
EN-US'><span style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span>update the account<o:p></o:p></span></p>
<p class=MsoNormal align=left style='text-align:left;mso-pagination:widow-orphan;
tab-stops:45.8pt 91.6pt 137.4pt 183.2pt 229.0pt 274.8pt 320.6pt 366.4pt 412.2pt 458.0pt 503.8pt 549.6pt 595.4pt 641.2pt 687.0pt 732.8pt'><span
lang=EN-US style='font-size:12.0pt;color:black;mso-font-kerning:0pt;mso-ansi-language:
EN-US'><o:p> </o:p></span></p>
<p class=MsoNormal align=left style='text-align:left;mso-pagination:widow-orphan;
tab-stops:45.8pt 91.6pt 137.4pt 183.2pt 229.0pt 274.8pt 320.6pt 366.4pt 412.2pt 458.0pt 503.8pt 549.6pt 595.4pt 641.2pt 687.0pt 732.8pt'><span
lang=EN-US style='font-size:12.0pt;color:black;mso-font-kerning:0pt;mso-ansi-language:
EN-US'><o:p> </o:p></span></p>
<p class=MsoNormal align=left style='mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan'><span lang=EN-US
style='font-size:12.0pt;color:black;mso-font-kerning:0pt;mso-ansi-language:
EN-US'>This worked, but it took hours to process a large batch of updates.
Every "find account data" step required a fairly lengthy lookup of
records stored on magnetic tape. My student had a better idea. He kept the
account data in sorted order and he sorted the updates as well. Once sorted (a
relatively fast operation), he could make one pass through the accounts data,
making all the updates in order. Sequential access to the accounts data was so
much faster, he expected a factor of 10 speedup. It also paid his tuition!<o:p></o:p></span></p>
<p class=MsoNormal align=left style='mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan'><span lang=EN-US
style='font-size:12.0pt;color:black;mso-font-kerning:0pt;mso-ansi-language:
EN-US'>This is the general pattern for making programs faster:<o:p></o:p></span></p>
<p class=MsoNormal align=left style='mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;margin-left:36.1pt;text-align:left;text-indent:-18.0pt;mso-pagination:
widow-orphan;mso-list:l1 level1 lfo8;tab-stops:list 36.0pt'><![if !supportLists]><span
lang=EN-US style='font-size:12.0pt;mso-fareast-font-family:"Times New Roman";
color:black;mso-font-kerning:0pt;mso-ansi-language:EN-US'><span
style='mso-list:Ignore'>1.<span style='font:7.0pt "Times New Roman"'>
</span></span></span><![endif]><span lang=EN-US style='font-size:12.0pt;
color:black;mso-font-kerning:0pt;mso-ansi-language:EN-US'>Understand what makes
the program slow. Where does the program spend most of its time? Chances are
good that a few places account for a lot of time. <o:p></o:p></span></p>
<p class=MsoNormal align=left style='mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;margin-left:36.1pt;text-align:left;text-indent:-18.0pt;mso-pagination:
widow-orphan;mso-list:l1 level1 lfo8;tab-stops:list 36.0pt'><![if !supportLists]><span
lang=EN-US style='font-size:12.0pt;mso-fareast-font-family:"Times New Roman";
color:black;mso-font-kerning:0pt;mso-ansi-language:EN-US'><span
style='mso-list:Ignore'>2.<span style='font:7.0pt "Times New Roman"'>
</span></span></span><![endif]><span lang=EN-US style='font-size:12.0pt;
color:black;mso-font-kerning:0pt;mso-ansi-language:EN-US'>Design and implement
a solution that will give you the most speedup for the least effort. <o:p></o:p></span></p>
<p class=MsoNormal align=left style='mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;margin-left:36.1pt;text-align:left;text-indent:-18.0pt;mso-pagination:
widow-orphan;mso-list:l1 level1 lfo8;tab-stops:list 36.0pt'><![if !supportLists]><span
lang=EN-US style='font-size:12.0pt;mso-fareast-font-family:"Times New Roman";
color:black;mso-font-kerning:0pt;mso-ansi-language:EN-US'><span
style='mso-list:Ignore'>3.<span style='font:7.0pt "Times New Roman"'>
</span></span></span><![endif]><span lang=EN-US style='font-size:12.0pt;
color:black;mso-font-kerning:0pt;mso-ansi-language:EN-US'>Iterate steps 1 and 2
until performance is satisfactory or until the remaining optimizations are not
worth the effort. <o:p></o:p></span></p>
<p class=MsoNormal align=left style='margin-top:12.0pt;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan'><span lang=EN-US
style='font-size:10.0pt;color:black;mso-font-kerning:0pt;mso-ansi-language:
EN-US'>© Copyright 1999-2005 iCarnegie, Inc. All rights reserved.<o:p></o:p></span></p>
<b><span lang=EN-US style='font-size:18.0pt;font-family:SimSun;mso-bidi-font-family:
SimSun;mso-ansi-language:EN-US;mso-fareast-language:ZH-CN;mso-bidi-language:
AR-SA'><br clear=all style='page-break-before:always'>
</span></b>
<h2><span lang=EN-US style='font-family:"Times New Roman";color:black;
mso-ansi-language:EN-US'>4.1 Measurement and Profiling<o:p></o:p></span></h2>
<p class=MsoNormal align=left style='mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;margin-left:36.1pt;text-align:left;text-indent:-18.0pt;mso-pagination:
widow-orphan;mso-list:l2 level1 lfo10;tab-stops:list 36.0pt'><![if !supportLists]><span
lang=EN-US style='font-size:10.0pt;mso-bidi-font-size:12.0pt;font-family:Symbol;
mso-fareast-font-family:Symbol;mso-bidi-font-family:Symbol;color:black;
mso-font-kerning:0pt;mso-ansi-language:EN-US'><span style='mso-list:Ignore'>·<span
style='font:7.0pt "Times New Roman"'>
</span></span></span><![endif]><span lang=EN-US style='font-size:12.0pt;
color:black;mso-font-kerning:0pt;mso-ansi-language:EN-US'><a
href="javascript:ContentByName('pg-variables');">4.1.1 What to Measure</a> <o:p></o:p></span></p>
<p class=MsoNormal align=left style='mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;margin-left:36.1pt;text-align:left;text-indent:-18.0pt;mso-pagination:
widow-orphan;mso-list:l2 level1 lfo10;tab-stops:list 36.0pt'><![if !supportLists]><span
lang=EN-US style='font-size:10.0pt;mso-bidi-font-size:12.0pt;font-family:Symbol;
mso-fareast-font-family:Symbol;mso-bidi-font-family:Symbol;color:black;
mso-font-kerning:0pt;mso-ansi-language:EN-US'><span style='mso-list:Ignore'>·<span
style='font:7.0pt "Times New Roman"'>
</span></span></span><![endif]><span lang=EN-US style='font-size:12.0pt;
color:black;mso-font-kerning:0pt;mso-ansi-language:EN-US'><a
href="javascript:ContentByName('pg-timing-mechanisms');">4.1.2 Timing
Mechanisms</a> <o:p></o:p></span></p>
<p class=MsoNormal align=left style='margin-top:12.0pt;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan'><span lang=EN-US
style='font-size:10.0pt;color:black;mso-font-kerning:0pt;mso-ansi-language:
EN-US'>© Copyright 1999-2005 iCarnegie, Inc. All rights reserved.<o:p></o:p></span></p>
<b><span lang=EN-US style='font-size:18.0pt;font-family:SimSun;mso-bidi-font-family:
SimSun;mso-ansi-language:EN-US;mso-fareast-language:ZH-CN;mso-bidi-language:
AR-SA'><br clear=all style='page-break-before:always'>
</span></b>
<h2><span lang=EN-US style='font-family:"Times New Roman";color:black;
mso-ansi-language:EN-US'>4.1.1 What to Measure<o:p></o:p></span></h2>
<p><span lang=EN-US style='font-family:"Times New Roman";color:black;
mso-ansi-language:EN-US'>It is often surprising where programs spend most of
their time. Therefore, it is foolish to optimize without actually measuring a
working program. This is another reason not to optimize too much during
development: you may spend a lot of time optimizing the wrong thing. (If you
feel you must optimize early, make some small tests to convince yourself that
optimization is really going to be necessary.)<o:p></o:p></span></p>
<p><span lang=EN-US style='font-family:"Times New Roman";color:black;
mso-ansi-language:EN-US'>The most common thing to measure is CPU time. CPU time
is the time a process spends executing instructions. It does not count any time
spent executing other programs or just waiting. An alternative is to measure
real time or "wall clock time" (sometimes just "wall
time")-which is the time an ordinary clock on the wall or a wrist watch
shows. The difference between CPU time and wall time can give some indication
of the time spent waiting for I/O. Earlier, I described a bank program that my
student optimized. It probably spent most of its time waiting for disk I/O.
Therefore, you should also measure how much your program waits for I/O
operations. You might want to break down I/O into categories including file
I/O, network I/O, and graphical I/O.<o:p></o:p></span></p>
<p><span lang=EN-US style='font-family:"Times New Roman";color:black;
mso-ansi-language:EN-US'>CPU time can be divided between <i>user time</i>, the
time spent directly executing your program code, and <i>system time</i>, the
time spent by the operating system on behalf of your program. All of these
measurements help you understand what is going on in your program when it
executes.<o:p></o:p></span></p>
<p class=footer><span lang=EN-US style='font-family:"Times New Roman";
color:black;mso-ansi-language:EN-US'>© Copyright 1999-2005 iCarnegie, Inc.
All rights reserved.<o:p></o:p></span></p>
<b><span lang=EN-US style='font-size:18.0pt;font-family:SimSun;mso-bidi-font-family:
SimSun;mso-ansi-language:EN-US;mso-fareast-language:ZH-CN;mso-bidi-language:
AR-SA'><br clear=all style='page-break-before:always'>
</span></b>
<h2><span lang=EN-US style='font-family:"Times New Roman";color:black;
mso-ansi-language:EN-US'>4.1.2 Timing Mechanisms<o:p></o:p></span></h2>
<p class=MsoNormal align=left style='mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;margin-left:36.1pt;text-align:left;text-indent:-18.0pt;mso-pagination:
widow-orphan;mso-list:l10 level1 lfo12;tab-stops:list 36.0pt'><![if !supportLists]><span
lang=EN-US style='font-size:10.0pt;mso-bidi-font-size:12.0pt;font-family:Symbol;
mso-fareast-font-family:Symbol;mso-bidi-font-family:Symbol;color:black;
mso-font-kerning:0pt;mso-ansi-language:EN-US'><span style='mso-list:Ignore'>·<span
style='font:7.0pt "Times New Roman"'>
</span></span></span><![endif]><span lang=EN-US style='font-size:12.0pt;
color:black;mso-font-kerning:0pt;mso-ansi-language:EN-US'><a
href="http://www.icarnegie.com/content/SSD/SSD6/2.0/normal/pg-performance-improvement/pg-profiling/pg-timing-mechanisms/pg-timing-mechanisms.html#hires#hires">High-Resolution
on Pentium Systems</a> <o:p></o:p></span></p>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -