posts - 7,  comments - 64,  trackbacks - 0

我现在需要统计一篇文章中的单词数量,并排序输出。
格式

单词1 500
单词2 499
单词3 300
.....
...
..
.

现在的思路是
第一步:先将单词读入到map<string,size_t> ssmap;当中;这样每次扫描到一个新单词后都可以++ssmap[str];来统计单词数;
第二步:将map中的内容拷贝到vector<pair<string*,size_t> > vec;当中,之后对vec用sort进行排序。(之所以要用string*是因为不希望发生string的拷贝构造,以免浪费时间)。
第三步:将vec输出。

试验了一下上述方法可以正确执行。
但我想应该有更快的方法,请各位赐教一下!


呵呵,谢谢大家这么积极。

字符串长度没有限制,这个从一个分词程序对文章进行分词处理以后的结果。单词可能是“的,了”这种单个字,也可能是“中华人民共和国”这种字符串。还有可能遇到像“\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\...(n个)”这种比较变态的符号。

posted on 2009-09-03 16:05 HIT@ME 阅读(1894) 评论(16)  编辑 收藏 引用

FeedBack:
# re: 有没有更快的办法来统计一篇文章中的词组数量并排序输出(挑战速度)![未登录]
2009-09-03 16:20 | foxriver
map查找已经足够快了。你看看是不是单词多,排序浪费了太多的时间。可以修改成radix sort, 加快速度。不过可能会有点难度,你要把string转换成int,还用到多重排序。

个人测试大规模数据,速度还能接受。贴点逼人的简陋代码,仅供参考,核心算法见:http://www.codercorner.com/RadixSortRevisited.htm

class vector_string : public vector<string>
{
public:
vector_string()
{
}
~vector_string()
{
}

public:
void sort(vector<int>* r_offsetset = 0)
{
vector<string> swaplist;
swaplist.resize(_Num);

vector<uint> sorttable1;
vector<uint> sorttable2;
vector<uint> sorttable3;

sorttable1.resize(_Num);
sorttable2.resize(_Num);
sorttable3.resize(_Num);

int i;
for (i=0;i<_Num;i++)
{
const string& str = _First[i];
uint b;
int n;

b = 0;
for (n=0;n<4 && n<str.size();n++)
{
if (n == 0) b |= (str[n] << 24) & 0xff000000;
if (n == 1) b |= (str[n] << 16) & 0x00ff0000;
if (n == 2) b |= (str[n] << 8) & 0x0000ff00;
if (n == 3) b |= (str[n]) & 0x000000ff;
}
sorttable1[i] = b;

b = 0;
for (n=4;n<8 && n<str.size();n++)
{
if (n == 4) b |= (str[n] << 24) & 0xff000000;
if (n == 5) b |= (str[n] << 16) & 0x00ff0000;
if (n == 6) b |= (str[n] << 8) & 0x0000ff00;
if (n == 7) b |= (str[n]) & 0x000000ff;
}
sorttable2[i] = b;

b = 0;
for (n=8;n<12 && n<str.size();n++)
{
if (n == 8) b |= (str[n] << 24) & 0xff000000;
if (n == 9) b |= (str[n] << 16) & 0x00ff0000;
if (n == 10) b |= (str[n] << 8) & 0x0000ff00;
if (n == 11) b |= (str[n]) & 0x000000ff;
}
sorttable3[i] = b;
}

radixsort_t radix;
uint* sorted = radix.Sort((uint*)&sorttable3[0], sorttable3.size(), false).Sort((uint*)&sorttable2[0], sorttable2.size(), false).Sort((uint*)&sorttable1[0], sorttable1.size(), false).GetIndices();

resort(sorted, 0, _Num, swaplist);
if (r_offsetset) r_offsetset->resort(sorted, 0, _Num);

// ------- 2 ------
vector<uint> swaptable;
swaptable.resize(_Num);

for (i=0;i<_Num;i++) swaptable[i] = sorttable1[i];
for (i=0;i<_Num;i++) sorttable1[i] = swaptable[sorted[i]];

for (i=0;i<_Num;i++) swaptable[i] = sorttable2[i];
for (i=0;i<_Num;i++) sorttable2[i] = swaptable[sorted[i]];

for (i=0;i<_Num;i++) swaptable[i] = sorttable3[i];
for (i=0;i<_Num;i++) sorttable3[i] = swaptable[sorted[i]];

// 测试 程序 文字 1
// 测试 程序 文字
// 测试 程序 文比
uint tab1 = 0xFFFFFFFF;
uint tab2 = 0xFFFFFFFF;
uint tab3 = 0xFFFFFFFF;

int samecount = 0;
for (i=0;i<_Num;i++)
{
if (tab1 == sorttable1[i] && tab2 == sorttable2[i] && tab3 == sorttable3[i])
{
samecount++;
continue;
}

if (samecount)
{
int start = i - samecount-1;
int total = samecount + 1;

bool exactsame = true;
for (int n=start+1;n<start+total;n++)
{
if (_First[n-1] != _First[n])
{
exactsame = false;
break;
}
}

if (exactsame == false)
{
quicksort_t::sort((int*)sorted, _First+start, total, _cmp);
resort(sorted, start, total, swaplist);
if (r_offsetset) r_offsetset->resort(sorted, start, total);
}
}

tab1 = sorttable1[i];
tab2 = sorttable2[i];
tab3 = sorttable3[i];
samecount = 0;
}

if (samecount)
{
int start = i - samecount-1;
int total = samecount + 1;

quicksort_t::sort((int*)sorted, _First+start, total, _cmp);
resort(sorted, start, total, swaplist);
if (r_offsetset) r_offsetset->resort(sorted, start, total);
}
}

protected:
void resort(const uint* r_sorted, int r_offset, int r_num, vector<string>& r_swaplist)
{
int i;
for (i=0;i<r_num;i++) r_swaplist[i].swap(_First[r_sorted[i]+r_offset]);
for (i=0;i<r_num;i++) _First[i+r_offset].swap(r_swaplist[i]);
}
};

  回复  更多评论
  
