posts - 7,  comments - 64,  trackbacks - 0

.....
...
..
.

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

FeedBack:
# re: 有没有更快的办法来统计一篇文章中的词组数量并排序输出（挑战速度）！[未登录]
2009-09-03 16:20 | foxriver

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;
}

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

# re: 有没有更快的办法来统计一篇文章中的词组数量并排序输出（挑战速度）！
2009-09-03 16:38 | Vincent

# re: 有没有更快的办法来统计一篇文章中的词组数量并排序输出（挑战速度）！[未登录]
2009-09-03 16:42 | foxriver

# re: 有没有更快的办法来统计一篇文章中的词组数量并排序输出（挑战速度）！
2009-09-03 16:46 | Vincent

hash的话,就想到一个比较出名的elfhash..  回复  更多评论

# re: 有没有更快的办法来统计一篇文章中的词组数量并排序输出（挑战速度）！[未登录]
2009-09-03 16:46 | foxriver

# re: 有没有更快的办法来统计一篇文章中的词组数量并排序输出（挑战速度）！
2009-09-03 16:48 | Vincent

# re: 有没有更快的办法来统计一篇文章中的词组数量并排序输出（挑战速度）！[未登录]
2009-09-03 16:49 | foxriver

# re: 有没有更快的办法来统计一篇文章中的词组数量并排序输出（挑战速度）！
2009-09-03 16:51 | Vincent

# 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

# re: 有没有更快的办法来统计一篇文章中的词组数量并排序输出（挑战速度）！[未登录]
2009-09-03 23:26 | dskit
map的底层用红黑树实现，

# re: 有没有更快的办法来统计一篇文章中的词组数量并排序输出（挑战速度）！
2009-09-03 23:46 | gbb

# re: 有没有更快的办法来统计一篇文章中的词组数量并排序输出（挑战速度）！
2009-09-04 14:30 | 凡客诚品

# re: 有没有更快的办法来统计一篇文章中的词组数量并排序输出（挑战速度）！
2009-09-06 23:19 | 唐风
std::map

 只有注册用户登录后才能发表评论。
 < 2009年9月 >
303112345
6789101112
13141516171819
20212223242526
27282930123
45678910

•