ISME J审稿咋这么慢啊 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Biology - 生物学

ISME J审稿咋这么慢啊

ISME J审稿咋这么慢啊# Biology - 生物学

g*u2014-01-17 08:01

1 楼

请问大家一个区间overlap的问题：
比如说我们有如下的区间：
[1, 5], [2, 6], [3, 7], [8, 10], [9, 11]
如果是判断是否有overlap的话，可以sort stating point, 然后用类似merge的方法
来确定是否有overlap( O(nlog n) )；
如何找到所有的overlap的区间呢？
用brute force就是O(n^2)的解法，有没有更快的呢？
谢谢

m*k2014-01-17 08:01

2 楼

这里有几个人为了自己快点拿卡，把老墨描述成了勤劳有高技术的高薪白领金领，老墨
交的税远超吃掉的福利，剩下的钱还给白人和亚裔提供了福利的来源。
来看看下面这个帖子。你们心目中的墨西哥劳动模范，为什么他们的老窝失业率这么高
呢？为什么他们不去发挥自己高级的技术来找个年薪10万的工作，而选择在家失业呢？
到底是老墨是高级技术人才，还是你们是虚伪可耻为了自己的蝇头小利可以做人无底线
的小人呢？
发信人: tmd001 (The Movie Depot), 信区: EB23
标题: 美国失业率最高的城市
发信站: BBS 未名空间站 (Mon Mar 18 20:53:24 2013, 美东)
美国失业率最高的城市排名榜，前四名如下，共同的特点是拥有大量的老墨。难道
是巧合？如果失业是因为这些城市没有工作机会，那为什么不到有工作机会的地方找
工作呢？还是根本就不想工作，宁愿吃福利呢？
Yuma, Ariz. 失业率 27.5% 墨墨占城市人口比例 54.8%
El Centro, Calif. 失业率 26.6% 墨墨占城市人口比例 81.6%
Yuba City, Calif. 失业率15.8% 墨墨占城市人口比例 28.4%
Merced, Calif. 失业率 15.7% 墨墨占城市人口比例 49.6%

p*r2014-01-17 08:01

3 楼

春蚕到死丝方尽，
秋瓜黄时受刀剜。

a*f2014-01-17 08:01

4 楼

Mickey
Coco
Mickey and Coco
Newcomer Kaka
Mickey and Kaka's toy
Who's butt

t*z2014-01-17 08:01

5 楼

我等投ISME J，投稿第二天就under review，都快两个月了还是under review，没有任
何消息。其间催问过，大约四十天的时候，他们说才找好了一个审稿人，正在找第二个
。我想这审稿审到何年何月啊？各位有没有在这杂志上投稿经验的说说，他们审稿一般
要多久呐？谢谢
-

i*e2014-01-17 08:01

6 楼

可以 define 一下所有 overlap 的区间吗？
好像你的例子，
答案应该是什么呢？

p*82014-01-17 08:01

7 楼

洗洗睡了

p*r2014-01-17 08:01

8 楼

7月中做的瓜，一直挂在藤上留种子。

t*e2014-01-17 08:01

9 楼

哈哈，肉肉的Kaka~

m*l2014-01-17 08:01

10 楼

why can't you just build the BST like:
1, 2, 3, 4, 5
then add, 2, 3, 4, 5, 6... etc
that way, you can find out overlaps by O(n)

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

: 请问大家一个区间overlap的问题：
: 比如说我们有如下的区间：
: [1, 5], [2, 6], [3, 7], [8, 10], [9, 11]
: 如果是判断是否有overlap的话，可以sort stating point, 然后用类似merge的方法
: 来确定是否有overlap( O(nlog n) )；
: 如何找到所有的overlap的区间呢？
: 用brute force就是O(n^2)的解法，有没有更快的呢？
: 谢谢

j*n2014-01-17 08:01

11 楼

洗洗睡了

f*c2014-01-17 08:01

