找回密码
 欢迎注册
楼主: litaoye

[求助] 关于一个运算优化的问题

[复制链接]
 楼主| 发表于 2009-3-12 17:26:53 | 显示全部楼层
原帖由 无心人 于 2009-3-12 17:23 发表
或许
只能是bsr了

0.1的代码在哪里?


没有代码,只是看到别人的成绩是0.062。我提交的是0.968,不过后来修改了一些,应该可以到0.6左右!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-3-12 17:29:45 | 显示全部楼层


如果用浮点是多少??
单精度浮点?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-3-12 17:37:04 | 显示全部楼层
没有试过,他给的都是整形数据,所以我也一直用整形做的,可能心里觉得还是整形快一些吧!

我自己做了一个傻算的程序,不过算的都是2^32以内的整数,也不算快,如果单纯用浮点,而不做优化的话,应该还不如这个整形傻算的快!

原帖由 无心人 于 2009-3-12 17:29 发表


如果用浮点是多少??
单精度浮点?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-3-12 17:39:21 | 显示全部楼层
你先测试下排序的时间
和总时间
告诉俺
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-3-12 17:49:36 | 显示全部楼层

回复 34# 无心人 的帖子

我现在是用1-10000做测试,反正程序会停上2秒钟左右,而排序几乎不用等!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-3-12 17:51:26 | 显示全部楼层


要具体时间,精确到0.001s的

最好带源代码

呵呵
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-3-12 18:52:54 | 显示全部楼层
如果使用BSR指令后,可能会快很多。

按照楼主的算法,求log(10)的算法是一个2分查找算法。
采用了BSR指令后,就是一个直接查表算法了,速度就快了很多倍
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-3-12 23:23:27 | 显示全部楼层
哈哈,代码终于完成了。程序中用到了一条汇编指令。在PIV 2.6G,5000个数据,用时大约0.3秒。
楼主可用我的代码跑一下,看看能你目前的版本快多少。

