map查找已經(jīng)足夠快了。你看看是不是單詞多，排序浪費(fèi)了太多的時(shí)間。可以修改成radix sort, 加快速度。不過可能會(huì)有點(diǎn)難度，你要把string轉(zhuǎn)換成int，還用到多重排序。
個(gè)人測(cè)試大規(guī)模數(shù)據(jù)，速度還能接受。貼點(diǎn)逼人的簡(jiǎn)陋代碼，僅供參考，核心算法見：
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]];
// 測(cè)試 程序 文字 1
// 測(cè)試 程序 文字
// 測(cè)試 程序 文比
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]);
}
};
回復(fù) 更多評(píng)論