数学研发网设为首页收藏本站
切换到窄版

 找回密码
 欢迎注册
数学研发论坛»论坛 › 【算法研发】 › 编程擂台 › 求由0和1构成的最小十进制正整数，其是指定正整数的倍数 ...
1234下一页
返回列表 发新帖
楼主: gxqcn

[擂台] 求由0和1构成的最小十进制正整数，其是指定正整数的倍数

[复制链接]
gxqcn
 楼主| 发表于 2009-8-16 07:46:30 | 显示全部楼层

优化版本

  1. //  http://bbs.emath.ac.cn/viewthread.php?tid=1689&page=2&fromuid=8#pid21088

  3. #include <iostream>
  4. #include <ctime>

  6. #include <vector>
  7. #include <map>
  8. using namespace std;


  11. typedef unsigned int UINT32, *PUINT32;
  12. typedef unsigned __int64 UINT64, *PUINT64;

  14. typedef struct node
  15. {
  16.     UINT32  key;
  17.     UINT32  value;
  18. }NODE;

  20. typedef vector< NODE >              NODE_VECTOR;
  21. typedef map< UINT32, UINT32 >       KEY_INDEX_MAP;
  22. typedef KEY_INDEX_MAP::value_type   MVT;

  24. #ifndef UInt32x32To64
  25. #     define UInt32x32To64(a, b)    ((UINT64)(((UINT64)(a)) * ((UINT64)(b))))
  26. #endif

  28. char szResult[128];

  30. //  http://bbs.emath.ac.cn/viewthread.php?tid=1207&page=6&fromuid=8#pid16108
  31. UINT32 Sqrt( UINT32 n )
  32. {
  33.     UINT32 t;
  34.     UINT32 ret = 0;

  36.     #define SQRT_CORE(x)        \
  37.         t = ret + (1UL<<(x));   \
  38.         ret >>= 1;              \
  39.         if ( n >= t )           \
  40.         {                       \
  41.             n -= t;             \
  42.             ret += (1UL<<(x));  \
  43.         }

  45.     SQRT_CORE(30);
  46.     SQRT_CORE(28);
  47.     SQRT_CORE(26);
  48.     SQRT_CORE(24);
  49.     SQRT_CORE(22);
  50.     SQRT_CORE(20);
  51.     SQRT_CORE(18);
  52.     SQRT_CORE(16);
  53.     SQRT_CORE(14);
  54.     SQRT_CORE(12);
  55.     SQRT_CORE(10);
  56.     SQRT_CORE(8);
  57.     SQRT_CORE(6);
  58.     SQRT_CORE(4);
  59.     SQRT_CORE(2);
  60.     SQRT_CORE(0);

  62.     #undef SQRT_CORE

  64.     return ret;
  65. }

  67. const char * GetMin01( UINT32 n )
  68. {
  69.     char * p = szResult;

  71.     UINT32 i=0, j=0, d, ten, bits, index, size0, size1;
  72.     UINT32 key, SqrtN;
  73.     UINT32 value;

  75.     NODE info;
  76.     NODE_VECTOR vNode;
  77.     KEY_INDEX_MAP mKeyIndex;

  79.     KEY_INDEX_MAP::iterator it;

  81.     *( p += 127 ) = '\0';

  83. //  if ( 0 == n ) return p;

  85.     while ( 0 == ( 1 & n ))
  86.     {
  87.         ++i;    //times of prime 2
  88.         n >>= 1;
  89.     }
  90.     while ( 0 == n % 5 )
  91.     {
  92.         ++j;    //times of prime 5
  93.         n /= 5;
  94.     }
  95.     if ( i < j ) i = j; //max times of prime 2 and prime 5
  96.     memset( p -= i, '0', i * sizeof(char));

  98.     if ( 1 == n )
  99.     {
  100.         *(--p) = '1';

  102.         return p;
  103.     }

  105.     //special case that n+1 is 10^j
  106.     i = n + 1;
  107.     j = 0;
  108.     while ( 0 == i % 10 )
  109.     {
  110.         ++j;
  111.         i /= 10;
  112.     }
  113.     if ( 1 == i )
  114.     {
  115.         j *= 9;
  116.         memset( p -= j, '1', j * sizeof(char));

  118.         return p;
  119.     }

  121.     switch( n )
  122.     {
  123.     case 3:
  124.     case 37: n = 111;
  125.         break;

  127.     case 7:
  128.     case 13: n = 1001;
  129.         break;

  131.     case 337: n = 1011;
  132.         break;

  134.     case 367: n = 1101;
  135.         break;

  137.     default:
  138.         break;
  139.     }

  141.     i = n;
  142.     j = 0;
  143.     while (( d = i % 10 ) <= 1 )
  144.     {
  145.         *(--p) = '0' + d;
  146.         if ( 0 == ( i /= 10 ))
  147.         {
  148.             return p;
  149.         }

  151.         ++j;
  152.     }
  153.     p += j;

  155.     const UINT32 INIT4BITS[] = { 0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111, };
  156.     for ( i=0; 16!=i; ++i )
  157.     {
  158.         info.key = INIT4BITS[i] % n;
  159.         info.value = i;
  160.         vNode.push_back( info );
  161.         mKeyIndex.insert( MVT( info.key, i ));
  162.     }
  163.     index = i - 1;

  165.     SqrtN = Sqrt( n );
  166.     for ( bits=4, ten=10000%n, size1=size0=vNode.size(); ; )
  167.     {
  168.         for ( i=1; size0!=i; ++i )
  169.         {
  170.             d = (UINT32)( UInt32x32To64( vNode[i].key, ten ) % n );
  171.             if ( mKeyIndex.end() != ( it = mKeyIndex.find( n - d )))
  172.             {
  173.                 value = vNode[(*it).second].value;
  174.                 do
  175.                 {
  176.                     *(--p) = '0' + ( 1 & value );
  177.                     value >>= 1;
  178.                 } while( 0 != --bits );

  180.                 value = vNode[i].value;
  181.                 do
  182.                 {
  183.                     *(--p) = '0' + ( 1 & value );
  184.                 } while( 0 != ( value >>= 1 ));

  186.                 return p;
  187.             }
  188.         }

  190.         for ( i=1; size1!=i; ++i )
  191.         {
  192.             d = (UINT32)( UInt32x32To64( vNode[i].key, ten ) % n );
  193.             value = vNode[i].value << bits;

  195.             for ( j=0; size0!=j; ++j )
  196.             {
  197.                 key = vNode[j].key + d;
  198.                 if ( key < d || key >= n )
  199.                 {
  200.                     key -= n;
  201.                 }
  202.                 if ( mKeyIndex.end() == mKeyIndex.find( key ))
  203.                 {
  204.                     mKeyIndex.insert( MVT( info.key = key, ++index ));
  205.                     info.value = vNode[j].value | value;
  206.                     vNode.push_back( info );
  207.                 }
  208.             }
  209.         }

  211.         if ( size1 == size0 )
  212.         {
  213.             bits <<= 1;
  214.             ten = (UINT32)( UInt32x32To64( ten, ten ) % n );
  215.         }
  216.         else
  217.         {
  218.             ++bits;
  219.             ten = (UINT32)( UInt32x32To64( ten, 10 ) % n );
  220.         }

  222.         size0 = vNode.size();
  223.         if ( size0 <= SqrtN /*&& bits < 16*/ )
  224.         {
  225.             size1 = size0;
  226.         }
  227.         else
  228.         {
  229.             size1 = 2;
  230.         }
  231.     }

  233.     return p;
  234. }


  237. int main( void )
  238. {
  239.     UINT32 n;
  240.     const char * p;

  242.     while( 1 )
  243.     {
  244.         cout << "N=";
  245.         cin >> n;

  247.         if( 0 == n )
  248.         {
  249.             break;
  250.         }

  252.         clock_t start=clock();
  253.         p = GetMin01( n );
  254.         clock_t end=clock();

  256.         cout << p << "\n";
  257.         cout<< "Total cost " << end-start << "ms" << "\n" << endl;
  258.     }

  260.     return 0;
  261. }
