请教一个查找排序算法问题

xiongzm

三维空间中点P(x,y,z)， x, y, z为整数
那么点P到原点O的距离平方为：rsq = x*x + y*y + z*z

(x,y,z) 各分量在区间[-100,100]取值

（1） 请问每个相同rsq对应P点的个数，并按rsq排序
比如rsq = 1的时候有6个点(1,0,0), (-1,0,0), (0,1,0), (0,-1,0)等

（2） 同时，当给出一个合理的rsq（P点存在）, 求这个rsq在序列中的位置？

上面的问题涉及到排序，查找
对于第（2）个问题，可以在O(1)时间内得到吗？怎么设计hash函数？

cugb_cat

rsq相同的点在同一个球面上，对rsq排序，相当于有很多球面，由里向外。

xiongzm

恩，这些相同半径的离散点位于等球面上
对于第二个问题，还是没想到一个好的解决办法

cugb_cat

原帖由 xiongzm 于 2008-4-26 12:48 发表
恩，这些相同半径的离散点位于等球面上
对于第二个问题，还是没想到一个好的解决办法

你的第二个问题我没明白是啥意思？
给定一个半径，找出这个半径在序列中的位置？

xiongzm

对，因为程序中经常要查找这个半径在序列中的位置

程序框架大概是这样的：

首先计算点P(x,y,z)  ( 各分量在比如[-100,100]这个范围内)  的模方
即点P到原点O的距离平方

a） 这个模方序列，有多长？对于每个计算出来的模方，其对应的P点个数是多少
按模方数值大小排序得到一个序列，最小的模方显然为0, 最大为30000

这个问题计算量不大，也好求。

b) 程序的主要部分是一个大循环， 循环 给出P点的坐标，(px,py,pz)， 计算一些和P点相关的量，
然后存储到和P点模方相对应的某些数组中。所以要由点P的坐标，得到在前面计算出来
的那个序列中的位置。

因为同一个模方rsq存在着大量的格点，而且p点的范围可能较大，比如[-1000,1000]，
所以查找比较费时，空间消耗也很大。能否有一个好的hash table处理这个问题？



你的第二个问题我没明白是啥意思？
给定一个半径，找出这个半径在序列中的位置？ [/quote]

cugb_cat

原帖由 xiongzm 于 2008-4-26 20:58 发表
对，因为程序中经常要查找这个半径在序列中的位置

程序框架大概是这样的：

首先计算点P(x,y,z)  ( 各分量在比如[-100,100]这个范围内)  的模方
即点P到原点O的距离平方

a） 这个模方序列，有多长？对 ...

用各个分量做索引是否可以？

xiongzm

看看我的代码，运行起来太慢了
不知道有哪些地方可以优化

比如运行时取参数 LSIZE=500
老半天出不来

#include <stdlib.h> #include <stdio.h> typedef struct _RSQ {     int rsq;     int nsq;     struct _RSQ *pre;     struct _RSQ *next; }RSQ; int prsq[1000][1000]; int main( int argc, char **argv ) {     int LSIZE;     register int i, j, k;     register int ir, iq, ip;     register int msq;     int *mysq;         RSQ *psq, *qsq, *osq;     RSQ rsq;             if ( argc < 2 )     {         printf( "usage: ./prog LSIZE\n" );         exit(1);     }         LSIZE = atoi( argv[1] );         rsq.rsq = -1;     rsq.nsq = 0;     rsq.pre = NULL;     rsq.next = NULL;              psq = &rsq;         for ( i = 0; i <= LSIZE; i++ )     {         printf( "i = %d\n", i );         for ( j = 0; j <= LSIZE; j++ )         {             for ( k = 0; k <= LSIZE; k++ )             {                 msq = i*i + j*j + k*k;                                 if ( msq > psq->rsq )                 {                     // allocate one                     qsq = (RSQ*) malloc( sizeof(RSQ) );                     psq->next = qsq;                                          qsq->pre = psq;                     qsq->rsq = msq;                     qsq->nsq = ( ( i*j*k ) ? 8 : ( (i*j||j*k||i*k) ? 4 : ( (i||j||k)? 2 : 1 ) ) );                     qsq->next = NULL;                                              psq = qsq;                 }                 else if ( msq < psq->rsq )                 {                     qsq = psq->pre;                                          while ( msq < qsq->rsq )                     {                         qsq = qsq->pre;                     }                                          if ( msq == qsq->rsq )                     {                                                  qsq->nsq += ( ( i*j*k ) ? 8 : ( (i*j||j*k||i*k) ? 4 : ( (i||j||k)? 2 : 1 ) ) );                     }                     else                     {                         // insert one                         osq = (RSQ*) malloc( sizeof(RSQ) );                         osq->pre = qsq;                         osq->next = qsq->next;                         osq->rsq = msq;                         osq->nsq = ( ( i*j*k ) ? 8 : ( (i*j||j*k||i*k) ? 4 : ( (i||j||k)? 2 : 1 ) ) );                                                  (qsq->next)->pre = osq;                         qsq->next = osq;                                                                      }                 }                                 else if ( msq == psq->rsq )                 {                     psq->nsq += ( ( i*j*k ) ? 8 : ( (i*j||j*k||i*k) ? 4 : ( (i||j||k)? 2 : 1 ) ) );                 }                             }         }     }     ir = 0;         for ( qsq = rsq.next; qsq->next != NULL; qsq = qsq->next )     {         printf( "%d\t%d\n", qsq->rsq, qsq->nsq );         ir++;     }     printf( "%d\t%d\n", qsq->rsq, qsq->nsq );     ir++;         mysq = (int*)malloc( ir*sizeof(int) );         ir = 0;     for ( qsq = rsq.next; qsq->next != NULL; qsq = qsq->next )         mysq[ir++] = qsq->rsq;     mysq[ir++] = qsq->rsq;         for ( qsq = psq; qsq->pre != NULL;  )     {         osq = qsq->pre;         free(qsq);         qsq = osq;     }                     prsq[0][0] = 0;            for ( i = 1; i < LSIZE; i++ )     {         for ( j = i; j < LSIZE; j++ )         {             msq = i*i + j*j;                      for ( k = prsq[i-1][j-1]+1; k < ir; k++ )             {                    qsq = psq->next;                                 if ( msq == mysq[k] )                 {                     prsq[i][j] = k;                     break;                 }             }             if ( k == ir-1 )             {                 printf( "don't find it\n" );                 exit(1);             }                                         printf( "%d\t%d\t%d\n", i, j, prsq[i][j] );         }                       }                 free(mysq);              return 1; }

[ 本帖最后由 xiongzm 于 2008-4-27 22:16 编辑 ]

xiongzm

没有人对这个问题感兴趣吗？
我自己再来顶一下！
按上面的算法，不算排序的时间，问题规模首先是O(N^3)的
加上排序算法，时间复杂性更大了

我对那些排序算法不熟悉
上面的代码用指针插入排序
对这个问题有什么好的排序算法吗？

xiongzm

在上面的代码基础上，k分量循环里面顺序排序加以改进
现在可以在合理的时间内算出来，N=400时10来分钟

如果在(J,K)两重循环里面先排序，再合并，估计还要快点。

tyz

我看看啊