`

可笑的优化

Chrome多线程CachethreadJavaScript 
阅读更多

这几天没事做的时候都会上projecteuler.net上面去做题，其中14题是这样的：
he following iterative sequence is defined for the set of positive integers:

n → n /2 (n is even)
n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

 

    题目并不难理解，这个据说是著名的角谷猜想，现在要找到100万以下的数字中展开这个链最长的数字是多少。如果我一开始就直接按照题意来解答，这个题目花不了几分钟，直接暴力法。然而我却想的太多了，我猜想在计算这个链条长度的过程中会不会有很多数字会重复计算，如果加上缓存 以前计算的结果是否能节约比较多的时间？那么第一次解答如下：

<!---->#include < iostream >
#include < map >
#include < windows.h >
using   namespace  std;
unsigned  long  produce_term(unsigned  long  n)
{
     if (n & 1 )
         return   3 * n + 1 ;
     else
         return  n >> 1 ;
}
 int  main()
{
    map < unsigned  long , int >  counters;
     int  max_i = 0 ;
     int  max_count = 0 ;
    DWORD tick1,tickPassed;
    tick1  =  GetTickCount(); 
     for ( int  i = 1 ;i < 1000000 ;i ++ )
    {
         int  sum = 2 ;
        unsigned  long  term = i;
         while ((term = produce_term(term)) != 1 )
        {
             if (counters[term]){
                sum += counters[term];
                 break ;
            } else
                sum += 1 ;
        }

         if (sum > max_count)
        {
            max_i = i;
            max_count = sum;
            counters[i] = sum;
        }

    }
    tickPassed  =  GetTickCount() - tick1; 
    cout << tickPassed << endl;
    cout << max_i << endl << max_count << endl;
     return   0 ;
}

  
    遗憾的是，这个版本跑了快13分钟，太让人难以接受了。那么是否能优化下？怎么优化？我的机器是双核的，跑这个单进程单线程的程序只利用了一半的CPU，那么能不能搞成两个线程 来计算？缓存需要在两个线程之间做同步，显然读的多，写的少，应该采用读写锁 。OK，第二个版本利用ACE的线程封装实现如下：

<!---->#include < iostream >
#include < map >
#include  " ace/Thread_mutex.h "
#include  " ace/Synch.h "
#include  " ace/Thread_Manager.h "
using   namespace  std;
 class  ThreadSafeMap
{
 public :
    ThreadSafeMap()
    {
    }
     int   get (unsigned  long  n)
    {
        ACE_READ_GUARD_RETURN(ACE_RW_Thread_Mutex,guard,mutex_, 0 );
         return  counters_[n];
    }
     int  put(unsigned  long  key, int  value)
    {
        ACE_WRITE_GUARD_RETURN(ACE_RW_Thread_Mutex,guard,mutex_, - 1 );
        counters_[key] = value;
         return   0 ;
    }

 private :
    map < unsigned  long , int >  counters_;
    ACE_RW_Thread_Mutex mutex_;
};
unsigned  long  produce_term(unsigned  long  n)
{
     if (n & 1 )
         return   3 * n + 1 ;
     else
         return  n >> 1 ;
}
 static  ThreadSafeMap counters;
ACE_THR_FUNC_RETURN run_svc ( void   * arg)
{
     int  max_i = 0 ;
     int  max_count = 0 ;
     for ( int  i = 500001 ;i < 1000000 ;i ++ )
    {
         int  sum = 2 ;
        unsigned  long  term = i;
         while ((term = produce_term(term)) != 1 )
        {
             if (counters. get (term)){
                sum += counters. get (term);
                 break ;
            } else
                sum += 1 ;
        }

         if (sum > max_count)
        {
            max_i = i;
            max_count = sum;
            counters.put(i,sum);
        }

    }
    cout << max_i << endl << max_count << endl;
     return   0 ;
}
 int  main( int  ac, char *  argv[])
{
     if  (ACE_Thread_Manager::instance () -> spawn (
         //  Pointer to function entry point.
        run_svc,
         //  <run_svc> parameter.
        NULL,
        THR_DETACHED  |  THR_SCOPE_SYSTEM)  ==   - 1 )
         return   - 1 ;
     int  max_i = 0 ;
     int  max_count = 0 ;

     for ( int  i = 1 ;i < 500000 ;i ++ )
    {
         int  sum = 2 ;
        unsigned  long  term = i;
         while ((term = produce_term(term)) != 1 )
        {
             if (counters. get (term)){
                sum += counters. get (term);
                 break ;
            } else
                sum += 1 ;
        }

         if (sum > max_count)
        {
            max_i = i;
            max_count = sum;
            counters.put(i,sum);
        }

    }
    cout << max_i << endl << max_count << endl;
     return  ACE_Thread_Manager::instance () -> wait ();
}

   
    将数据分成了两半，利用两个线程来计算，果然快了一点，快了多少呢？从13分钟减少到9分钟，CPU利用率也到了100%，内存占用也降低了一半，似乎成绩不错呀。正在沾沾自喜之际，突然想起，能不能简单地暴力破解，咱不搞缓存，不搞多线程，看看效果怎么样。那么第三个版本简单实现如下：

<!---->#include < iostream >
using   namespace  std;
unsigned  long  produce_term(unsigned  long  n)
{
     if (n & 1 )
         return   3 * n + 1 ;
     else
         return  n >> 1 ;
}
 int  main()
{
   int  max_i;
   int  max_count = 0 ;
   for ( int  i = 1 ;i < 1000000 ;i ++ )
  {
      int  count = 2 ;
     unsigned  long  term = i;
      while ((term = produce_term(term)) > 1 )
         count += 1 ;
      if (count > max_count){
           max_i = i;
           max_count = count;
     }
  }
  cout << max_i << endl << max_count << endl;
  system( " pause " );
   return   0 ;
}


    程序执行的结果让我惊掉了下巴，竟然只执行了1秒多，换成java也是一样。什么缓存、多线程，全抛到了九霄云外。

     总结教训，想当然的性能估计是愚不可及的，想当然的优化是愚不可及的，简单直接才是美！

分享到：
| yanf4j-0.41 beta发布
评论
6 楼 yangguo 2010-09-27  
暴力美学。
5 楼 dennis_zane 2009-02-04  
测了下，缓存命中率竟然是0，汗
4 楼 dennis_zane 2009-02-04  
@hax
又用java验证了一下，结果是一样的
import java.util.*;

public class Test {
	static long produce_term(long n) {
		if ((n & 1) != 0)
			return 3 * n + 1;
		else
			return n >> 1;
	}

	public static void main(String args[]) {
		test1();
		test2();
	}

	private static void test1() {
		long start = System.currentTimeMillis();
		int max_i = 0;
		int max_count = 0;
		for (int i = 1; i < 1000000; i++) {
			int count = 2;
			long term = i;
			while ((term = produce_term(term)) > 1) {
				count += 1;
			}
			if (count > max_count) {
				max_i = i;
				max_count = count;
			}
		}
		System.out.println("max_i=" + max_i + ",max_count=" + max_count);
		System.out.println("timed:" + (System.currentTimeMillis() - start));
	}

	static void test2() {
		Map<Integer, Integer> cache = new HashMap<Integer, Integer>();
		long start = System.currentTimeMillis();
		int max_i = 0;
		int max_count = 0;
		for (int i = 1; i < 1000000; i++) {
			int count = 2;
			long term = i;
			while ((term = produce_term(term)) > 1) {
				if (cache.containsKey(term))
					count += cache.get(term);
				else
					count++;
			}
			if (count > max_count) {
				max_i = i;
				max_count = count;
				cache.put(i, count);
			}
		}
		System.out.println("max_i=" + max_i + ",max_count=" + max_count);
		System.out.println("timed:" + (System.currentTimeMillis() - start));
	}
}
3 楼 dennis_zane 2009-02-04  
@hax
测了下你给的代码，问题在于n溢出了，变成了负数，你可以查看n=837799时n的计算链条

要注意到在计算的过程中n一定会超出100万这个范围的，所以在cpp中用了unsigned  long


2 楼 dennis_zane 2009-02-04  
@hax
你的答案是错误的，正确的是837799

数据量是100万，而非100000
1 楼 hax 2009-02-04  
你的程序有问题吧。用javascript写了一个测试，明显缓存是有效的。

[code=JavaScript]
var MAX = 100000

new function () {
var start = new Date().getTime()
var max = 0, maxn
var n, count
for (var i = 2; i < MAX; i++) {
n = i, count = 0
do {
if ((n & 1) === 0) n = n >> 1
else n = (n * 3 + 1) >> 1
count++
} while(n > 1);
if (count > max) {
max = count
maxn = i
}
}
var end = new Date().getTime()
say (maxn, max, end - start)
}

new function () {
var start = new Date().getTime()
var max = 0, maxn
var cache = []
var n, count
for (var i = 2; i < MAX; i++) {
n = i, count = 0
do {
if ((n & 1) === 0) n = n >> 1
else n = (n * 3 + 1) >> 1
if (cache[n]) {
count += cache[n] + 1
break
}
count++
} while(n > 1);
cache[i] = count
if (count > max) {
max = count
maxn = i
}
}
var end = new Date().getTime()
say (maxn, max, end - start)
}


注：需要自己写一个say函数来打印输出。

如果你使用Google Chrome，可以把MAX设为100000，因为Chrome的V8引擎对整数运算做了优化，所以比其他浏览器要快一个数量级。在我的机器上结果是：

910107 299 1541 910107 299 485

也就是不缓存用了1.5秒，缓存的用了0.5秒不到。
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    鲁棒优化研究综述

    正如中国谚语所说：“不确定性让人不安，但确定性则令人可笑。”在实际应用中，我们无法获得完全确定的信息，因此如何在不确定性环境下做出最优决策成为了一个重要的问题。 #### 鲁棒优化的基本概念 鲁棒优化的...

    华三无线优化配置指导书

    华三无线优化配置指导书主要包含了一系列针对WLAN网络的优化配置措施，旨在提升无线网络的性能和用户体验。以下是对文档中提到的各个配置知识点的详细解释。 1. WLAN网络调优简介 WLAN网络调优是指对无线局域网进行...

    快速创建可笑的词法分析器-Rust开发

    创建可笑的快速Lexers徽标创建可笑的快速Lexers。 徽标有两个目标：使创建Lexer变得容易，因此您可以专注于更复杂的问题。 要使生成的Lexer比您用手编写的任何内容都要快。 为了实现这些目标，徽标：将所有令牌定义...

    MSSQL优化之探索MSSQL执行计划（转）

    网上的SQL优化的文章实在是很多，说实在的，我也曾经到处找这样的文章，什么不要使用IN了，什么OR了，什么AND了，很多很多，还有很多人拿出仅几S甚至几MS的时间差的例子来证明着什么(有点可笑)，让许多人不知道其是...

    MouseWheel:零依赖可笑的快速鼠标滚轮处理程序

    再者，"可笑的快速"可能暗示了该库使用了一些高效的算法或优化技巧，使得即使在处理大量滚轮事件时也能保持流畅性，不会对页面性能造成显著影响。 最后，项目名为"MouseWheel-master"，其中"master"通常代表项目的...

    在我的JSP学生信息管理系统中的检测用户名是否重复的页面中时 遇到了一个可笑的问题.doc

    从给定的文件信息来看，主要讨论的是在JSP学生信息管理...正确使用`equals`方法、合理选择循环结构、掌握数据库查询与结果集处理，以及利用AJAX技术优化用户体验，都是构建高效、安全的学生信息管理系统的必要条件。

    症结：Emacs可笑有用的扩展的集合

    Crux这个名字在英语中有关键、核心之意，暗示了这些扩展对于优化Emacs工作流程的重要性。 Crux的扩展覆盖了编辑、导航、代码补全、项目管理等多个方面，旨在提高生产力，减少不必要的操作。下面我们将深入探讨其中...

    TOScrollBar:交互式滚动条，用于遍历可笑的大量滚动视图

    它的设计使其外观和行为类似于标准系统控件，并进行了优化以确保对滚动性能的影响最小。特征允许对UIScrollView的整个内容高度进行细粒度的滚动。 通过Objective-C运行时和KVO直接与UIScrollView互操作。 与标准...

    【优化方案】（山东专用）高中英语 Unit1 SectionⅠ Warming Up & Reading Preparing精品课件 新人教版选修6

    【优化方案】（山东专用）高中英语 Unit1 SectionⅠ Warming Up & Reading Preparing精品课件 新人教版选修6，这个标题表明我们正在探讨一个针对山东省高中英语教学的优化方案，主要集中在Unit1的SectionⅠ，即...

    react-storefront：React Storefront-电子商务的PWA。 100％离线，与平台无关，无头，支持Magento 2。 始终开源，Apache-2.0许可证。 加入我们作为贡献者（contributors@reactstorefront.io）

    React Storefront框架...可笑的速度React Storefront付出了更多努力，以从所有可能的实际和用户感知的性能优化中挤出速度，包括： 动态数据的高速缓存命中率高服务器端渲染自动创建AMP 动态数据的预测性预取代码拆分缓

    silenceblee-basic-framework2-master_java_

    "小小码童，可笑可笑"这句描述可能暗示了该项目起始于作者初学编程时的基础阶段，但随着时间的推移，它已经发展成为一个相对完整的框架，用于展示Java的高级应用。 在Java编程中，进阶学习通常涉及到以下几个方面：...

    4P与4C营销理论企业应用方案.docx

    假如企业不管4C只是、一味地强4调4P理论，那就是在闭门造车，一定会制订出可笑的销售政策、可笑的产品、可笑的促销计划；假如企业只是、一味地站在消费者的角度进行4C的时候，来满意消费者的需求，企业的成本将会...

    RecyclerView5.1.1后的各个版本

    例如，它提供了更强大的性能优化，如回收视图（view recycling）机制，减少内存占用和提高滚动流畅性。同时，RecyclerView支持多种布局管理器，如线性布局（LinearLayoutManager）、网格布局（GridLayoutManager）和...

    湖南省益阳市第六中学七年级语文上册 趣味阅读 阿长与《山海经》（第2课时）教案 北师大版

    在教学目标方面，学生需要整体感知课文，理解阿长的人物形象，包括她的饶舌多事、规矩繁多、爽朗热心、乐于助人的性格特征，以及她的无知可笑、愚昧落后和淳朴善良、仁慈的美德。同时，学生应学会通过领会文章中的...

    comic:测试

    描述中的"可笑的"可能是在描述漫画内容的幽默性质，或者是在开发过程中遇到了一些令人啼笑皆非的问题。结合标签"JavaScript"，我们可以推测这是一个使用JavaScript技术来创建的Web应用，可能是用于展示漫画、制作...

    comic

    在描述中提到的"可笑的"，虽然在中文里主要表达一种幽默或滑稽的感觉，但在IT语境下，这可能是对设计或交互性的形容，比如一个具有趣味性、引人发笑的漫画网站或应用。这可能涉及到如何通过HTML的特性，如CSS...

    Practical Photoshop September2016

    通过使用Photoshop CC的工具，用户可以轻松地将不同人的面部特征进行交换或组合，创造出一系列滑稽可笑的形象。这项技巧不仅可以用来增加乐趣，还能帮助设计师探索不同人物造型的可能性。 ##### 通过色调调整改变...

    托福词汇红宝(便携版).

    作者邀请读者发现并纠正可能存在的错误，这种开放态度有助于资源的不断完善和优化，使之成为更加宝贵的备考资料。这种互动交流的方式不仅促进了知识的共享，也激发了社区内成员的学习热情和互助精神，共同构建了一个...

    卷积神经网络的研究.pdf

    随着技术的发展，深度卷积神经网络通过增加网络层数、扩大训练数据集规模以及优化网络结构和训练算法，逐步提升了模型的性能。例如，AlexNet、ZF-Net、VGG、GoogleNet和ResNet等经典网络结构不断挑战深度的极限，...

Magicbox
Global site tag (gtag.js) - Google Analytics