12 楼

标题好吓人

a*a2014-01-17 08:01

13 楼

两团大毛球呀

i*e2014-01-17 08:01

14 楼

我看这题最理想的解法应该是用这个来储存 intervals.
http://en.wikipedia.org/wiki/Interval_tree

w*i2014-01-17 08:01

15 楼

Agree! 洗洗睡了!

p*r2014-01-17 08:01

16 楼

呵呵，效果达到了。O(∩_∩)O~

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

: 标题好吓人

s*d2014-01-17 08:01

17 楼

喜欢Mickey and Kaka's toy 的那张。是胶片拍的吧？

【在 a*f 的大作中提到】

: Mickey
: Coco
: Mickey and Coco
: Newcomer Kaka
: Mickey and Kaka's toy
: Who's butt

f*42014-01-17 08:01

18 楼

clrs上interval tree，找到一个有冲突了就停止了
可以模仿了寻找所有的冲突

【在 i**********e 的大作中提到】

: 我看这题最理想的解法应该是用这个来储存 intervals.
: http://en.wikipedia.org/wiki/Interval_tree

c*e2014-01-17 08:01

19 楼

也许是老墨把工作机会都占了?

【在 m***k 的大作中提到】

: 这里有几个人为了自己快点拿卡，把老墨描述成了勤劳有高技术的高薪白领金领，老墨
: 交的税远超吃掉的福利，剩下的钱还给白人和亚裔提供了福利的来源。
: 来看看下面这个帖子。你们心目中的墨西哥劳动模范，为什么他们的老窝失业率这么高
: 呢？为什么他们不去发挥自己高级的技术来找个年薪10万的工作，而选择在家失业呢？
: 到底是老墨是高级技术人才，还是你们是虚伪可耻为了自己的蝇头小利可以做人无底线
: 的小人呢？
: 发信人: tmd001 (The Movie Depot), 信区: EB23
: 标题: 美国失业率最高的城市
: 发信站: BBS 未名空间站 (Mon Mar 18 20:53:24 2013, 美东)
: 美国失业率最高的城市排名榜，前四名如下，共同的特点是拥有大量的老墨。难道

y*82014-01-17 08:01

20 楼

re
籽留到没有？

标题好吓人

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

: 标题好吓人

b*i2014-01-17 08:01

21 楼

Wow, all yours? Nice.
Good Luck.

【在 a*f 的大作中提到】

: Mickey
: Coco
: Mickey and Coco
: Newcomer Kaka
: Mickey and Kaka's toy
: Who's butt

d*l2014-01-17 08:01

22 楼

如果要统计两两overlap的总对数，那用线段树应该能O(nlogn)出来。如果要输出所有
，那只能O(n^2)了

F*r2014-01-17 08:01

23 楼

瞧这股子卑鄙劲...比红脖子还不如.

【在 m***k 的大作中提到】

s*02014-01-17 08:01

24 楼

这个还籽还没好吧？
看着水水的

i*e2014-01-17 08:01

25 楼

刚看了 clrs 的 interval tree 章节，里面有一个习题应该就是跟 LZ 的问题一样的：
Given an interval tree T and an interval i, describe how all intervals in T
that overlap i can be listed in O(min(n, k lg n)) time, where k is the
number of intervals in the output list.
难点在于找到了一个，有可能另一个在根节点另一边啊...
Edit:
给个例子：
[16,21]
/ \
[15,23] [22,23]
i = [22,23]
我要找所有与 i 产生冲突的 interval.
如果跟着 clrs 的方法只能找到 [15,23].
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 f****4 的大作中提到】

: clrs上interval tree，找到一个有冲突了就停止了
: 可以模仿了寻找所有的冲突

D*92014-01-17 08:01

26 楼

墨墨s are doing cash only job. They jobs 墨墨s are doing are not counting
into the employment calculated by US government.
墨墨s are doing low-pay job other Americans don't want to do.
Think about you can buy $2/pound green pepper now. If no 墨墨s, the price
could be double or triple.

