August 2017
Intermediate to advanced
360 pages
8h 35m
Chinese
Content preview from 算法技术手册（原书第2 版）
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.
314
｜
第
11
章
表
11
-
4
：辅助线程所带来的性能改进（
r
=
1
和
r
= MAXINT 相比）
n 从使用多线程到不用线程所获得的性能提速
65,536 1.24
131,072 1.37
262,144 1.35
524,288 1.37
1,048,576 1.31
由图
11-1
可以看到，
r
=2
时较之前的性能改善是最多的。因为每创建一个新的线程都会
有一定的费用，我们无法保证直至辅助线程执行完毕，主线程不会发生等待和阻塞问题，
所以不应不假思索地执行一个新线程。这些性能改进在不同的平台上会有不同。
很多情况下，加速比也和
CPU
数目息息相关。图
11-2
给出了在双核和四核平台下的加
速比情况。其中行表示可用线程数，列则表示阈值
r
。需要排序的元素数目
n
是
1 048
576
。四核平台下的性能显示出多线程的高效（加速比高达
1.5
）而双核平台下只有不到
5%
的改进。
从对并行算法中加速比的研究可以看出，额外的线程或者处理器会带来一些帮助，但其
实还是会有一些限制条件。多线程快速排序之所以可以达到一个不错的加速比，是因为
实现不会导致多线程对共享资源的竞争，进而也就不会导致死锁。如果其他问题能够解
决多线程导致的竞争和死锁情况，那么它们也可以从多线程中受益。
11.4 概率算法
概率算法会将一系列的随机值（例如随机数）作为计算的一部分，所以在每次运行该算
法时都会得到不同的解。
从实践角度来看，在确定性自动机上生成随机值是一件非常困难的事情。虽然我们可以
生成真假莫辨的伪随机值，费用却是不可忽视的。
11.4.1 估计集合 ...
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access
More than 5,000 organizations count on O’Reilly
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.Julian F.
I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.Addison B.
I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.Amir M.
I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.