C++程序设计教程第二版课件C++程序设计教程6章节幻灯片.pptVIP

* * 分别排序，直接加以字串比较是直截了当的思路： for ( string s,t; inst; ) { sort ( s.begin ( ), s.end ( ) ) ; sort ( t.begin ( ), t.end ( ) ) ; cout( s==t ? yes\n : no\n ) ; } C++标准算法 * * 避免排序，分别统计两个字串中０１的个数则性能更优：( 排序至少做O(nlogn)数量级运算，统计只做O(n)数量级运算 ) for ( string s,t; inst; ) { int s1=count(s.begin(), s.end(), ’1’); int s0=count(s.begin(), s.end(), ’0’); int t1=count(t.begin(), t.end(), ’1’); int t0=count(t.begin(), t.end(), ’0’); cout(s1==t1 s0==t0 ? yes\n : no\n); } C++标准算法 * * 字串中非０即１的特征，可以避免多余的统计，进一步提高性能： for ( string s,t; inst; ) { int s1=count ( s.begin(), s.end(), ’1’) ; int t1=count ( t.begin(), t.end(), ’1’) ; cout (s1==t1 s.length()==t.length() ? yes\n : no\n); } C++标准算法 * * 6. 动态内存 ( Dynamic Memory ) 揭示：许多问题不知道数据量的大小，需要所运用的数据结构具有扩容能力；许多问题要求时间性能甚于空间占用．充分利用堆空间(动态内存)是解决这些问题的关键 做法：理解堆空间的使用场合，学习堆空间的使用方法 * * 使用容器，便是自动使用堆内存 例如，从abc.txt中读取诸段落： ifstream in ( abc.txt ) ; vectorstring ps ; // ps.reserve(1100) ; 可以预留 for ( string s ; getline ( in, s ) ; ) ps.push_back(s) ; 预留是减小频繁扩容造成的数据移动开销 * * 若每个数据的处理，都要用到已经处理的数据时，保存历史数据，则可以改善时间性能 例如，统计一亿之内的素数个数(原始版)： bool isPrime(int n){ int sqrtn=sqrt(n*1.0); for(int i=2; i=sqrtn; ++i) if(n%i==0) return false; return true; }//-------------------------- int main(){ int num=0; for(int i=2; i=100000000; ++i) if(isPrime(i)) num++; coutnumendl; }//-------------------------- * * 空间换时间版 int main() { bitset100000000* p = new bitset100000000; p-set(); for(int i=2; i=10000; ++i) if(p-test(i)) for(int j=i*i; jp-size(); j+=i) p-reset(j); int num=0; for(int i=2; i100000000; ++i) if(p-test(i)) num++; coutnumendl; delete[] p; } 在空间中统计 完成每个 元素的标记 * * 7. 低级编程 ( Lower Programming ) 揭示：通过无原则的代码优化来简化程序的执行步骤,从而提高性能.它会影响可读性,并需要对程序的内存布局有深刻的了解,这一般是编程课的后继学习内容 做法：尽量去掉组织程序所花费的代价:少用调用频繁的函数;通过指针间访数据;尽可能不用类;无原则数据共享;用C库不用C++库 * * 低级编程版：逐一读入两个０１字串，比较是否含有相同元素 int cnt(char* a){ int num=0; while(*a) if(*a