关于一个运算优化的问题

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

如果用浮点是多少？？单精度浮点？

litaoye · 发表于 2009-3-12 17:37:04

没有试过，他给的都是整形数据，所以我也一直用整形做的，可能心里觉得还是整形快一些吧！我自己做了一个傻算的程序，不过算的都是2^32以内的整数，也不算快，如果单纯用浮点，而不做优化的话，应该还不如这个整形傻算的快！

原帖由 无心人 于 2009-3-12 17:29 发表如果用浮点是多少？？单精度浮点？

无心人 · 发表于 2009-3-12 17:39:21

你先测试下排序的时间和总时间告诉俺

litaoye · 发表于 2009-3-12 17:49:36

我现在是用1-10000做测试，反正程序会停上2秒钟左右，而排序几乎不用等！

无心人 · 发表于 2009-3-12 17:51:26

要具体时间，精确到0.001s的最好带源代码呵呵

liangbch · 发表于 2009-3-12 18:52:54

如果使用BSR指令后，可能会快很多。按照楼主的算法，求log(10)的算法是一个2分查找算法。采用了BSR指令后，就是一个直接查表算法了，速度就快了很多倍

liangbch · 发表于 2009-3-12 23:23:27

哈哈，代码终于完成了。程序中用到了一条汇编指令。在PIV 2.6G，5000个数据，用时大约0.3秒。楼主可用我的代码跑一下，看看能你目前的版本快多少。下面给出程序。

#include <stdlib.h>
#include <stdio.h>
#include <windows.h> //for GetTickCount function declare
typedef unsigned __int64 UINT64;
typedef unsigned long DWORD;
typedef unsigned char BYTE;
/*
This topic can be found at
http://acm.timus.ru/problem.aspx?space=1&num=1318
*/
typedef struct
{
DWORD U[4];
}UINT128;
UINT128 pow10[40];
UINT128 tabLimit[128];
BYTE tabValue[128];
void set( UINT128 *n1,DWORD n)
{
n1->U[0]=0;
n1->U[1]=0;
n1->U[2]=0;
n1->U[3]=n;
}
//if n1>=n2 return 1 ,else return 0;
int ge( UINT128 *n1, UINT128 *n2)
{
if ( n1->U[0] > n2->U[0] )
return 1;
else if ( n1->U[0] < n2->U[0] )
return 0;
if ( n1->U[1] > n2->U[1] )
return 1;
else if ( n1->U[1] < n2->U[1] )
return 0;
if ( n1->U[2] > n2->U[2] )
return 1;
else if ( n1->U[2] < n2->U[2] )
return 0;
if ( n1->U[3] >= n2->U[3] )
return 1;
else
return 0;
}
inline int _log2(DWORD r)
{
_asm
{
bsr eax,r
}
}
int log2( UINT128 *n1)
{
int i=0;
while ( n1->U[i]==0 && i<=3)
i++;
if (i==4)
return 0;
return (3-i)*32+_log2(n1->U[i]);
}
void Mul( UINT128 *n,DWORD m)
{
int i;
UINT64 x=0;
for (i=3;i>=0;i--)
{
x+= (UINT64)(n->U[i]) * (UINT64)m;
n->U[i]=(DWORD)(x);
x >>= 32;
}
}
void InitSearchTab()
{
int i,j,shift,base;
UINT128 r,low;
set(&r,1);
for (i=0;i<=38;i++)
{
pow10[i]=r;
Mul(&r,10);
}
tabValue[0]=0;
set( &(tabLimit[0]),10);
base=0;
for (i=1;i<127;i++)
{
shift= i % 32;
low.U[0]=low.U[1]=low.U[2]=low.U[3]=0;
low.U[3-i/32]= 1L << shift;
if (base<38 && ge( &low,&(pow10[base+1]) ) )
base++;
j=base;
while ( ge( &low,&(pow10[j]) ) && j<=38 )
j++;
tabLimit[i]=pow10[j];
tabValue[i]=j-1;
}
}
int logSum( UINT128 *data,int count)
{
int i,j,bc;
UINT128 t;
DWORD r=0;
for (i=0;i<count;i++)
{
for (j=i+1;j<count;j++)
{
t=data[i];
t.U[0] ^= data[j].U[0];
t.U[1] ^= data[j].U[1];
t.U[2] ^= data[j].U[2];
t.U[3] ^= data[j].U[3];
bc= log2(&t);
if (bc==127)
r+=38;
else
r+= tabValue[bc];
if ( ge( &t, &(tabLimit[bc])) )
r++;
}
}
return r*2;
}
int main(int argc, char* argv[])
{
int i,count;
DWORD d0,d1,d2,d3, nlogSum;
UINT128 *pData=NULL;
DWORD t=GetTickCount();
InitSearchTab();
scanf("%d",&count);
pData=new UINT128[count];
for (i=0;i<count;i++)
{
scanf("%u %u %u %u",&d0,&d1,&d2,&d3);
pData[i].U[0]=d0;
pData[i].U[1]=d1;
pData[i].U[2]=d2;
pData[i].U[3]=d3;
}
nlogSum= logSum(pData,count);
delete[] pData; pData=NULL;
printf("%u\n",nlogSum);
t=GetTickCount()-t;
printf("It take %d ms\n",t);
return 0;
}

复制代码

litaoye · 发表于 2009-3-12 23:23:54

有人就是用BSR解的，不过我感觉差不出10倍，可能是我总想从算法本身作改进吧，也可能就是这些细节决定了速度上的差异。不过还是有些不死心，今天晚上我用二分递归搜索再试一下，明天告诉大家结果！

litaoye · 发表于 2009-3-12 23:26:21

呵呵！好的，我也修改一下，按照新的想法编写一下！明天给个测试结果！另外你可以直接贴到那个ACM网站上，看看他测试的结果是多少！

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

账号		自动登录	找回密码
密码			欢迎注册

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

回复 34# 无心人的帖子

评分

回复 37# liangbch 的帖子

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

回复 34# 无心人 的帖子

评分

回复 37# liangbch 的帖子

回复 34# 无心人的帖子