中國過渡政府總統伍凡 2012年新年賀詞 (转载) - 未名空间MITBBS历史存档

中國過渡政府總統伍凡 2012年新年賀詞 (转载)# Joke - 肚皮舞运动

d*u2012-01-01 08:01

1 楼

这题以前板上应该讨论过，搜了一下没找到link
这题的变体就是那个找离地球最近的stars。。。
我能想到的就是build一个max heap，里面包含k个离原点最近的点
每读一个新的点，跟root比，比root小就加到heap里面，把root删掉，调整heap。
这个的时间复杂度是 O(nlgk), space是O(k)
请问还有别的方法吗?

z*n2012-01-01 08:01

2 楼

【以下文字转载自 Military 讨论区】
发信人: meiguohuaren (唐骏博士), 信区: Military
标题: 中國過渡政府總統伍凡 2012年新年賀詞
发信站: BBS 未名空间站 (Sun Jan 1 15:22:53 2012, 美东)

z*82012-01-01 08:01

3 楼

应该只有这个了

【在 d******u 的大作中提到】

: 这题以前板上应该讨论过，搜了一下没找到link
: 这题的变体就是那个找离地球最近的stars。。。
: 我能想到的就是build一个max heap，里面包含k个离原点最近的点
: 每读一个新的点，跟root比，比root小就加到heap里面，把root删掉，调整heap。
: 这个的时间复杂度是 O(nlgk), space是O(k)
: 请问还有别的方法吗?

l*t2012-01-01 08:01

4 楼

不专业, 背后应该是一个书架放满了书, 还有一面旗子. 过渡政府的旗子是什么?

c*r2012-01-01 08:01

5 楼

基本上好像就这个思路，但是有个叫k-d tree的是解决general case的。但是这个k-d
tree比较偏门了。还有就是在计算距离的时候乘法会比较消耗时间，可以考虑做圆
的外接正方形的思路，缩小范围以后再提取k个点。
这个是我以前遇到过的问题，也不知道对不对，面试官是比较肯定的。

o*12012-01-01 08:01

6 楼

轮子有一点说的没错，中国处在大变革的前夜，中国的经济和政治，都将在这场大变
革中面目全非。。。

【在 z**n 的大作中提到】

: 【以下文字转载自 Military 讨论区】
: 发信人: meiguohuaren (唐骏博士), 信区: Military
: 标题: 中國過渡政府總統伍凡 2012年新年賀詞
: 发信站: BBS 未名空间站 (Sun Jan 1 15:22:53 2012, 美东)

w*o2012-01-01 08:01

7 楼

“还有就是在计算距离的时候乘法会比较消耗时间，可以考虑做圆
的外接正方形的思路，缩小范围以后再提取k个点。”
clouder,
能否在详细的讲讲你的方法？这些百万个3d的点，是如何存储的？如何组织的？是放在
一个数组里吗？
谢谢！

d

【在 c*****r 的大作中提到】

: 基本上好像就这个思路，但是有个叫k-d tree的是解决general case的。但是这个k-d
: tree比较偏门了。还有就是在计算距离的时候乘法会比较消耗时间，可以考虑做圆
: 的外接正方形的思路，缩小范围以后再提取k个点。
: 这个是我以前遇到过的问题，也不知道对不对，面试官是比较肯定的。

w*p2012-01-01 08:01

8 楼

关键问题是这一晚上有多长，章老师已经做了第二次预测了

【在 o******1 的大作中提到】

: 轮子有一点说的没错，中国处在大变革的前夜，中国的经济和政治，都将在这场大变
: 革中面目全非。。。

z*c2012-01-01 08:01

9 楼

那快速选择算法呢？
算出距离以后，按照快排的思想选取pivot划分成左集合和右集合，如果左集合大于k，
那么只用对左集合选取前k个就行，否则左集合都属于k个点，然后对右集合选取距离最
小的k - size(左集合)

【在 d******u 的大作中提到】

: 这题以前板上应该讨论过，搜了一下没找到link
: 这题的变体就是那个找离地球最近的stars。。。
: 我能想到的就是build一个max heap，里面包含k个离原点最近的点
: 每读一个新的点，跟root比，比root小就加到heap里面，把root删掉，调整heap。
: 这个的时间复杂度是 O(nlgk), space是O(k)
: 请问还有别的方法吗?

s*a2012-01-01 08:01

10 楼

哪儿就冒出来一个总统，太搞笑了，比中共还搞笑。

【在 z**n 的大作中提到】