p*y2014-01-17 08:01

27 楼

看那刀叉真有点恐怖

t*k2014-01-17 08:01

28 楼

Just sort all the starting points and ending points.
Then traverse the list in the increasing order:
if get a starting point, put the corresponding interval into a hash set, and
output all the intervals that start with this starting point and end with
the ending points of the intervals that are in the hash set;
if get an ending point, just remove the corresponding interval from the hash
set.
So the time complexity should be O(nlogn+m) where m is the number of
overlapped intervals? Btw, m could be n^2.

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

j*p2014-01-17 08:01

29 楼

LZ提醒我了，我还有两根老丝瓜挂在藤上呢，不知道能不能摘了。
怎么判断丝瓜可以留种了？

f*42014-01-17 08:01

30 楼

找到[15,23]之后找它的后继，一直到后继的start time大于23就可以停止了

的：
T

【在 i**********e 的大作中提到】

: 刚看了 clrs 的 interval tree 章节，里面有一个习题应该就是跟 LZ 的问题一样的：
: Given an interval tree T and an interval i, describe how all intervals in T
: that overlap i can be listed in O(min(n, k lg n)) time, where k is the
: number of intervals in the output list.
: 难点在于找到了一个，有可能另一个在根节点另一边啊...
: Edit:
: 给个例子：
: [16,21]
: / \
: [15,23] [22,23]

g*e2014-01-17 08:01

31 楼

表面枯干.

【在 j******p 的大作中提到】

: LZ提醒我了，我还有两根老丝瓜挂在藤上呢，不知道能不能摘了。
: 怎么判断丝瓜可以留种了？

m*q2014-01-17 08:01

32 楼

恩，最近刚看过interval tree，这个应该是对的。
复杂度是O(max(k, lgn)), k为和i有overlap的
节点数

【在 f****4 的大作中提到】

: 找到[15,23]之后找它的后继，一直到后继的start time大于23就可以停止了
:
: 的：
: T

m*q2014-01-17 08:01

33 楼

Seems this won't work...
The reason is the method only examines the intervals
already in the tree, but an interval could overlap with
the intervals after it.
[1, 2], [3, 10], [5, 7], [6, 9], [8, 12],..
For [5, 7], the overlaping intervals include [3, 10] and
[6, 9], while the proposed way only identifies the former...

and
hash

【在 t**k 的大作中提到】

: Just sort all the starting points and ending points.
: Then traverse the list in the increasing order:
: if get a starting point, put the corresponding interval into a hash set, and
: output all the intervals that start with this starting point and end with
: the ending points of the intervals that are in the hash set;
: if get an ending point, just remove the corresponding interval from the hash
: set.
: So the time complexity should be O(nlogn+m) where m is the number of
: overlapped intervals? Btw, m could be n^2.

t*k2014-01-17 08:01

34 楼

Why? In your example, the 2nd interval will be identified when we reach the
starting point 6.
Btw, there's no tree in my algorithm.

【在 m**q 的大作中提到】

: Seems this won't work...
: The reason is the method only examines the intervals
: already in the tree, but an interval could overlap with
: the intervals after it.
: [1, 2], [3, 10], [5, 7], [6, 9], [8, 12],..
: For [5, 7], the overlaping intervals include [3, 10] and
: [6, 9], while the proposed way only identifies the former...
:
: and
: hash

d*l2014-01-17 08:01

35 楼

想到如下方法：
1. 按区间起点排序
2. 离散化，总共不超过2n个端点，重新编号为0 - 2n-1
3. 遍历所有区间，对每个区间，计算(start, end)区间中起点的个数，累加到结果中
4. 单独计算起点重合的情况
离散化之后，可以用O(n)空间记录起点的分布，如果用O(n)预处理一下sum[i]，第三步
只需要O(1)时间。并且能处理区间端点不是整数的情况。只有第一步是O(nlogn)的，其
他都是O(n)。这样有什么bug吗？

