reviewer needed - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Biology - 生物学

reviewer needed

reviewer needed# Biology - 生物学

m*n2017-11-02 07:11

1 楼

find out K most frequent numbers from incoming streams of numbers on the fly
我的方法是保存一个hashtable
value---->(int frequency, boolean inHeap)
每一个值，都保存一个频率和是否在heap上
一个MIN Heap, Heap上保存value,frequency, 但只比较frequency
大家还有更好办法么？

y*m2017-11-02 07:11

2 楼

投稿需要reviewers，如果有兴趣的老师或者同仁请和我联系。肝炎病毒方面的。
谢谢

l*82017-11-02 07:11

3 楼

frequency是从steam开始的时候累计计数吗？还是有一个time window？

fly

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

: find out K most frequent numbers from incoming streams of numbers on the fly
: 我的方法是保存一个hashtable
: value---->(int frequency, boolean inHeap)
: 每一个值，都保存一个频率和是否在heap上
: 一个MIN Heap, Heap上保存value,frequency, 但只比较frequency
: 大家还有更好办法么？

d*u2017-11-02 07:11

4 楼

私信我吧

m*n2017-11-02 07:11

5 楼

开始时计数啊。

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

: frequency是从steam开始的时候累计计数吗？还是有一个time window？
:
: fly

p*22017-11-02 07:11

6 楼

Hashtable stores frequency.
For each coming number, add it and frequency into max heap.

l*82017-11-02 07:11

7 楼

我觉得像马兰说的， hashtable还需要保存IsInHeap的flag。不然heap里面怎么避免
duplicated item?

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

: Hashtable stores frequency.
: For each coming number, add it and frequency into max heap.

m*n2017-11-02 07:11

8 楼

显然是min heap, 只保存K 最大的。
来一个新的数，只有4种可能：
1. 不在min heap里面，而且frequency 小于 top of the min heap
2. 不在min heap里面，frequncy 大于top of the min heap
3. 在min heap里面，但不是最小的
4. 在min heap里面，是最小的

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

: Hashtable stores frequency.
: For each coming number, add it and frequency into max heap.

h*l2017-11-02 07:11

9 楼

你存这个inheap显然不好，你还要往heap里面加过来后才能回来update这个flag
之用保存一个 min，然后直接看是不是在heap里面就好了

fly

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

l*82017-11-02 07:11

10 楼

是minheap, 因为要插入新的frequent item into the heap的时候，要删除的是原来
heap里面最不frequent的item.

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

: 显然是min heap, 只保存K 最大的。
: 来一个新的数，只有4种可能：
: 1. 不在min heap里面，而且frequency 小于 top of the min heap
: 2. 不在min heap里面，frequncy 大于top of the min heap
: 3. 在min heap里面，但不是最小的
: 4. 在min heap里面，是最小的

p*22017-11-02 07:11

11 楼

有duplicate无所谓。只加不删除。删除的话performance可就受影响了。

p*22017-11-02 07:11

12 楼

