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

 找回密码
 欢迎注册
数学研发论坛»论坛 › 【算法研发】 › 编程擂台 › 求由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-11-22 01:21 , Processed in 0.029335 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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