s*y2014-01-17 08:01

36 楼

请问输出的overlap是不是不能够有overlap的
譬如 [1，5] 和[3，7] overlap [3，5]
[1，5] 和[2，6] overlap [2，5]
不能够输出 [2，5][3，5]
只能够输出[2，5]

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

g*u2014-01-17 08:01

37 楼

这个应该是可行的，但是我不确定是
max（k, lgn)
如果是ordinary BST的话，怎样返回下一个overlap的区间呢？
就是说寻找overlap的不是O(k)，是O(k*log n)么?

【在 m**q 的大作中提到】

: 恩，最近刚看过interval tree，这个应该是对的。
: 复杂度是O(max(k, lgn)), k为和i有overlap的
: 节点数

g*u2014-01-17 08:01

38 楼

不是的。
我重新编辑了例子

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

: 请问输出的overlap是不是不能够有overlap的
: 譬如 [1，5] 和[3，7] overlap [3，5]
: [1，5] 和[2，6] overlap [2，5]
: 不能够输出 [2，5][3，5]
: 只能够输出[2，5]

g*u2014-01-17 08:01

39 楼

那个interval tree保证了如果有interval的话，那么肯定可以找到。但怎样找回所有
的overlapped的区间呢？
大家提到的interval tree应该怎样建立？
每个节点存的是什么额外的信息？

【在 f****4 的大作中提到】

: clrs上interval tree，找到一个有冲突了就停止了
: 可以模仿了寻找所有的冲突

g*u2014-01-17 08:01

40 楼

可以解释一下第三步么？
假设有下面4个区间：
[1,10], [2,11],[3, 12],[4,13]
需要返回所有的overlap的区间pairs
如何返回：
([1,10],[2,11]);
([1,10],[3,12]);
([1,10],[4,13]);
([2,11],[3,12]);
([2,11],[4,13]);
([3,12],[4,13]);

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

: 想到如下方法：
: 1. 按区间起点排序
: 2. 离散化，总共不超过2n个端点，重新编号为0 - 2n-1
: 3. 遍历所有区间，对每个区间，计算(start, end)区间中起点的个数，累加到结果中
: 4. 单独计算起点重合的情况
: 离散化之后，可以用O(n)空间记录起点的分布，如果用O(n)预处理一下sum[i]，第三步
: 只需要O(1)时间。并且能处理区间端点不是整数的情况。只有第一步是O(nlogn)的，其
: 他都是O(n)。这样有什么bug吗？

d*l2014-01-17 08:01

41 楼

如果要输出所有的pairs，那没有什么好办法，因为这样的pairs最多有O(n^2)个，我们
不可能做的比这个更好。直接排序之后，每个区间往后找就行了，再精巧的方法也不会
从本质上降低复杂度。
我说的是计算overlap pairs数目的方法。这个是可以O(nlogn)时间计算出来的。

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

:
: 可以解释一下第三步么？
: 假设有下面4个区间：
: [1,10], [2,11],[3, 12],[4,13]
: 需要返回所有的overlap的区间pairs
: 如何返回：
: ([1,10],[2,11]);
: ([1,10],[3,12]);
: ([1,10],[4,13]);
: ([2,11],[3,12]);

g*u2014-01-17 08:01

42 楼

恩，又想了想，还有些没明白：
在计算数目的时候，通过计算在每个值左侧的开始的点的个数来确定么？比如说
左边只有1个starting point，就是0个overlap；
左边2个starting pt，就是1个overlap；
类似的3个，就是3个overlap；
n个，就是n*(n-1)/2；
如果开始遇到ending point的话，怎样处理？如果下个是starting point的话，总共
overlap的个数怎么算？
关键是遇到一个overlap后，我们不知道对应的starting point...
好像不容易计算这个个数

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