# re: 有没有更快的办法来统计一篇文章中的词组数量并排序输出(挑战速度)![未登录]
2009-09-03 16:32 | foxriver
如果你用的是标准的new,stl的string会频繁调用也耗费不少时间。可以改用id software的那个idHeap,官网quake4 sdk里就有,速度号称是vc版本的N倍。

当然,前提必须是单线程。  回复  更多评论
  
# re: 有没有更快的办法来统计一篇文章中的词组数量并排序输出(挑战速度)!
2009-09-03 16:38 | Vincent
今年的astar就有一道牵扯到这个的题目.
楼主的做法应该就是利用hash表统计吧..
我提出另外一个做法用trie树..  回复  更多评论
  
# re: 有没有更快的办法来统计一篇文章中的词组数量并排序输出(挑战速度)![未登录]
2009-09-03 16:42 | foxriver
楼主应该不是hash表,是rt树,不过两者速度也差不多了,没什么可优化的地方。hash只有在数据相当大的情况下(>1000万条),才会有明显优势。  回复  更多评论
  
# re: 有没有更快的办法来统计一篇文章中的词组数量并排序输出(挑战速度)!
2009-09-03 16:46 | Vincent
哦..呵呵..我不太清楚rt树是什么..
而且楼主说的这个还是太笼统..
比如单词字符串的长度上限等等.
不同的条件下不同的方法有着不同的效率..

hash的话,就想到一个比较出名的elfhash..  回复  更多评论
  
# re: 有没有更快的办法来统计一篇文章中的词组数量并排序输出(挑战速度)![未登录]
2009-09-03 16:46 | foxriver
晕死,打错字了,是RB-TREE.  回复  更多评论
  
# re: 有没有更快的办法来统计一篇文章中的词组数量并排序输出(挑战速度)!
2009-09-03 16:48 | Vincent
红黑树啊..
呵呵...个人觉得只要能设计出合理的hash还是hash更快些吧..  回复  更多评论
  
# re: 有没有更快的办法来统计一篇文章中的词组数量并排序输出(挑战速度)![未登录]
2009-09-03 16:49 | foxriver
我喜欢用BKDR Hash Function,简单方便,散布率对本人而言,已经相当满意了。  回复  更多评论
  
# re: 有没有更快的办法来统计一篇文章中的词组数量并排序输出(挑战速度)!
2009-09-03 16:51 | Vincent
惭愧啊..事实上我只会写elfhash...  回复  更多评论
  
# re: 有没有更快的办法来统计一篇文章中的词组数量并排序输出(挑战速度)![未登录]
2009-09-03 16:53 | foxriver
"个人觉得只要能设计出合理的hash还是hash更快些吧", 严重同意!不过对于楼主来说,写一个hash查找来替换std::map挺费时间的,内存管理上弄不好的话,效率和稳定性会下降,说不定还没人家stl的快,所以不是很推荐呢。  回复  更多评论
  
# re: 有没有更快的办法来统计一篇文章中的词组数量并排序输出(挑战速度)!
2009-09-03 16:56 | Vincent
^_^stl王道  回复  更多评论
  
# re: 有没有更快的办法来统计一篇文章中的词组数量并排序输出(挑战速度)!
2009-09-03 23:00 | wcdj
用Unix or Linux下的使用程序 sort wc 是相当的快  回复  更多评论
  
# re: 有没有更快的办法来统计一篇文章中的词组数量并排序输出(挑战速度)![未登录]
2009-09-03 23:26 | dskit
map的底层用红黑树实现,
可以用trie树,但是有中文,还有其他符号,好像就不好处理了  回复  更多评论
  
# re: 有没有更快的办法来统计一篇文章中的词组数量并排序输出(挑战速度)!
2009-09-03 23:46 | gbb
这个不是标准的mapreduce样例么?  回复  更多评论
  
# re: 有没有更快的办法来统计一篇文章中的词组数量并排序输出(挑战速度)!
2009-09-04 14:30 | 凡客诚品
不错哦  回复  更多评论
  
# re: 有没有更快的办法来统计一篇文章中的词组数量并排序输出(挑战速度)!
2009-09-06 23:19 | 唐风
std::map
本身不就是排序的吗?为什么还要倒到vector里排?不解  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

常用链接

留言簿(5)

随笔档案

test

搜索

  •  

最新评论

阅读排行榜

评论排行榜