: 【以下文字转载自 Military 讨论区】
: 发信人: meiguohuaren (唐骏博士), 信区: Military
: 标题: 中國過渡政府總統伍凡 2012年新年賀詞
: 发信站: BBS 未名空间站 (Sun Jan 1 15:22:53 2012, 美东)

d*u2012-01-01 08:01

11 楼

这个优化的idea不错，但是，如果以圆的外界正方形为判断标准的话，返回k个点就不
够了，因为会有一些点落在正方形里面，圆形外面
这时候可以按照圆和正方形的面积比取多一些点，但还是不能保证，一次能找到k个点

d

【在 c*****r 的大作中提到】

: 基本上好像就这个思路，但是有个叫k-d tree的是解决general case的。但是这个k-d
: tree比较偏门了。还有就是在计算距离的时候乘法会比较消耗时间，可以考虑做圆
: 的外接正方形的思路，缩小范围以后再提取k个点。
: 这个是我以前遇到过的问题，也不知道对不对，面试官是比较肯定的。

h*82012-01-01 08:01

12 楼

＂總統＂嘴角的俩肉疙瘩是肿么回事？大法练到几成才有捏？

【在 z**n 的大作中提到】

: 【以下文字转载自 Military 讨论区】
: 发信人: meiguohuaren (唐骏博士), 信区: Military
: 标题: 中國過渡政府總統伍凡 2012年新年賀詞
: 发信站: BBS 未名空间站 (Sun Jan 1 15:22:53 2012, 美东)

d*u2012-01-01 08:01

13 楼

这个方法不错，时间复杂度是O(n)，但空间呢。。。如果所有数不能同时load进内存的话

【在 z********c 的大作中提到】

: 那快速选择算法呢？
: 算出距离以后，按照快排的思想选取pivot划分成左集合和右集合，如果左集合大于k，
: 那么只用对左集合选取前k个就行，否则左集合都属于k个点，然后对右集合选取距离最
: 小的k - size(左集合)

c*r2012-01-01 08:01

14 楼

百万个点的数据结构，我当时遇到的时候被告知不用担心。就当作是streaming进来的
一个个点的坐标。或者说是一个个读取object。
另外，我遇到的二维的情况，所以可以认为接收到的object是（ x, y）. 然后距离计
算距离的时候就需要（x^2 + y^2）.面试官说是否可以再快一点，这么多点计算乘法很
慢。然后又说假设k很小。
我就说了用 2(|x| + |Y|)作为判断距离大小的标准，这样就只需要做位的左移操作和
绝对值操作了。有一定概率会发生错误但是既然k很小，又有百万个点。这个概率是很
小的。这样下来我们找到所有在这个 2(|x| + |Y|)以内的点以后，如果大于k个，再
通过（x^2 + y^2）求最近的点。大概就这个思路。当时面试官好像是肯定了这个想法
的。
不过如果你的面试官没有说可以忽略一定的概率，这个方法可能不行哦。

【在 w****o 的大作中提到】

: “还有就是在计算距离的时候乘法会比较消耗时间，可以考虑做圆
: 的外接正方形的思路，缩小范围以后再提取k个点。”
: clouder,
: 能否在详细的讲讲你的方法？这些百万个3d的点，是如何存储的？如何组织的？是放在
: 一个数组里吗？
: 谢谢！
:
: d

s*d2012-01-01 08:01

15 楼

K-d tree 和 NNS 基本上能解决
反正俺是被amazon问倒了。

c*r2012-01-01 08:01

16 楼

小弟也是amazon 问到的

【在 s*********d 的大作中提到】

: K-d tree 和 NNS 基本上能解决
: 反正俺是被amazon问倒了。

w*o2012-01-01 08:01

17 楼

什么是 k-d tree?
是不是如果是一维的点的话，就不用这些优化了，直接用首贴的LZ的max_heap方法就行
了？

【在 s*********d 的大作中提到】

: K-d tree 和 NNS 基本上能解决
: 反正俺是被amazon问倒了。

w*o2012-01-01 08:01

18 楼

这个快速选择的方法的复杂度怎么是 O(n)呢？

的话

【在 d******u 的大作中提到】

: 这个方法不错，时间复杂度是O(n)，但空间呢。。。如果所有数不能同时load进内存的话

d*u2012-01-01 08:01

19 楼

这题以前板上应该讨论过，搜了一下没找到link
这题的变体就是那个找离地球最近的stars。。。
我能想到的就是build一个max heap，里面包含k个离原点最近的点
每读一个新的点，跟root比，比root小就加到heap里面，把root删掉，调整heap。
这个的时间复杂度是 O(nlgk), space是O(k)
请问还有别的方法吗?