: 如果要输出所有的pairs，那没有什么好办法，因为这样的pairs最多有O(n^2)个，我们
: 不可能做的比这个更好。直接排序之后，每个区间往后找就行了，再精巧的方法也不会
: 从本质上降低复杂度。
: 我说的是计算overlap pairs数目的方法。这个是可以O(nlogn)时间计算出来的。

d*l2014-01-17 08:01

43 楼

计算每个区间上开始点的个数，还是用这个例子：
[1, 5], [2, 6], [3, 7], [8, 10], [9, 11]
这个已经排序了。开始点一共5个，分别是1，2，3，8，9。
[1, 5] -> 2,3 共两个
[2, 6] -> 3 一个
[3, 7] -> 0个
[8, 10] -> 9 一个
[9, 11] -> 0个
总共就4对overlap。其中计算某个区间按上开始点的个数可以O(1)做到，就是离散化之
后用O(n)的数组，对每个开始点对数组相应的位置计数加一，然后求出sum[i]，这样每
个区间(a, b）上开始点的数目就是sum[b-1]-sum[a]。所以总得复杂度就是排序的复杂
度。我得想法是两个区间overlap的充要条件就是其中一个的开始点位于另一个区间的
内部，不知道这么想有没有什么漏洞。上面的方法要单独处理下开始点重合的那些区间。

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

:
: 恩，又想了想，还有些没明白：
: 在计算数目的时候，通过计算在每个值左侧的开始的点的个数来确定么？比如说
: 左边只有1个starting point，就是0个overlap；
: 左边2个starting pt，就是1个overlap；
: 类似的3个，就是3个overlap；
: n个，就是n*(n-1)/2；
: 如果开始遇到ending point的话，怎样处理？如果下个是starting point的话，总共
: overlap的个数怎么算？
: 关键是遇到一个overlap后，我们不知道对应的starting point...

s*x2014-01-17 08:01

44 楼

at the end of that excise, it says "optional: find a solution without
modifying the tree". so I think it is easier to modify the interval tree.
1) use the search method mentioned in the book to find an interval.
2) once you find an internal, delete that node from the tree
3) continue 1) and 2) until nothing is found.
hence we have O(min(n, klgn)) complexity, since you can not delete more than
n internal, and 1) is logn.

的：
T

【在 i**********e 的大作中提到】

m*q2014-01-17 08:01

45 楼

CLRS, 2nd
12.2-8 是可以证明的
实际上就是连续调用successor直到当前
node和给定的range没有overlap，假设
调用successor次数为k，则复杂度是O(k+lgn)

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

m*q2014-01-17 08:01

46 楼

Yes your solution should work..
I misunderstood the original question.

the

【在 t**k 的大作中提到】

: Why? In your example, the 2nd interval will be identified when we reach the
: starting point 6.
: Btw, there's no tree in my algorithm.

m*q2014-01-17 08:01

47 楼

这个思路不错。
感觉应该需要一些额外空间来记录start[]和end[]两个数组元素的对应关系，不过额外
空间也是O(n)的。
重复起点的问题可以在O(n)时间解决，最后扫一遍数组，减掉重复计算的值就行了。
ps:另外一种统计个数的方法是对每个区间二分查找，不用额外空间，不过就是O(nlgn)了

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

: 计算每个区间上开始点的个数，还是用这个例子：
: [1, 5], [2, 6], [3, 7], [8, 10], [9, 11]
: 这个已经排序了。开始点一共5个，分别是1，2，3，8，9。
: [1, 5] -> 2,3 共两个
: [2, 6] -> 3 一个
: [3, 7] -> 0个
: [8, 10] -> 9 一个
: [9, 11] -> 0个
: 总共就4对overlap。其中计算某个区间按上开始点的个数可以O(1)做到，就是离散化之
: 后用O(n)的数组，对每个开始点对数组相应的位置计数加一，然后求出sum[i]，这样每