if(!ht.containsKey(n))
ht.put(n,0);
ht.put(n, ht.get(n)+1);
maxheap.add(new Freq(n, ht.get(n)); 就可以了。

h*l2017-11-02 07:11

13 楼

worse case你的heap太大了把，所有的东西都要加进去
当然这个具体可以优化

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

: 有duplicate无所谓。只加不删除。删除的话performance可就受影响了。

p*22017-11-02 07:11

14 楼

这情况我碰到几次了。都这么做的。删除的perf不行，过不了test case。

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

: worse case你的heap太大了把，所有的东西都要加进去
: 当然这个具体可以优化

m*n2017-11-02 07:11

15 楼

如果要删除的话，要用BST .

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

:
: 这情况我碰到几次了。都这么做的。删除的perf不行，过不了test case。

h*l2017-11-02 07:11

16 楼

？？？
heap删除跟bst有什么关系？

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

: 如果要删除的话，要用BST .

m*n2017-11-02 07:11

17 楼

我说的是如果数字不仅仅增加，还可能减小的情况。

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

: ？？？
: heap删除跟bst有什么关系？

m*n2017-11-02 07:11

18 楼

这个你只增加，不是意味着一个num保存了无数个freq对象？
任意来一个数字，你都增加一个freq对象，内存受得了？

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

: if(!ht.containsKey(n))
: ht.put(n,0);
: ht.put(n, ht.get(n)+1);
: maxheap.add(new Freq(n, ht.get(n)); 就可以了。

l*82017-11-02 07:11

19 楼

你是怎么从堆中删除元素的？或许可以改进删除方法

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

:
: 这情况我碰到几次了。都这么做的。删除的perf不行，过不了test case。

l*82017-11-02 07:11

20 楼

在这个例子里面，如果使用min heap,应该是把新加入item替换原来的堆顶item,然后调
整新item的位置，是log(k)代价。

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

: 你是怎么从堆中删除元素的？或许可以改进删除方法

h*l2017-11-02 07:11

21 楼

感觉按照题目，不会频率减小，但是多想也挺好

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

: 我说的是如果数字不仅仅增加，还可能减小的情况。

l*82017-11-02 07:11

22 楼

如果frequency只是计算time window里的，比如说过去24小时. 那么频率就会减小。

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

: 感觉按照题目，不会频率减小，但是多想也挺好

h*l2017-11-02 07:11

23 楼

对，这样会减小

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

: 如果frequency只是计算time window里的，比如说过去24小时. 那么频率就会减小。

p*22017-11-02 07:11

24 楼

达到一定程度一次性丢掉就可以了。
if(maxheap.size()>N)
{
new maxheap
copy K elements into new maxheap
delete old max heap
}

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

: 这个你只增加，不是意味着一个num保存了无数个freq对象？
: 任意来一个数字，你都增加一个freq对象，内存受得了？

l*82017-11-02 07:11

25 楼

But the first K elements can also have duplications.

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

:
: 达到一定程度一次性丢掉就可以了。
: if(maxheap.size()>N)
: {
: new maxheap
: copy K elements into new maxheap
: delete old max heap
: }

z*c2017-11-02 07:11

26 楼

每次都要添加元素到maxheap里么？那MaxHeap的大小超过了K怎么办？

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

: if(!ht.containsKey(n))
: ht.put(n,0);
: ht.put(n, ht.get(n)+1);
: maxheap.add(new Freq(n, ht.get(n)); 就可以了。

w*x2017-11-02 07:11

27 楼

我觉得就是hashtable + minheap
之前的数的频率肯定是要的存储的, 哪怕只是第一个数只出现了一次
维护k大的数我觉得可以就用一个排序数组, 因为每次一个数只加1,所以只需要和最小
的比较(不在数组内的情况)或第i-1个比较, 比如
5,4,3,3,2,1, 如果第4个数加1, ==> 5,4,3,4,2,1
只需要swap第3个数=> 5,4,4,3,2,1 貌似是O(1) ,如果重复情况太多可以修改成
更复杂的数据结构, 因该有办法说在发生改变的情况下达到O(1)
不过说实话, 实际跑起来肯定比用堆慢, hashtable + minheap因该最好

z*c2017-11-02 07:11

28 楼

我很困惑的是，如果更新了一个元素的freq，然后这个元素属于minHeap，那么怎么更
新这个元素在heap中的位置？

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

: 我觉得就是hashtable + minheap
: 之前的数的频率肯定是要的存储的, 哪怕只是第一个数只出现了一次
: 维护k大的数我觉得可以就用一个排序数组, 因为每次一个数只加1,所以只需要和最小
: 的比较(不在数组内的情况)或第i-1个比较, 比如
: 5,4,3,3,2,1, 如果第4个数加1, ==> 5,4,3,4,2,1
: 只需要swap第3个数=> 5,4,4,3,2,1 貌似是O(1) ,如果重复情况太多可以修改成
: 更复杂的数据结构, 因该有办法说在发生改变的情况下达到O(1)
: 不过说实话, 实际跑起来肯定比用堆慢, hashtable + minheap因该最好

p*22017-11-02 07:11

29 楼

这个倒是。不过一般做题的时候还要maitain 一个visited array来check这个。

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

: But the first K elements can also have duplications.

p*22017-11-02 07:11

30 楼

这个倒是。不过一般做题的时候还要maitain 一个visited array来check这个。

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

: But the first K elements can also have duplications.

w*x2017-11-02 07:11

31 楼

up shift, 局部向上调整

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

: 我很困惑的是，如果更新了一个元素的freq，然后这个元素属于minHeap，那么怎么更
: 新这个元素在heap中的位置？

z*c2017-11-02 07:11

32 楼

自己实现一个heap是可以做到的，但是如果他要你写code，用标准库提供的容器可以做
到么?

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

:
: up shift, 局部向上调整

w*x2017-11-02 07:11

33 楼

这种题不会叫写代码的

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

: 自己实现一个heap是可以做到的，但是如果他要你写code，用标准库提供的容器可以做
: 到么?

l*82017-11-02 07:11

34 楼

yes, this works.

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

:
: 这个倒是。不过一般做题的时候还要maitain 一个visited array来check这个。

l*82017-11-02 07:11

35 楼

c++ stl's priority_queue doesn't support updating privority. But boost

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

: 自己实现一个heap是可以做到的，但是如果他要你写code，用标准库提供的容器可以做
: 到么?

z*c2017-11-02 07:11

36 楼

heap不能解决频度发生改变时的调整，所以我想到的可以用hash+BST解决，C++里BST的
实现采用set
map freq;
set > bst;
bst的元素是一个的pair，以frequency排序
来一个str
1. f = freq[str] ++;
2. if (bst.find ((f, str)) != bst.end ()) {
// bst里有str了，那么更新str的freq值
bst.erase ((f, str))
bst.insert ((f + 1, str))
}
3. else
if (bst.size () < K)
// bst里元素不足K
bst.insert ((f + 1, str))
4. else
if (f + 1 > bst.begin ()->first) {
// str的freq大于bst中最小元素的freq
bst.erase (bst.begin ())
bst.insert ((f + 1, str))
}

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

:
: 这种题不会叫写代码的

p*22017-11-02 07:11

37 楼

这个刚才我也想过
不过java里更新的时候要delete insert

heap不能解决频度发生改变时的调整，所以我想到的可以用hash BST解决，C 里BST的
实现采用setmap freq;set★ Sent from iPhone App: iReader Mitbbs Lite 7.52

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

: heap不能解决频度发生改变时的调整，所以我想到的可以用hash+BST解决，C++里BST的
: 实现采用set
: map freq;
: set > bst;
: bst的元素是一个的pair，以frequency排序
: 来一个str
: 1. f = freq[str] ++;
: 2. if (bst.find ((f, str)) != bst.end ()) {
: // bst里有str了，那么更新str的freq值
: bst.erase ((f, str))

l*82017-11-02 07:11

38 楼

既然你的bst是以frequency排序，那么 bst.find ((f, str)) 岂不是很慢。

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

p*22017-11-02 07:11

39 楼

用hashtable找

既然你的bst是以frequency排序，那么 bst.find ((f, str)) 岂不是很慢。
★ Sent from iPhone App: iReader Mitbbs Lite 7.52

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

: 既然你的bst是以frequency排序，那么 bst.find ((f, str)) 岂不是很慢。

z*c2017-11-02 07:11

40 楼

why？logK呀？

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

: 既然你的bst是以frequency排序，那么 bst.find ((f, str)) 岂不是很慢。

l*82017-11-02 07:11

41 楼

你的key是frequency, 要查找string，没办法用二分查找的啊。

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

: why？logK呀？

z*c2017-11-02 07:11

42 楼

key是的pair

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

: 你的key是frequency, 要查找string，没办法用二分查找的啊。

l*82017-11-02 07:11

43 楼

你compare key的函数是什么？

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

: key是的pair

l*82017-11-02 07:11

44 楼

default comparision between two pairs:
In inequality comparisons (), the first elements are compared first, and
only if the inequality comparison is not true for them, the second elements
are compared.

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

: 你compare key的函数是什么？

P*A2017-11-02 07:11

45 楼

用BST挺好，比heap维护更方便，
修改了一下，可以不用把pair当作key来排序，在hash里面记录BST结点的指针
multimap bst;
hash_map > hm;
foreach given key k
0. if(hm.find(k)==hm.end()) {
hm.insert(make_pair(k, make_pair(1, bst.end())));
if (bst.size () < K) {
// bst里元素不足K
t = bst.insert (make_pair(f, k))
hm[k].second = t;
}
continue;
}
1. f = ++hm[k].first;
2. if (hm[k].second != bst.end()) {
// bst里有k了，那么更新freq值
bst.erase (hm[k].second)
t = bst.insert (make_pair(f, k))
hm[k].second = t;
}
3. else
if (f > bst.begin()->first) {
// k的freq大于bst中最小元素的freq
bst.erase (bst.begin ())
t = bst.insert (make_pair(f, k))
hm[k].second = t;
}

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