z*82012-01-01 08:01

20 楼

应该只有这个了

【在 d******u 的大作中提到】

: 这题以前板上应该讨论过，搜了一下没找到link
: 这题的变体就是那个找离地球最近的stars。。。
: 我能想到的就是build一个max heap，里面包含k个离原点最近的点
: 每读一个新的点，跟root比，比root小就加到heap里面，把root删掉，调整heap。
: 这个的时间复杂度是 O(nlgk), space是O(k)
: 请问还有别的方法吗?

c*r2012-01-01 08:01

21 楼

基本上好像就这个思路，但是有个叫k-d tree的是解决general case的。但是这个k-d
tree比较偏门了。还有就是在计算距离的时候乘法会比较消耗时间，可以考虑做圆
的外接正方形的思路，缩小范围以后再提取k个点。
这个是我以前遇到过的问题，也不知道对不对，面试官是比较肯定的。

w*o2012-01-01 08:01

22 楼

“还有就是在计算距离的时候乘法会比较消耗时间，可以考虑做圆
的外接正方形的思路，缩小范围以后再提取k个点。”
clouder,
能否在详细的讲讲你的方法？这些百万个3d的点，是如何存储的？如何组织的？是放在
一个数组里吗？
谢谢！

d

【在 c*****r 的大作中提到】

: 基本上好像就这个思路，但是有个叫k-d tree的是解决general case的。但是这个k-d
: tree比较偏门了。还有就是在计算距离的时候乘法会比较消耗时间，可以考虑做圆
: 的外接正方形的思路，缩小范围以后再提取k个点。
: 这个是我以前遇到过的问题，也不知道对不对，面试官是比较肯定的。

z*c2012-01-01 08:01

23 楼

那快速选择算法呢？
算出距离以后，按照快排的思想选取pivot划分成左集合和右集合，如果左集合大于k，
那么只用对左集合选取前k个就行，否则左集合都属于k个点，然后对右集合选取距离最
小的k - size(左集合)

【在 d******u 的大作中提到】

: 这题以前板上应该讨论过，搜了一下没找到link
: 这题的变体就是那个找离地球最近的stars。。。
: 我能想到的就是build一个max heap，里面包含k个离原点最近的点
: 每读一个新的点，跟root比，比root小就加到heap里面，把root删掉，调整heap。
: 这个的时间复杂度是 O(nlgk), space是O(k)
: 请问还有别的方法吗?

d*u2012-01-01 08:01

24 楼

这个优化的idea不错，但是，如果以圆的外界正方形为判断标准的话，返回k个点就不
够了，因为会有一些点落在正方形里面，圆形外面
这时候可以按照圆和正方形的面积比取多一些点，但还是不能保证，一次能找到k个点

d

【在 c*****r 的大作中提到】

: 基本上好像就这个思路，但是有个叫k-d tree的是解决general case的。但是这个k-d
: tree比较偏门了。还有就是在计算距离的时候乘法会比较消耗时间，可以考虑做圆
: 的外接正方形的思路，缩小范围以后再提取k个点。
: 这个是我以前遇到过的问题，也不知道对不对，面试官是比较肯定的。

d*u2012-01-01 08:01

25 楼

这个方法不错，时间复杂度是O(n)，但空间呢。。。如果所有数不能同时load进内存的话

【在 z********c 的大作中提到】

: 那快速选择算法呢？
: 算出距离以后，按照快排的思想选取pivot划分成左集合和右集合，如果左集合大于k，
: 那么只用对左集合选取前k个就行，否则左集合都属于k个点，然后对右集合选取距离最
: 小的k - size(左集合)

c*r2012-01-01 08:01

26 楼

百万个点的数据结构，我当时遇到的时候被告知不用担心。就当作是streaming进来的
一个个点的坐标。或者说是一个个读取object。
另外，我遇到的二维的情况，所以可以认为接收到的object是（ x, y）. 然后距离计
算距离的时候就需要（x^2 + y^2）.面试官说是否可以再快一点，这么多点计算乘法很
慢。然后又说假设k很小。
我就说了用 2(|x| + |Y|)作为判断距离大小的标准，这样就只需要做位的左移操作和
绝对值操作了。有一定概率会发生错误但是既然k很小，又有百万个点。这个概率是很
小的。这样下来我们找到所有在这个 2(|x| + |Y|)以内的点以后，如果大于k个，再
通过（x^2 + y^2）求最近的点。大概就这个思路。当时面试官好像是肯定了这个想法
的。
不过如果你的面试官没有说可以忽略一定的概率，这个方法可能不行哦。

