可笑的优化
2023-03-14 10:26:00 时间
这几天没事做的时候都会上projecteuler.net上面去做题,其中14题是这样的:
he following iterative sequence is defined for the set of positive integers:
遗憾的是,这个版本跑了快13分钟,太让人难以接受了。那么是否能优化下?怎么优化?我的机器是双核的,跑这个单进程单线程的程序只利用了一半的CPU,那么能不能搞成两个线程来计算?缓存需要在两个线程之间做同步,显然读的多,写的少,应该采用读写锁。OK,第二个版本利用ACE的线程封装实现如下:
将数据分成了两半,利用两个线程来计算,果然快了一点,快了多少呢?从13分钟减少到9分钟,CPU利用率也到了100%,内存占用也降低了一半,似乎成绩不错呀。正在沾沾自喜之际,突然想起,能不能简单地暴力破解,咱不搞缓存,不搞多线程,看看效果怎么样。那么第三个版本简单实现如下:
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;
}
#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 ();
}
#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;
}
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也是一样。什么缓存、多线程,全抛到了九霄云外。
总结教训,想当然的性能估计是愚不可及的,想当然的优化是愚不可及的,简单直接才是美!
文章转自庄周梦蝶 ,原文发布时间 2009-01-23
相关文章
- PHP 性能分析与实验——性能的宏观分析
- 数据挖掘领域十大经典算法之C4.5算法(超详细附代码)
- 每位新手程序员都应当了解的七条箴言
- 程序员要如何学英语?
- 程序员该如何应对老板和客户的施压
- 大数据的8个最佳实践
- 从把三千行代码重构成15行代码谈起
- 企业大数据工作的任务、工具及挑战
- 独立程序员如何赚钱致富
- 数据危机再起!外卖平台信息泄露拷问企业数据资产管理
- 华为发布新一代企业级分布式数据仓库FusionInsight LibrA
- 在算法交易中使用大数据分析
- 七年一剑 华丽蜕变:WOT2018揭秘技术背后的真相
- 半路学编程,可以成为大牛程序员吗?
- 关于烂代码的那些事
- 数据挖掘领域十大经典算法之—K-Means算法(超详细附代码)
- 程序员和工程师有什么不一样?
- 甲骨文携手巨大集团 树立制造业数字化转型新典范
- 3月份Github上最热门的数据科学和机器学习项目
- 程序人生的寂静欢喜