复制代码
Change list:
1、新增整数开方函数；
2、将 value 由 UINT64 修改成 UINT32
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
发表于 2009-8-16 17:22:05 | 显示全部楼层
呃

那个函数代码行数有点大哦
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
发表于 2009-8-17 07:48:20 | 显示全部楼层
运行大量数据的统计结果,11#的程序速度并没有优势.
我这里运行时比如数据2230767,2384613,2389761都比较慢
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

gxqcn
 楼主| 发表于 2009-8-17 08:23:17 | 显示全部楼层
很奇怪，在我这里结论是相反的：
2#的测试结果如下：
  1. N=2230767
  2. 1000001010001010101110111110111110111111101
  3. Total cost 1418ms
  4. N=2384613
  5. 1000001010001010111110111111101110101110111
  6. Total cost 1637ms
  7. N=2389761
  8. 1000011101111111110111111011111111111111111
  9. Total cost 1606ms
  10. N=4294967291
  11. 1011101001001001001010000111001
  12. Total cost 312ms
  13. N=4294967279
  14. 1111011110011001110000101001001001
  15. Total cost 407ms
  16. N=4294967231
  17. 11111001101001000000010011010111
  18. Total cost 437ms
  19. N=899999999
  20. 1110010111111110000001111011010101101010101
  21. Total cost 2296ms
  22. N=