【在 w****o 的大作中提到】

: “还有就是在计算距离的时候乘法会比较消耗时间，可以考虑做圆
: 的外接正方形的思路，缩小范围以后再提取k个点。”
: clouder,
: 能否在详细的讲讲你的方法？这些百万个3d的点，是如何存储的？如何组织的？是放在
: 一个数组里吗？
: 谢谢！
:
: d

s*d2012-01-01 08:01

27 楼

K-d tree 和 NNS 基本上能解决
反正俺是被amazon问倒了。

c*r2012-01-01 08:01

28 楼

小弟也是amazon 问到的

【在 s*********d 的大作中提到】

: K-d tree 和 NNS 基本上能解决
: 反正俺是被amazon问倒了。

w*o2012-01-01 08:01

29 楼

什么是 k-d tree?
是不是如果是一维的点的话，就不用这些优化了，直接用首贴的LZ的max_heap方法就行
了？

【在 s*********d 的大作中提到】

: K-d tree 和 NNS 基本上能解决
: 反正俺是被amazon问倒了。

w*o2012-01-01 08:01

30 楼

这个快速选择的方法的复杂度怎么是 O(n)呢？

的话

【在 d******u 的大作中提到】

: 这个方法不错，时间复杂度是O(n)，但空间呢。。。如果所有数不能同时load进内存的话

b*72012-01-01 08:01

31 楼

因为递归式平均情况是T(n) = T(n/2) + O(n)，所以是O（n)
参见算法导论第9章select k问题，随机划分平均性能O（n），精细划分最坏情况O（n）

【在 w****o 的大作中提到】

: 这个快速选择的方法的复杂度怎么是 O(n)呢？
:
: 的话

b*72012-01-01 08:01

32 楼

1、建k最大堆时同时计算该堆所有点所在的外接矩形，{max(x)，max(y)}
2、后续n-k点每次通过比较是否落入矩形，若落入矩形内才计算距离并与堆顶元素比较
，若入堆，根据改点维护外接矩形
应该没有什么概率问题

【在 c*****r 的大作中提到】

: 百万个点的数据结构，我当时遇到的时候被告知不用担心。就当作是streaming进来的
: 一个个点的坐标。或者说是一个个读取object。
: 另外，我遇到的二维的情况，所以可以认为接收到的object是（ x, y）. 然后距离计
: 算距离的时候就需要（x^2 + y^2）.面试官说是否可以再快一点，这么多点计算乘法很
: 慢。然后又说假设k很小。
: 我就说了用 2(|x| + |Y|)作为判断距离大小的标准，这样就只需要做位的左移操作和
: 绝对值操作了。有一定概率会发生错误但是既然k很小，又有百万个点。这个概率是很
: 小的。这样下来我们找到所有在这个 2(|x| + |Y|)以内的点以后，如果大于k个，再
: 通过（x^2 + y^2）求最近的点。大概就这个思路。当时面试官好像是肯定了这个想法
: 的。

d*x2012-01-01 08:01

33 楼

上次讨论过这个kd-tree
这东西适合多次查询
只算一次的话就quick selection

d

【在 c*****r 的大作中提到】

: 基本上好像就这个思路，但是有个叫k-d tree的是解决general case的。但是这个k-d
: tree比较偏门了。还有就是在计算距离的时候乘法会比较消耗时间，可以考虑做圆
: 的外接正方形的思路，缩小范围以后再提取k个点。
: 这个是我以前遇到过的问题，也不知道对不对，面试官是比较肯定的。

j*n2012-01-01 08:01

34 楼

你要知道 k-d tree 或者 ball-tree, metric-tree 就可以提一提。不会让你实现的。

b*72012-01-01 08:01

35 楼

因为递归式平均情况是T(n) = T(n/2) + O(n)，所以是O（n)
参见算法导论第9章select k问题，随机划分平均性能O（n），精细划分最坏情况O（n）

【在 w****o 的大作中提到】

: 这个快速选择的方法的复杂度怎么是 O(n)呢？
:
: 的话

b*72012-01-01 08:01

36 楼

1、建k最大堆时同时计算该堆所有点所在的外接矩形，{max(x)，max(y)}
2、后续n-k点每次通过比较是否落入矩形，若落入矩形内才计算距离并与堆顶元素比较
，若入堆，根据改点维护外接矩形
应该没有什么概率问题

【在 c*****r 的大作中提到】

