扭腰时报醒世好文：美国股市不再是经济的晴雨表 (转载)# Stock
b*e
1 楼
请问：既然quick selection 理论上证明是linear，比heap selection快。那为什么
top k 的问题都用heap 呢？
按理说应该用最快的quick selection啊。
top k 的问题都用heap 呢？
按理说应该用最快的quick selection啊。
w*n
2 楼
8，9个的时候能做不？
a*6
3 楼
【 以下文字转载自 Military 讨论区 】
发信人: abcxyz2046 (灌君), 信区: Military
标 题: 扭腰时报醒世好文：美国股市不再是经济的晴雨表
发信站: BBS 未名空间站 (Tue Feb 15 10:50:19 2011, 美东)
换句话说，中国股市输出价值观，华尔街不再是美国经济的晴雨表，而成了投机巨头们
独享的乐园。
http://www.nytimes.com/2011/02/14/opinion/14Salmon.html?src=me&
Wall Street’s Dead End (华尔街的穷途末路）
By FELIX SALMON （作者：菲利克斯.沙门鱼）
。。。 But look at America’s stock exchanges more closely, and there’s
less to them than meets the eye. In truth, the stock market is becoming
increasingly irrelevant — a trend that threatens the core principles of
American capitalism.
。。。可是，如果近观美国股市，远非像表面看起来那么吸引人的眼球。实际上，股市
和经济渐行渐远，这种势头在威胁美帝的核心价值。
These days a healthy stock market doesn’t mean a healthy economy, as a
glance at the high unemployment rate or the low labor-market participation
rate will show. The Tea Party is right about one thing: What’s good for
Wall Street isn’t necessarily good for Main Street. And the Germans aren’t
buying the New York Stock Exchange for its commoditized, highly competitive
and ultra-low-margin stock business, but rather for its lucrative
derivatives operations.
这年头，良好的股市不再是经济的晴雨表，这个从居高不下的下岗率就能看出。奶茶党
有一个说法是对的：华尔街的利好不一定是 P民街之福。德国人参与华尔街的大交易仅
仅是为了金融衍生这颗摇钱树。
The stock market is still huge, of course: the companies listed on American
exchanges are valued at more than $17 trillion, and they’re not going to
disappear in the foreseeable future.
But the glory days of publicly traded companies dominating the American
business landscape may be over. The number of companies listed on the major
domestic exchanges peaked in 1997 at more than 7,000, and it has been
falling ever since. It’s now down to about 4,000 companies, and given its
steep downward trend will surely continue to shrink.
Nor are the remaining stocks an obvious proxy for the health of the American
economy. Innovative American companies like Apple and Google may be worth
hundreds of billions of dollars, but most of them don’t pay dividends or
employ many Americans, and their shares are essentially speculative
investments for people making a bet on how we’re going to live in the
future.
......
发信人: abcxyz2046 (灌君), 信区: Military
标 题: 扭腰时报醒世好文：美国股市不再是经济的晴雨表
发信站: BBS 未名空间站 (Tue Feb 15 10:50:19 2011, 美东)
换句话说，中国股市输出价值观，华尔街不再是美国经济的晴雨表，而成了投机巨头们
独享的乐园。
http://www.nytimes.com/2011/02/14/opinion/14Salmon.html?src=me&
Wall Street’s Dead End (华尔街的穷途末路）
By FELIX SALMON （作者：菲利克斯.沙门鱼）
。。。 But look at America’s stock exchanges more closely, and there’s
less to them than meets the eye. In truth, the stock market is becoming
increasingly irrelevant — a trend that threatens the core principles of
American capitalism.
。。。可是，如果近观美国股市，远非像表面看起来那么吸引人的眼球。实际上，股市
和经济渐行渐远，这种势头在威胁美帝的核心价值。
These days a healthy stock market doesn’t mean a healthy economy, as a
glance at the high unemployment rate or the low labor-market participation
rate will show. The Tea Party is right about one thing: What’s good for
Wall Street isn’t necessarily good for Main Street. And the Germans aren’t
buying the New York Stock Exchange for its commoditized, highly competitive
and ultra-low-margin stock business, but rather for its lucrative
derivatives operations.
这年头，良好的股市不再是经济的晴雨表，这个从居高不下的下岗率就能看出。奶茶党
有一个说法是对的：华尔街的利好不一定是 P民街之福。德国人参与华尔街的大交易仅
仅是为了金融衍生这颗摇钱树。
The stock market is still huge, of course: the companies listed on American
exchanges are valued at more than $17 trillion, and they’re not going to
disappear in the foreseeable future.
But the glory days of publicly traded companies dominating the American
business landscape may be over. The number of companies listed on the major
domestic exchanges peaked in 1997 at more than 7,000, and it has been
falling ever since. It’s now down to about 4,000 companies, and given its
steep downward trend will surely continue to shrink.
Nor are the remaining stocks an obvious proxy for the health of the American
economy. Innovative American companies like Apple and Google may be worth
hundreds of billions of dollars, but most of them don’t pay dividends or
employ many Americans, and their shares are essentially speculative
investments for people making a bet on how we’re going to live in the
future.
......
n*x
4 楼
我的理解是quick selection只能handle有限集合，heap可以搞stream
【在 b*********e 的大作中提到】
: 请问：既然quick selection 理论上证明是linear，比heap selection快。那为什么
: top k 的问题都用heap 呢？
: 按理说应该用最快的quick selection啊。
【在 b*********e 的大作中提到】
: 请问：既然quick selection 理论上证明是linear，比heap selection快。那为什么
: top k 的问题都用heap 呢？
: 按理说应该用最快的quick selection啊。
p*5
5 楼
over 14 days
h*n
6 楼
巧了，我今天就被问了这个，我先用了heap然后让我写quick select没写出来
真丢人
【在 b*********e 的大作中提到】
: 请问：既然quick selection 理论上证明是linear，比heap selection快。那为什么
: top k 的问题都用heap 呢？
: 按理说应该用最快的quick selection啊。
真丢人
【在 b*********e 的大作中提到】
: 请问：既然quick selection 理论上证明是linear，比heap selection快。那为什么
: top k 的问题都用heap 呢？
: 按理说应该用最快的quick selection啊。
r*f
7 楼
8-9周都可以。。。
【在 w******n 的大作中提到】
: 8，9个的时候能做不？
【在 w******n 的大作中提到】
: 8，9个的时候能做不？
a*m
8 楼
硬写quick select?那不丢人吧。。。。
【在 h*********n 的大作中提到】
: 巧了，我今天就被问了这个，我先用了heap然后让我写quick select没写出来
: 真丢人
【在 h*********n 的大作中提到】
: 巧了，我今天就被问了这个，我先用了heap然后让我写quick select没写出来
: 真丢人
y*a
9 楼
理论上同是O(N),但用heap的结果似乎要快一点？没懂
【在 b*********e 的大作中提到】
: 请问：既然quick selection 理论上证明是linear，比heap selection快。那为什么
: top k 的问题都用heap 呢？
: 按理说应该用最快的quick selection啊。
【在 b*********e 的大作中提到】
: 请问：既然quick selection 理论上证明是linear，比heap selection快。那为什么
: top k 的问题都用heap 呢？
: 按理说应该用最快的quick selection啊。
L*s
10 楼
生背下来就好了…… 现场写容易搞错边界
【在 a********m 的大作中提到】
: 硬写quick select?那不丢人吧。。。。
【在 a********m 的大作中提到】
: 硬写quick select?那不丢人吧。。。。
L*s
11 楼
求 K-largest from N elements：
若用 MinHeap of size K，空间 O(K)，
时间：平均和最坏都是 O(N logK)，若要排序输出再加 O(K logK)。
若用 QuickSelect，空间 O(N)，
时间：平均O(N)，最坏O(N^2)，不用再排序，因为已经在最右端排好了。
如果 N 非常大，或者是不确定长度的流，当然还是用 heap。
若用 MinHeap of size K，空间 O(K)，
时间：平均和最坏都是 O(N logK)，若要排序输出再加 O(K logK)。
若用 QuickSelect，空间 O(N)，
时间：平均O(N)，最坏O(N^2)，不用再排序，因为已经在最右端排好了。
如果 N 非常大，或者是不确定长度的流，当然还是用 heap。
s*z
12 楼
用median of median的quickselect就是O(N)，不用平均
【在 L***s 的大作中提到】
: 求 K-largest from N elements：
: 若用 MinHeap of size K，空间 O(K)，
: 时间：平均和最坏都是 O(N logK)，若要排序输出再加 O(K logK)。
: 若用 QuickSelect，空间 O(N)，
: 时间：平均O(N)，最坏O(N^2)，不用再排序，因为已经在最右端排好了。
: 如果 N 非常大，或者是不确定长度的流，当然还是用 heap。
【在 L***s 的大作中提到】
: 求 K-largest from N elements：
: 若用 MinHeap of size K，空间 O(K)，
: 时间：平均和最坏都是 O(N logK)，若要排序输出再加 O(K logK)。
: 若用 QuickSelect，空间 O(N)，
: 时间：平均O(N)，最坏O(N^2)，不用再排序，因为已经在最右端排好了。
: 如果 N 非常大，或者是不确定长度的流，当然还是用 heap。
W*o
13 楼
quickselect 是 in-place的，咋还算空间 O(N) ? 难道是算input的那个array 空间？
【在 L***s 的大作中提到】
: 求 K-largest from N elements：
: 若用 MinHeap of size K，空间 O(K)，
: 时间：平均和最坏都是 O(N logK)，若要排序输出再加 O(K logK)。
: 若用 QuickSelect，空间 O(N)，
: 时间：平均O(N)，最坏O(N^2)，不用再排序，因为已经在最右端排好了。
: 如果 N 非常大，或者是不确定长度的流，当然还是用 heap。
【在 L***s 的大作中提到】
: 求 K-largest from N elements：
: 若用 MinHeap of size K，空间 O(K)，
: 时间：平均和最坏都是 O(N logK)，若要排序输出再加 O(K logK)。
: 若用 QuickSelect，空间 O(N)，
: 时间：平均O(N)，最坏O(N^2)，不用再排序，因为已经在最右端排好了。
: 如果 N 非常大，或者是不确定长度的流，当然还是用 heap。
m*c
14 楼
深入点，我会考怎么lock-free并行。
相关阅读