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 阅读(1961) 评论(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倍。

当然，前提必须是单线程。回复更多评论