求助：求一个简单的小算法，经常被调用，希望高效点

okocha-jay

大家都很热心，非常感谢。
才注册没几天，以后我回常来的。

1. 
   
2. //这是等级0到9对应的最低分数线；比如，得分是2万，那么等级是1；因为超过了1万分（等级1，也就数组下标），没达到3万分（下标2）
   
3. const unsigned int levels[10] = {0, 10000, 30000, 60000, 100000, 150000, 210000, 280000, 360000, 450000};
   
4. 
   
5. 求一个函数，根据输入分数，得到对应等级
   
6. 
   
7. int getLevel(unsigned int score);
   
8. 
   
9. 我写了一个，谢谢大家的帮助
   
10. unsigned short getLevel(unsigned int score )
    
11. {
    
12.         int low = 0, high = 9;
    
13.         int mid;
    
14. 
    
15.         while ( true )
    
16.         {
    
17.                 mid = (low + high ) / 2;
    
18. 
    
19.                 if ( score >= levels[mid])
    
20.                 {
    
21.                         if ( mid==9 || score < levels[mid+1])
    
22.                                 return mid;
    
23.                         else
    
24.                                 low = mid + 1;
    
25.                 }
    
26.                 else//不可能是mid等级
    
27.                 {
    
28.                         assert(mid>0);
    
29.                         high = mid - 1;
    
30.                 }
    
31.         }
    
32. }
    

复制代码

cugb_cat

写最原始的需求

yylogo

如果要被经常调用的话, 最好用汇编, 或者嵌入式汇编.

cugb_cat

如果要被经常调用的话, 最好用汇编, 或者嵌入式汇编.
yylogo 发表于 2010-02-09 21:57

这种优化是最最后才考虑的。

daybreakcx

看你的数据如果去掉四个0的话就是1,3,6,10,15,...，这个按照目前的规律是前n项自然数的和，也就是1+2+...+n=n*(n+1)/2，我们只要找到对应的n就可以了
假设你的输入是x，对于n*(n+1)/2=x化简后就是n^2 + n - 2*x = 0这个方程在x为正数的时候对应的n值唯一，且为正数，我们求解这个方程有
n=(sqrt(8*x+1)-1)/2，也就是我们根据x求出n后求整就可以了。
然后接下来就是求这个公式了，记得我们原先的x是在score/10000之后的，所以n=(sqrt(x/1250+1)-1)/2，函数内代码就一行：

1. int getLevel(unsigned int score)
   
2. {
   
3.         return (int)((sqrt(score / 1250.0 + 1) - 1) / 2);
   
4. }

复制代码

不知道有没有更快的，毕竟我用了sqrt，可能用牛顿叠代在你精度要求不大的时候计算次数少，会更快点儿，反正我的想法就是这样{:3_186:}

w_anthony

回复 1# okocha-jay

通用方法是二分法，可以借助stl的std::lower_bound来完成，把内容存入vector，lower_bound得到iterator后跟begin减一下就行了。

不过也有更快的方法，你这组数字有一个规律：s = (n + 1) * n * 10000。
而对于给定一个s找出n的规则是满足s>=(n + 1) *n * 10000的最大正整数n，也就是满足n<=(sqrt(1 + 8 * s / 10000) - 1) / 2这个条件的最大正整数n，考虑浮点计算误差，那么C/C++代码大致如下：
int n = (int)((sqrt(1.0f + 8.0f * (s + 0.5f) / 10000.0f) - 1.0f) / 2.0f);
如果n有界限，可以最后判断一下截止也行。

daybreakcx

楼上，我们想一块儿去了，握个手吧

w_anthony

回复 7# daybreakcx


   

群雄逐鹿中原

反正就那几个数，先生成一个46个值的表，然后查表，飞快。
int level[] =
{
    0, //0
    1, //10000
    1, //20000
    2, //30000
    2, //40000
    2, //50000
    3, //60000
    3, //70000
    ....
};

noword2k

查表不对吧，中间的数怎么办？

另外用sqrt和浮点数的方法，不见得比老老实实的一个个if else快，毕竟比较是整数，还可以用二分法优化一下。