c**a
发帖数: 316 | 1 一个巨大的文本， 输出频率最高的 1 million 个单词及其频率。
我的想法：
扫描文本的过程中按 string 建
1个 binary search tree，
（其实用 hash 也可以， 但是 STL 没有 hash）
map
同时维持 一个 Min Heap 记录 目前频率 最高的单词
vector >
结束时 把 heap 搞出来就行了。 |
c**a
发帖数: 316 | 2 请大家拍一拍。
我觉得 问题就是 BST 比 hash 慢一些。
【在 c**a 的大作中提到】
: 一个巨大的文本， 输出频率最高的 1 million 个单词及其频率。
: 我的想法：
: 扫描文本的过程中按 string 建
: 1个 binary search tree，
: （其实用 hash 也可以， 但是 STL 没有 hash）
: map
: 同时维持 一个 Min Heap 记录 目前频率 最高的单词
: vector >
: 结束时 把 heap 搞出来就行了。
|
b***y
发帖数: 2799 | 3 我用 prefix tree, 每拿到一个单词就插入到TREE里, 用一个叶结点记录这个单词出现
的数目.
prefix tree的深度是最长单词的长度, 基本上是个constant. 而binary tree的深度是
log(N), N是unique单词总数, N>= 1M, 所以BST的深度至少是20, 甚至更多.
所以我觉得PREFIX TREE更快点.
【在 c**a 的大作中提到】
: 一个巨大的文本， 输出频率最高的 1 million 个单词及其频率。
: 我的想法：
: 扫描文本的过程中按 string 建
: 1个 binary search tree，
: （其实用 hash 也可以， 但是 STL 没有 hash）
: map
: 同时维持 一个 Min Heap 记录 目前频率 最高的单词
: vector >
: 结束时 把 heap 搞出来就行了。
|
c**a
发帖数: 316 | 4 弱若的问一下， prefix tree 是啥？
哪里有写。
感觉就是 trie ？
【在 b***y 的大作中提到】
: 我用 prefix tree, 每拿到一个单词就插入到TREE里, 用一个叶结点记录这个单词出现
: 的数目.
: prefix tree的深度是最长单词的长度, 基本上是个constant. 而binary tree的深度是
: log(N), N是unique单词总数, N>= 1M, 所以BST的深度至少是20, 甚至更多.
: 所以我觉得PREFIX TREE更快点.
|
T*******i
发帖数: 4992 | 5 yes
【在 c**a 的大作中提到】
: 弱若的问一下， prefix tree 是啥？
: 哪里有写。
: 感觉就是 trie ？
|
b***y
发帖数: 2799 | 6 就是trie.
【在 c**a 的大作中提到】
: 弱若的问一下， prefix tree 是啥？
: 哪里有写。
: 感觉就是 trie ？
|
r*********r
发帖数: 3195 | |
h****n
发帖数: 101 | 8
hashmap
【在 c**a 的大作中提到】
: 一个巨大的文本， 输出频率最高的 1 million 个单词及其频率。
: 我的想法：
: 扫描文本的过程中按 string 建
: 1个 binary search tree，
: （其实用 hash 也可以， 但是 STL 没有 hash）
: map
: 同时维持 一个 Min Heap 记录 目前频率 最高的单词
: vector >
: 结束时 把 heap 搞出来就行了。
|
c**a
发帖数: 316 | 9 在 大文本里找频率最高的1000 个词。
有个问题就是， 不管用 BST 还是 prefix tree，
如何 找到 频率最高的 1000 个词呢？
为了简单假设用 map;
如果保持一个min heap，长度为1000，
可以用 vector > ;
有 2种情况：
1. 当前词在 Heap 不在 heap 里， 这时 后者 不把当前词放进去， 后者把它和 root
交换(取决于根节点的值)
2. 如果在 Heap 里， 其相应节点的值要加 1
这时有两个问题，
1. 要找到 该节点
2. 破坏了 Heap 的结构， 如何恢复之？
【在 c**a 的大作中提到】
: 请大家拍一拍。
: 我觉得 问题就是 BST 比 hash 慢一些。
|
