求高效算法

Question

1，自定义数据类形PN，包括int ID，double x, double y ;以X从大到小及y从小到到排序。大约有五万个点左右，所以要求效率。
2，找出5万个字符串中，重复的项和重复的个数。就象数据库操作 Select a, count(a) from table group by a having count(a) > 1 的效果一样。同样要求高效

Answer 1

用stl 参考关联容器吧.
stl效率较高

Answer 2

第一个算法，用STL写过一个，效率不太理想

Answer 3

1. double数据能够转成大整型，然后用stl的vector，或者list存储，排序算法可以选择2. 不知道你这5万个字符串是怎么构建的，能不能在构建的时候存储一些附加信息，比如为每个字符串存储一个key，然后用stl的multi map 查找即可

Answer 4

1. 五万个节点总共就1MB的大小,直接排序就可以;
2. 建议使用Hash算法对数据重新整理,字符串为Key加计数即可.

Answer 5

我测试过一百万的数据量,用Hash整理完,不超过2s(12字符长度),我想你这5万,最多不会超过5秒就能够完成吧.问题一的数据没有做过测试,不敢盲目下结论.基本上参考stl的算法,把比较函数替换成自己的就可以了.

Answer 6

做了五万个元素的排序,好象也没什么时间消耗上的感觉.
typedef struct _data{
int ID;
double x;
double y;
}DATA,*LPDATA;DATA R[50000];
int CompareData(DATA &a,DATA &b)
{
if (a.x>b.x)return 1;
if (a.x<b.x) {
return -1;
}
if (a.y<b.y)return 1;
if (a.y>b.y) {
return -1;
}
return 0;
}void Partition(const int nSize,const int nLo)
{
  int Lo,Hi;
  Hi=nSize;
  Lo=nLo;
  DATA Mid=R[(Lo+Hi)/2];
  do
  {
 while(CompareData(R[Lo],Mid))
        Lo++;
 while(CompareData(Mid,R[Hi]))
        Hi--;
     if(Lo<=Hi)
 {
DATA tmp = R[Lo];
R[Lo]=R[Hi];
R[Hi]=tmp;
        Lo++;
        Hi--;
     }
  }while(Lo<=Hi);  if(Hi>nLo)
 Partition(Hi,nLo);
  if(Lo<nSize)
 Partition(nSize,Lo);}

Answer 7

上面的比较函数Copy错了
int CompareData(DATA &a,DATA &b)
{
if (a.x>b.x)return 1;
if (a.x<b.x) {
return 0;
}
if (a.y<b.y)return 1;
return 0;
}

Answer 8

用sqlite或者extremeDB的内存表功能，加个索引，这样做即简单，又有数据库的高效，使用起来又非常方便，省了写算法的时间，最重要的是都满足LZ的条件。

Answer 9

昨天看了下我原来的代码，和unsigned 的基本一样：bool op(const MyPnt *p1, const MyPnt *p2 )
{
if (p1->y > p2->y)
return true; if (p1->y < p2->y) 
return false; if (p1->x > p2->x)
return false;
else 
return true;
};