: 百万个点的数据结构，我当时遇到的时候被告知不用担心。就当作是streaming进来的
: 一个个点的坐标。或者说是一个个读取object。
: 另外，我遇到的二维的情况，所以可以认为接收到的object是（ x, y）. 然后距离计
: 算距离的时候就需要（x^2 + y^2）.面试官说是否可以再快一点，这么多点计算乘法很
: 慢。然后又说假设k很小。
: 我就说了用 2(|x| + |Y|)作为判断距离大小的标准，这样就只需要做位的左移操作和
: 绝对值操作了。有一定概率会发生错误但是既然k很小，又有百万个点。这个概率是很
: 小的。这样下来我们找到所有在这个 2(|x| + |Y|)以内的点以后，如果大于k个，再
: 通过（x^2 + y^2）求最近的点。大概就这个思路。当时面试官好像是肯定了这个想法
: 的。

d*x2012-01-01 08:01

37 楼

上次讨论过这个kd-tree
这东西适合多次查询
只算一次的话就quick selection

d

【在 c*****r 的大作中提到】

: 基本上好像就这个思路，但是有个叫k-d tree的是解决general case的。但是这个k-d
: tree比较偏门了。还有就是在计算距离的时候乘法会比较消耗时间，可以考虑做圆
: 的外接正方形的思路，缩小范围以后再提取k个点。
: 这个是我以前遇到过的问题，也不知道对不对，面试官是比较肯定的。

j*n2012-01-01 08:01

38 楼

你要知道 k-d tree 或者 ball-tree, metric-tree 就可以提一提。不会让你实现的。

s*n2012-01-01 08:01

39 楼

开始随机取k点，加入heap.建立bounding box. MBB(k)
性质：MBB（k) monotonically shrinks.
filering: if p(k) is not in MBB(k), discard.
这个计算会越来越快。因为MBB越来越小。
什么组，要考spatial index方面的知识？

【在 c*****r 的大作中提到】

: 百万个点的数据结构，我当时遇到的时候被告知不用担心。就当作是streaming进来的
: 一个个点的坐标。或者说是一个个读取object。
: 另外，我遇到的二维的情况，所以可以认为接收到的object是（ x, y）. 然后距离计
: 算距离的时候就需要（x^2 + y^2）.面试官说是否可以再快一点，这么多点计算乘法很
: 慢。然后又说假设k很小。
: 我就说了用 2(|x| + |Y|)作为判断距离大小的标准，这样就只需要做位的左移操作和
: 绝对值操作了。有一定概率会发生错误但是既然k很小，又有百万个点。这个概率是很
: 小的。这样下来我们找到所有在这个 2(|x| + |Y|)以内的点以后，如果大于k个，再
: 通过（x^2 + y^2）求最近的点。大概就这个思路。当时面试官好像是肯定了这个想法
: 的。

a*32012-01-01 08:01

40 楼

如果k很小，常数级别，或者k很大，跟n的差值是常数级别，都可以用最大，最小堆来
做吧
如果k跟n较接近，如n/2，感觉还是用partition的方法比较好
本题不适合多次查询，或者多次查询k近邻，所以感觉kd-tree之类的index不太合适，
复杂度偏高。

d*g2012-01-01 08:01

41 楼

为什么2(|x| + |Y|)而不是(|x| + |Y|)？应该没区别吧？

【在 c*****r 的大作中提到】

: 百万个点的数据结构，我当时遇到的时候被告知不用担心。就当作是streaming进来的
: 一个个点的坐标。或者说是一个个读取object。
: 另外，我遇到的二维的情况，所以可以认为接收到的object是（ x, y）. 然后距离计
: 算距离的时候就需要（x^2 + y^2）.面试官说是否可以再快一点，这么多点计算乘法很
: 慢。然后又说假设k很小。
: 我就说了用 2(|x| + |Y|)作为判断距离大小的标准，这样就只需要做位的左移操作和
: 绝对值操作了。有一定概率会发生错误但是既然k很小，又有百万个点。这个概率是很
: 小的。这样下来我们找到所有在这个 2(|x| + |Y|)以内的点以后，如果大于k个，再
: 通过（x^2 + y^2）求最近的点。大概就这个思路。当时面试官好像是肯定了这个想法
: 的。

a*32012-01-01 08:01

42 楼

streaming方式的话用heap吧，把在heap中的的点的最小x,y，最大x,y都保存，这四个
值可以构成一个矩形，在这个矩形之外的点直接filter，在矩形里面的才计算然后跟
heap top的元素比较

a*m2012-01-01 08:01

43 楼

选择算法需要交换，输入是流的话不太合适。