复制代码
我的则为：
  1. N=2230767
  2. 1000001010001010101110111110111110111111101
  3. Total cost 702ms

  5. N=2384613
  6. 1000001010001010111110111111101110101110111
  7. Total cost 779ms

  9. N=2389761
  10. 1000011101111111110111111011111111111111111
  11. Total cost 779ms

  13. N=4294967291
  14. 1011101001001001001010000111001
  15. Total cost 62ms

  17. N=4294967279
  18. 1111011110011001110000101001001001
  19. Total cost 234ms

  21. N=4294967231
  22. 11111001101001000000010011010111
  23. Total cost 93ms

  25. N=899999999
  26. 1110010111111110000001111011010101101010101
  27. Total cost 750ms

  29. N=
复制代码
我现在最新的代码如下（删除了开方函数，消减了初始化数量，新增了快速除5、除10的子函数）：
  1. //  http://bbs.emath.ac.cn/viewthread.php?tid=1689&page=2&fromuid=8#pid21101

  3. #include <iostream>
  4. #include <ctime>

  6. #include <vector>
  7. #include <map>
  8. using namespace std;


  11. typedef unsigned int UINT32, *PUINT32;
  12. typedef unsigned __int64 UINT64, *PUINT64;

  14. typedef struct node
  15. {
  16.     UINT32  key;
  17.     UINT32  value;
  18. }NODE;

  20. typedef vector< NODE >              NODE_VECTOR;
  21. typedef map< UINT32, UINT32 >       KEY_INDEX_MAP;
  22. typedef KEY_INDEX_MAP::value_type   MVT;

  24. #ifndef UInt32x32To64
  25. #     define UInt32x32To64(a, b)    ((UINT64)(((UINT64)(a)) * ((UINT64)(b))))
  26. #endif

  28. char szResult[128];


  31. __declspec(naked)
  32. UINT32 DivMod5( UINT32& n )
  33. {
  34.     __asm
  35.     {
  36.         mov     ecx, dword ptr[esp + 0x04];

  38.         mov     edx, dword ptr[ecx];
  39.         mov     eax, 0xCCCCCCCD;
  40.         push    edx;

  42.         mul     edx;
  43.         shr     edx, 2;
  44.         mov     dword ptr[ecx], edx;

  46.         lea     edx, [edx + 0x04*edx];

  48.         pop     eax;
  49.         sub     eax, edx;

  51.         ret;
  52.     }
  53. }


  56. __declspec(naked)
  57. UINT32 DivMod10( UINT32& n )
  58. {
  59.     __asm
  60.     {
  61.         mov     ecx, dword ptr[esp + 0x04];

  63.         mov     edx, dword ptr[ecx];
  64.         mov     eax, 0xCCCCCCCD;
  65.         push    edx;

  67.         mul     edx;
  68.         shr     edx, 3;
  69.         mov     dword ptr[ecx], edx;

  71.         imul    edx, 10;

  73.         pop     eax;
  74.         sub     eax, edx;

  76.         ret;
  77.     }
  78. }


  81. const char * GetMin01( UINT32 n )
  82. {
  83.     char * p = szResult;

  85.     UINT32 i=0, j=0, d, ten, bits, index, size0, size1;
  86.     UINT32 key;
  87.     UINT32 value;

  89.     NODE info;
  90.     NODE_VECTOR vNode;
  91.     KEY_INDEX_MAP mKeyIndex;

  93.     KEY_INDEX_MAP::iterator it;

  95.     *( p += 127 ) = '\0';

  97. //  if ( 0 == n ) return p;

  99.     while ( 0 == ( 1 & n ))
  100.     {
  101.         ++i;    //times of prime 2
  102.         n >>= 1;
  103.     }

  105.     while ( 0 == ( d = DivMod5( n )))
  106.     {
  107.         ++j;    //times of prime 5
  108.     }
  109.     n = n * 5 + d;

  111.     if ( i < j ) i = j; //max times of prime 2 and prime 5
  112.     memset( p -= i, '0', i * sizeof(char));

  114.     if ( 1 == n )
  115.     {
  116.         *(--p) = '1';

  118.         return p;
  119.     }

  121.     //special case that n+1 is 10^j
  122.     i = n + 1;
  123.     j = 0;
  124.     while ( 0 == ( d = DivMod10( i )))
  125.     {
  126.         ++j;
  127.     }
  128.     if ( 0 == i && 1 == d )
  129.     {
  130.         j *= 9;
  131.         memset( p -= j, '1', j * sizeof(char));

  133.         return p;
  134.     }

  136.     i = n;
  137.     j = 0;
  138.     while (( d = DivMod10( i )) <= 1 )
  139.     {
  140.         *(--p) = '0' + d;
  141.         if ( 0 == i )
  142.         {
  143.             return p;
  144.         }

  146.         ++j;
  147.     }
  148.     p += j;

  150.     info.value = info.key = 0;
  151.     vNode.push_back( info );
  152.     mKeyIndex.insert( MVT( info.key, index = 0 ));

  154.     info.value = info.key = 1;
  155.     vNode.push_back( info );
  156.     mKeyIndex.insert( MVT( info.key, ++index ));

  158.     for ( bits=1, ten=10%n, size1=size0=vNode.size(); ; )
  159.     {
  160.         for ( i=1; size0!=i; ++i )
  161.         {
  162.             d = (UINT32)( UInt32x32To64( vNode[i].key, ten ) % n );
  163.             if ( mKeyIndex.end() != ( it = mKeyIndex.find( n - d )))
  164.             {
  165.                 value = vNode[(*it).second].value;
  166.                 do
  167.                 {
  168.                     *(--p) = '0' + ( 1 & value );
  169.                     value >>= 1;
  170.                 } while( 0 != --bits );

  172.                 value = vNode[i].value;
  173.                 do
  174.                 {
  175.                     *(--p) = '0' + ( 1 & value );
  176.                 } while( 0 != ( value >>= 1 ));

  178.                 return p;
  179.             }
  180.         }

  182.         for ( i=1; size1!=i; ++i )
  183.         {
  184.             d = (UINT32)( UInt32x32To64( vNode[i].key, ten ) % n );
  185.             value = vNode[i].value << bits;

  187.             for ( j=0; size0!=j; ++j )
  188.             {
  189.                 key = vNode[j].key + d;
  190.                 if ( key < d || key >= n )
  191.                 {
  192.                     key -= n;
  193.                 }
  194.                 if ( mKeyIndex.end() == mKeyIndex.find( key ))
  195.                 {
  196.                     mKeyIndex.insert( MVT( info.key = key, ++index ));
  197.                     info.value = vNode[j].value | value;
  198.                     vNode.push_back( info );
  199.                 }
  200.             }
  201.         }

  203.         if ( size1 == size0 )
  204.         {
  205.             bits <<= 1;
  206.             ten = (UINT32)( UInt32x32To64( ten, ten ) % n );
  207.         }
  208.         else
  209.         {
  210.             ++bits;
  211.             ten = (UINT32)( UInt32x32To64( ten, 10 ) % n );
  212.         }

  214.         size0 = vNode.size();
  215.         if ( bits < 16 )
  216.         {
  217.             size1 = size0;
  218.         }
  219.         else
  220.         {
  221.             size1 = 2;
  222.         }
  223.     }

  225.     return p;
  226. }


  229. int main( void )
  230. {
  231.     UINT32 n;
  232.     const char * p;

  234.     while( 1 )
  235.     {
  236.         cout << "N=";
  237.         cin >> n;

  239.         if( 0 == n )
  240.         {
  241.             break;
  242.         }

  244.         clock_t start=clock();
  245.         p = GetMin01( n );
  246.         clock_t end=clock();

  248.         cout << p << "\n";
  249.         cout<< "Total cost " << end-start << "ms" << "\n" << endl;
  250.     }

  252.     return 0;
  253. }