d*l2014-01-17 08:01

48 楼

嗯，不过需要先排序所以还是O(nlogn)。上面讨论的区间树我有点记不清具体内容了，
但感觉如果建树再对每个区间查找所有overlap的区间，应该也不会好于O(nlogn)了吧
。不知有没有本质上更好的办法

nlgn)了

【在 m**q 的大作中提到】

: 这个思路不错。
: 感觉应该需要一些额外空间来记录start[]和end[]两个数组元素的对应关系，不过额外
: 空间也是O(n)的。
: 重复起点的问题可以在O(n)时间解决，最后扫一遍数组，减掉重复计算的值就行了。
: ps:另外一种统计个数的方法是对每个区间二分查找，不用额外空间，不过就是O(nlgn)了

s*y2014-01-17 08:01

49 楼

During the interview, how could we implenment this interval tree as it seems
belong to red-black tree.
Yous is much simpler and easier to understand.

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

: 嗯，不过需要先排序所以还是O(nlogn)。上面讨论的区间树我有点记不清具体内容了，
: 但感觉如果建树再对每个区间查找所有overlap的区间，应该也不会好于O(nlogn)了吧
: 。不知有没有本质上更好的办法
:
: nlgn)了

f*42014-01-17 08:01

50 楼

你写白板的时候可以假设interview tree的insert，delete等函数已经有了，调用函数
即可

seems

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

: During the interview, how could we implenment this interval tree as it seems
: belong to red-black tree.
: Yous is much simpler and easier to understand.

g*u2014-01-17 08:01

51 楼

恩，这个很好理解，谢谢了。
如果要返回所有的overlap的区间的pair的话，可不可以直接这样：
对按起点排好序之后的区间，对每个区间，用binary search寻找在它后面所有与之
overlap的区间。
我们有n个区间，每个区间寻找overlap的区间是 log n, 排序的复杂度是 nlog n，所
以总的复杂度依然是 o(nlogn).
不用interval tree 也可以做到。
但是如果我们有stream of intervals的话， interval tree估计派上用场了。

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

d*l2014-01-17 08:01

52 楼

应该可以，这样不用额外的处理也不用额外的空间，复杂度也不会增大。如果要支持动
态的更新，那用区间树可能更好

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

:
: 恩，这个很好理解，谢谢了。
: 如果要返回所有的overlap的区间的pair的话，可不可以直接这样：
: 对按起点排好序之后的区间，对每个区间，用binary search寻找在它后面所有与之
: overlap的区间。
: 我们有n个区间，每个区间寻找overlap的区间是 log n, 排序的复杂度是 nlog n，所
: 以总的复杂度依然是 o(nlogn).
: 不用interval tree 也可以做到。
: 但是如果我们有stream of intervals的话， interval tree估计派上用场了。

F*r2014-01-17 08:01

53 楼

弱问每个区间怎么二分查找？

nlgn)了

【在 m**q 的大作中提到】

d*l2014-01-17 08:01

54 楼

应该指的是对每个区间，在它后面二分查找第一个不被它覆盖的区间，也就是开始点大
于它结束点的第一个区间

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

: 弱问每个区间怎么二分查找？
:
: nlgn)了

F*r2014-01-17 08:01

55 楼

多谢！

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

: 应该指的是对每个区间，在它后面二分查找第一个不被它覆盖的区间，也就是开始点大
: 于它结束点的第一个区间

z*62014-01-17 08:01

56 楼

[1, 5], [2, 6], [3, 7], [8, 10], [9, 11]
[1, 5]
\
[2, 5, 6]
\
[3, 6，7 ]
\
[8, 10]
\
[9,10,11]
三个位置，左边，中间，右边。
左边不用管，右边不用管，中间的话，
如果5 <6, 把5加到[2,6]里，成[2,5,6],一次类推。。