下面给出程序。
  1. #include <stdlib.h>
  2. #include <stdio.h>

  3. #include <windows.h>  //for GetTickCount function declare

  4. typedef unsigned __int64 UINT64;
  5. typedef unsigned long DWORD;
  6. typedef unsigned char BYTE;

  7. /*
  8.   This topic can be found at
  9.   http://acm.timus.ru/problem.aspx?space=1&num=1318
  10. */

  11. typedef struct
  12. {
  13.         DWORD U[4];
  14. }UINT128;


  15. UINT128 pow10[40];
  16. UINT128 tabLimit[128];
  17. BYTE        tabValue[128];

  18. void set( UINT128 *n1,DWORD n)
  19. {
  20.         n1->U[0]=0;
  21.         n1->U[1]=0;
  22.         n1->U[2]=0;
  23.         n1->U[3]=n;
  24. }

  25. //if n1>=n2 return 1 ,else return 0;
  26. int ge( UINT128 *n1, UINT128 *n2)
  27. {
  28.         if ( n1->U[0] > n2->U[0] )
  29.                 return 1;
  30.         else if (  n1->U[0] < n2->U[0] )
  31.                 return 0;

  32.         if ( n1->U[1] > n2->U[1] )
  33.                 return 1;
  34.         else if ( n1->U[1] < n2->U[1] )
  35.                 return 0;

  36.         if ( n1->U[2] > n2->U[2] )
  37.                 return 1;
  38.         else if ( n1->U[2] < n2->U[2] )
  39.                 return 0;

  40.         if ( n1->U[3] >= n2->U[3] )
  41.                 return 1;
  42.         else
  43.                 return 0;
  44. }

  45. inline int _log2(DWORD r)
  46. {
  47.         _asm
  48.         {
  49.                 bsr eax,r
  50.         }
  51. }

  52. int log2( UINT128 *n1)
  53. {
  54.         int i=0;
  55.         while ( n1->U[i]==0 && i<=3)
  56.                 i++;
  57.         if (i==4)
  58.                 return 0;
  59.        
  60.         return (3-i)*32+_log2(n1->U[i]);
  61. }

  62. void Mul( UINT128 *n,DWORD m)
  63. {
  64.         int i;
  65.         UINT64 x=0;
  66.         for (i=3;i>=0;i--)
  67.         {
  68.                 x+= (UINT64)(n->U[i]) * (UINT64)m;
  69.                 n->U[i]=(DWORD)(x);
  70.                 x >>= 32;
  71.         }
  72. }

  73. void InitSearchTab()
  74. {
  75.         int i,j,shift,base;
  76.         UINT128 r,low;

  77.         set(&r,1);
  78.         for (i=0;i<=38;i++)
  79.         {
  80.                 pow10[i]=r;
  81.                 Mul(&r,10);
  82.         }

  83.         tabValue[0]=0;
  84.         set( &(tabLimit[0]),10);
  85.         base=0;
  86.         for (i=1;i<127;i++)
  87.         {
  88.                 shift= i % 32;
  89.                 low.U[0]=low.U[1]=low.U[2]=low.U[3]=0;
  90.                 low.U[3-i/32]= 1L << shift;
  91.                
  92.                 if (base<38 &&  ge( &low,&(pow10[base+1]) ) )
  93.                         base++;

  94.                 j=base;
  95.                 while (  ge( &low,&(pow10[j]) ) && j<=38 )
  96.                         j++;
  97.                
  98.                 tabLimit[i]=pow10[j];
  99.                 tabValue[i]=j-1;
  100.         }
  101. }

  102. int logSum( UINT128 *data,int count)
  103. {
  104.         int i,j,bc;
  105.         UINT128 t;
  106.         DWORD r=0;

  107.         for (i=0;i<count;i++)
  108.         {
  109.                 for (j=i+1;j<count;j++)
  110.                 {
  111.                         t=data[i];

  112.                         t.U[0] ^=  data[j].U[0];
  113.                         t.U[1] ^=  data[j].U[1];
  114.                         t.U[2] ^=  data[j].U[2];
  115.                         t.U[3] ^=  data[j].U[3];
  116.                
  117.                         bc= log2(&t);
  118.                         if (bc==127)
  119.                                 r+=38;
  120.                         else
  121.                                 r+= tabValue[bc];
  122.                         if ( ge( &t, &(tabLimit[bc])) )
  123.                                 r++;
  124.                 }
  125.         }
  126.        
  127.         return r*2;
  128. }

  129. int main(int argc, char* argv[])
  130. {
  131.         int i,count;
  132.         DWORD d0,d1,d2,d3, nlogSum;
  133.         UINT128 *pData=NULL;
  134.         DWORD t=GetTickCount();

  135.         InitSearchTab();
  136.         scanf("%d",&count);

  137.         pData=new UINT128[count];

  138.         for (i=0;i<count;i++)
  139.         {
  140.                 scanf("%u %u %u %u",&d0,&d1,&d2,&d3);
  141.                 pData[i].U[0]=d0;
  142.                 pData[i].U[1]=d1;
  143.                 pData[i].U[2]=d2;
  144.                 pData[i].U[3]=d3;
  145.         }

  146.         nlogSum= logSum(pData,count);
  147.         delete[] pData; pData=NULL;

  148.         printf("%u\n",nlogSum);
  149.         t=GetTickCount()-t;
  150.         printf("It take %d ms\n",t);

  151.         return 0;
  152. }
复制代码

评分

参与人数 1威望 +1 鲜花 +1 收起 理由
litaoye + 1 + 1 精彩绝伦

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-3-12 23:23:54 | 显示全部楼层

回复 37# liangbch 的帖子

有人就是用BSR解的,不过我感觉差不出10倍,可能是我总想从算法本身作改进吧,
也可能就是这些细节决定了速度上的差异。不过还是有些不死心,今天晚上我用二分递归搜索再试一下,明天告诉大家结果!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-3-12 23:26:21 | 显示全部楼层
呵呵!好的,我也修改一下,按照新的想法编写一下!明天给个测试结果!

另外你可以直接贴到那个ACM网站上,看看他测试的结果是多少!

原帖由 liangbch 于 2009-3-12 23:23 发表
哈哈,代码终于完成了。程序中用到了一条汇编指令。在PIV 2.6G,5000个数据,用时大约0.3秒。
楼主可用我的代码跑一下,看看能你目前的版本快多少。

下面给出程序。#include
#include

#include   //for Ge ...
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 21:26 , Processed in 0.045480 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表