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 閱讀(1995) 評論(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倍。

當然，前提必須是單線程。回復更多評論