复制代码
这是用VC2008编译的版本：
search_pid21021.exe (155.5 KB, 下载次数: 4)
search_pid21101.exe (149 KB, 下载次数: 5)
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
发表于 2009-8-17 08:57:59 | 显示全部楼层
应该U不同的原因

毕竟小肚子的机器忒好了
而且是正宗的Intel机器

郭的程序受缓存，指令周期的影响太大
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
发表于 2009-8-17 09:01:09 | 显示全部楼层
另外，哦只是另外
我没仔细考虑过

单纯用堆栈使用迭代的浮点运算
从头部计算是否能避免一些复杂数据结构的冗余带来的性能降低？
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

gxqcn
 楼主| 发表于 2009-8-17 09:10:15 | 显示全部楼层
我在家里的CPU也是intel的，不如mathe的好那是肯定的了。
无心人可以下载 14# 编译好的程序运行对比一下。

另外，这个问题如何用浮点解决？
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

gxqcn
 楼主| 发表于 2009-8-17 09:24:01 | 显示全部楼层
mathe 的程序强大在输入不局限32位内，可以适当超出一些。
我的估计内存耗用会少些（自我感觉，不敢确定），因为我是用32位存储的。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
发表于 2009-8-17 09:55:28 | 显示全部楼层
呵呵,我没有说你的程序慢,只是觉得性能基本相当.
还有我没有测试单个数据的速度区别(只是用gxqcn的程序找出几个比较慢的数据,在我的机器上500ms左右)
不过我的测量也不是完全准确,因为我的程序里面很多对最后结果转换部分删除了(我只统计每个结果的长度,而不管结果本身,所以可以删除部分代码).但是我觉得这部分代码对总体运行时间影响不大,所以就直接比较了.
而机器的区别在于我的机器内存缓存会比较好,所以对内存的访问速度要好很多
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
发表于 2009-8-17 09:57:02 | 显示全部楼层
我那个程序输入如果超过32位,还是需要修改一下,提供一个64比特整数乘64比特整数然后模一个64比特整数的函数,现在的程序结果会错的.但是可以大概用来评估一下计算超过32位时数据的速度.
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

1234下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-4-20 02:49 , Processed in 0.048132 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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