或许
只能是bsr了
0.1的代码在哪里？
没有代码，只是看到别人的成绩是0.062。我提交的是0.968，不过后来修改了一些，应该可以到0.6左右！ :)
如果用浮点是多少？？
单精度浮点？ 没有试过，他给的都是整形数据，所以我也一直用整形做的，可能心里觉得还是整形快一些吧！
我自己做了一个傻算的程序，不过算的都是2^32以内的整数，也不算快，如果单纯用浮点，而不做优化的话，应该还不如这个整形傻算的快！
原帖由 无心人 于 2009-3-12 17:29 发表 http://bbs.emath.ac.cn/images/common/back.gif
:)
如果用浮点是多少？？
单精度浮点？ 你先测试下排序的时间
和总时间
告诉俺
回复 34# 无心人 的帖子
我现在是用1-10000做测试，反正程序会停上2秒钟左右，而排序几乎不用等！ :)要具体时间，精确到0.001s的
最好带源代码
呵呵 如果使用BSR指令后，可能会快很多。
按照楼主的算法，求log(10)的算法是一个2分查找算法。
采用了BSR指令后，就是一个直接查表算法了，速度就快了很多倍 哈哈，代码终于完成了。程序中用到了一条汇编指令。在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;
}UINT128;
UINT128 pow10;
UINT128 tabLimit;
BYTE tabValue;
void set( UINT128 *n1,DWORD n)
{
n1->U=0;
n1->U=0;
n1->U=0;
n1->U=n;
}
//if n1>=n2 return 1 ,else return 0;
int ge( UINT128 *n1, UINT128 *n2)
{
if ( n1->U > n2->U )
return 1;
else if (n1->U < n2->U )
return 0;
if ( n1->U > n2->U )
return 1;
else if ( n1->U < n2->U )
return 0;
if ( n1->U > n2->U )
return 1;
else if ( n1->U < n2->U )
return 0;
if ( n1->U >= n2->U )
return 1;
else
return 0;
}
inline int _log2(DWORD r)
{
_asm
{
bsr eax,r
}
}
int log2( UINT128 *n1)
{
int i=0;
while ( n1->U==0 && i<=3)
i++;
if (i==4)
return 0;
return (3-i)*32+_log2(n1->U);
}
void Mul( UINT128 *n,DWORD m)
{
int i;
UINT64 x=0;
for (i=3;i>=0;i--)
{
x+= (UINT64)(n->U) * (UINT64)m;
n->U=(DWORD)(x);
x >>= 32;
}
}
void InitSearchTab()
{
int i,j,shift,base;
UINT128 r,low;
set(&r,1);
for (i=0;i<=38;i++)
{
pow10=r;
Mul(&r,10);
}
tabValue=0;
set( &(tabLimit),10);
base=0;
for (i=1;i<127;i++)
{
shift= i % 32;
low.U=low.U=low.U=low.U=0;
low.U= 1L << shift;
if (base<38 &&ge( &low,&(pow10) ) )
base++;
j=base;
while (ge( &low,&(pow10) ) && j<=38 )
j++;
tabLimit=pow10;
tabValue=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;
t.U ^=data.U;
t.U ^=data.U;
t.U ^=data.U;
t.U ^=data.U;
bc= log2(&t);
if (bc==127)
r+=38;
else
r+= tabValue;
if ( ge( &t, &(tabLimit)) )
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;
for (i=0;i<count;i++)
{
scanf("%u %u %u %u",&d0,&d1,&d2,&d3);
pData.U=d0;
pData.U=d1;
pData.U=d2;
pData.U=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;
}
回复 37# liangbch 的帖子
有人就是用BSR解的，不过我感觉差不出10倍，可能是我总想从算法本身作改进吧，也可能就是这些细节决定了速度上的差异。不过还是有些不死心，今天晚上我用二分递归搜索再试一下，明天告诉大家结果！ 呵呵！好的，我也修改一下，按照新的想法编写一下！明天给个测试结果！
另外你可以直接贴到那个ACM网站上，看看他测试的结果是多少！
原帖由 liangbch 于 2009-3-12 23:23 发表 http://bbs.emath.ac.cn/images/common/back.gif
哈哈，代码终于完成了。程序中用到了一条汇编指令。在PIV 2.6G，5000个数据，用时大约0.3秒。
楼主可用我的代码跑一下，看看能你目前的版本快多少。
下面给出程序。#include
#include
#include //for Ge ...