本文发表在 rolia.net 枫下论坛#include <iostream.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

typedef struct _RANDOM_STR_
{
int count;
union{
char str[12];
int number[3];
};
}RandomStr;

#define MAX_COUNT 100000
#define MAX_STR_LEN 12
#define INVALID_STR (-1)
#define TOP_TEN 10

RandomStr* pTop[TOP_TEN];

void addtotop( RandomStr* pTempStr, int start = -1, int end = -1 )
{
if( pTop[TOP_TEN-1] == NULL)
{
// first 10 times
for(int i = 0; i < TOP_TEN; i++)
{
if(pTop[i] != NULL && pTop[i]->count < pTempStr->count)
{
RandomStr* pTemp1 = pTop[i];
pTop[i] = pTempStr;
pTempStr = pTemp1;
} else if( pTop[i] == NULL )
{
pTop[i] = pTempStr;
break;
}
}
}
else if( start == -1 )
{
// 11th
if( pTop[TOP_TEN-1]->count < pTempStr->count )
{
addtotop(pTempStr, 0, TOP_TEN-1);
}
}
else
{
int i = (start + end) / 2;
if( 1 == end - start )
{
if( pTempStr->count > pTop[start]->count )
{
i = start;
}
else
i = end;

for( int j = TOP_TEN-1; j > i; j--)
{
pTop[j] = pTop[j-1];
}
pTop[i] = pTempStr;
}
else
{
if( pTempStr->count > pTop[i]->count )
{
addtotop(pTempStr, start, i);
}
else
{
addtotop(pTempStr, i, end);
}
}
}
}

char getarandomchar()
{
int i = ((double)rand() / (RAND_MAX+1) ) * 61;
char achar;
if( i >= 0 && i <= 9 )
{
achar = '0'+i;
}
else if( i >= 10 && i <= 35 )
{
achar = 'A' + i - 10;
}
else
{
achar = 'a' + i - 36;
}
return achar;
}

void createRandomString(char* pStr)
{
int iStrlen = (double)rand() / (RAND_MAX+1) * 7 + 5;
int i;

for( i = 0; i <= iStrlen; i++)
{
*pStr++ = getarandomchar();
}

for( ; i < MAX_STR_LEN; i++) *pStr++ = '\0';
}

void main(void)
{
RandomStr* pStr = new RandomStr[MAX_COUNT];
RandomStr* pTempStr = pStr;
RandomStr* pTempStr2;
clock_t t1, t2;
register int i, j;

srand( (unsigned)time( NULL ) );


for(i = 0; i<MAX_COUNT; i++)
{
pTempStr->count = 1;
createRandomString(pTempStr->str);
pTempStr++;
}

for( j = 0; j < 10; j++)
{
pTop[j] = NULL;
}

memset(pStr+10000, 0 ,sizeof(RandomStr)*10);
(pStr+10000)->count = 1;
strcpy((pStr+10000)->str, "test10th");
strcpy((pStr+10001)->str, "test10th");
strcpy((pStr+10002)->str, "test10th");
strcpy((pStr+10003)->str, "test10th");
strcpy((pStr+10004)->str, "test10th");
strcpy((pStr+10005)->str, "test10th");
strcpy((pStr+10006)->str, "test10th");
strcpy((pStr+10007)->str, "test10th");
strcpy((pStr+10008)->str, "test10th");
strcpy((pStr+10009)->str, "test10th");

memset(pStr+20000, 0 ,sizeof(RandomStr)*9);
(pStr+20000)->count = 1;
strcpy((pStr+20000)->str, "test9th");
strcpy((pStr+20001)->str, "test9th");
strcpy((pStr+20002)->str, "test9th");
strcpy((pStr+20003)->str, "test9th");
strcpy((pStr+20004)->str, "test9th");
strcpy((pStr+20005)->str, "test9th");
strcpy((pStr+20006)->str, "test9th");
strcpy((pStr+20007)->str, "test9th");
strcpy((pStr+20008)->str, "test9th");

memset(pStr+30000, 0 ,sizeof(RandomStr)*8);
(pStr+30000)->count = 1;
strcpy((pStr+30000)->str, "test8th");
strcpy((pStr+30001)->str, "test8th");
strcpy((pStr+30002)->str, "test8th");
strcpy((pStr+30003)->str, "test8th");
strcpy((pStr+30004)->str, "test8th");
strcpy((pStr+30005)->str, "test8th");
strcpy((pStr+30006)->str, "test8th");
strcpy((pStr+30007)->str, "test8th");

t1 = clock();
pTempStr = pStr;

for(i = 0; i<MAX_COUNT-1; i++)
{
if(pTempStr->count != INVALID_STR)
{
pTempStr2 = pTempStr+1;
for(j = i+1; j < MAX_COUNT; j++)
{
if( pTempStr2->count != INVALID_STR)
{
if( pTempStr->number[0] == pTempStr2->number[0]
&& pTempStr->number[1] == pTempStr2->number[1]
&& pTempStr->number[2] == pTempStr2->number[2] )
{
pTempStr->count++;
pTempStr2->count = INVALID_STR;
}
}
pTempStr2++;
}
}
pTempStr++;
}

pTempStr = pStr;
for( i = 0; i < MAX_COUNT; i++)
{
if( pTempStr->count != INVALID_STR)
{
addtotop(pTempStr);
}
pTempStr++;
}

for( i = 0; i < TOP_TEN; i++)
{
cout<<pTop[i]->count<<":"<<pTop[i]->str<<endl;
}

t2 = clock();

cout<<t2<<":"<<t1<<":"<<CLOCKS_PER_SEC<<":"<<(t2-t1)/CLOCKS_PER_SEC<<endl;

delete [] pStr;
}更多精彩文章及讨论，请光临枫下论坛 rolia.net