编程之美

按有用程度 按页码先后 最新笔记

• 

  1.1 让CPU占有率曲线听你指挥

  keep_it_real (No fear.No distractions.)

  让多核CPU占用率曲线听你指挥——《编程之美》1.1学习笔记 Problem: 写一个程序，让用户来决定Windows任务管理器（Task Manager）的CPU占用率。有以下几种情况： 1.CPU占用率固定在50%，为一条直线； 2.CPU的占用率为一条直线，具体占用率由命令行参数决定（范围1~100）； 3.CPU的占用率状态为一条正弦曲线。 分析与解法： （1）通过观察任务管理器，它大约1s更新一次。当CPU使用率为0时，System Idle Proces... (更多)

  让多核CPU占用率曲线听你指挥——《编程之美》1.1学习笔记

  Problem:

  写一个程序，让用户来决定Windows任务管理器（Task Manager）的CPU占用率。有以下几种情况： 1.CPU占用率固定在50%，为一条直线； 2.CPU的占用率为一条直线，具体占用率由命令行参数决定（范围1~100）； 3.CPU的占用率状态为一条正弦曲线。

  分析与解法：

  （1）通过观察任务管理器，它大约1s更新一次。当CPU使用率为0时，System Idle Process占用了CPU的空闲时间。

  System Idle Process在CPU空闲的的时候，发出一个IDLE命令，使CPU挂起（暂时停止工作），可有效的降低CPU内核的温度，无法终止。在这个进程里出现的CPU占用数值并不是真正的占用而是体现的CPU的空闲率，也就说这个数值越大CPU的空闲率就越高，反之就是CPU的占用率越高。Linux中对应的进程为init,PID为1。

  当系统中的进程或者在等待用户输入，或者在等待某些事件的发生（发出I/O请求等待I/O响应），或者主动进入休眠状态（比如Sleep()）。

  在任务管理器中的一个刷新周期内，CPU忙（执行应用程序）的时间和刷新周期总时间的比率就是CPU的占用率。其显示的是每个刷新周期内CPU占用率的统计平均值。我们可以写一个程序让它在任务管理器的刷新时间内一会儿忙，一会儿闲，通过调节忙/闲的比例，来控制任务管理器中显示的CPU占用率。

  书上的代码以单核CPU为前提，但对于多核CPU来说，同一个进程可能被CPU的任务分配器分配到不同的核心上执行，所以造成无法让任务管理器达到预想的效果。其实打开任务管理器，可以看到多个CPU使用记录。本人电脑CPU是Core i5 450M,双核4线程。在OS看来就如同有四个CPU工作一样。我的任务管理器中就有四个CPU使用记录。

  所谓超线程技术就是利用特殊的硬件指令，把多线程处理器内部的两个逻辑内核模拟成两个物理芯片，从而使单个处理器就能“享用”线程级的并行计算的处理器技术。多线程技术可以在支持多线程的操作系统和软件上，有效的增强处理器在多任务、多线程处理上的处理能力。

  可以使用SetProcessAffinityMask()函数可以使特定的处理器运行指定进程。

  BOOL SetProcessAffinityMask(HANDLE hProcess, DWORD_PTR dwProcessAffinityMask);

  第一个参数用来指定指定哪个进程，传入它的句柄。第二个进程用来指定哪个CPU核心来执行此进程。

  DWORD_PTR,其实就是unsigned long*.Unsigned long type for pointer precision.Use when casting a pointer to a long type to perform pointer arithmetic.(Also commonly used for general 32-bit parameters that have been extended to 64 bits in 64-bit windows.)

  DWORD 其实就是unsigned long。Windows下常用来保存地址或存放指针。

  比如这样调用函数：

  ::SetProcessAffinityMask(::GetCurrentProcess(),0x00000001);可以指定当前执行的进程在第一个CPU上运行。对于双核CPU，

  ::SetProcessAffinityMask(::GetCurrentProcess(),0x00000002);可以指定在第二个CPU上运行。

  ::SetProcessAffinityMask(::GetCurrentProcess(),0x00000003);可以允许在两个CPU上任意运行。

  HANDLE GetCurrentProcess(void);

  可以获得当前进程的句柄。注意，这个句柄为一个伪句柄。只能在我们的进程中才能代表当前进程的句柄，事实上这个函数目前只是简单的返回-1这个值。也就是说在我们的程序中-1便能表示本进程的句柄。

  （2）那么对于绘制50%直线，程序代码为：

  #include <Windows.h>  
  #include<stdlib.h>  
  #include<tchar.h>  
  int _tmain(int argc,_TCHAR* argv[])  
  {  
      int busyTime = 10;  
      int idleTime = busyTime*5;  
      __int64 startTime = 0;  
      ::SetThreadAffinityMask(::GetCurrentProcess(),0x00000001);  
      while(true)  
      {  
          startTime = GetTickCount();  
                  //busy loop  
          while((GetTickCount() - startTime) <= busyTime);  
                  //idle loop  
              Sleep(idleTime);  
      }  
      return 0;  
  }
  

  GetTickCount()可以得到系统从启动到运行到现在所经历时间的毫秒值。最多能统计到49.7天。我们利用它判断busy loop要持续多久。

  其中idleTime为busyTime的五倍，可以修改其值使其更逼近50%。不同机子的情况不同。

  __int64是VC++的64位扩展。范围为[-2^63,2^63)。当64位与32位混合运算时，32位整数会隐式转换成64位整数。输入输出它时使用cin、cout会造成错误。需要使用scanf("%I64d",&a);和printf("%I64d",a);

  还有unsigned __int64，其范围为[0,2^64)。

  对应g++中的64位扩展为long long和unsigned long long。范围与运算与上相仿。输入输出使用scanf("%lld",&a);和printf("%lld",a);

  int _tmain(int argc, _TCHAR* argv[])。

  _tmain这个符号多见于VC++创建的控制台工程中，这个是为了保证移植unicode而加入的（一般_t、_T、T()这些东西都和unicode有关系）。定义在头文件tchar.h中。

  （3）对于绘制正弦曲线：

  #include <Windows.h>  
  #include<stdlib.h>  
  #include<math.h>  
  #include<tchar.h>  
  const double SPLIT = 0.01;  
  const int COUNT = 200;  
  const double PI = 3.14159265;  
  const int INTERVAL = 300;  
  int _tmain(int argc, _TCHAR* argv[] )  
  {  
      DWORD busySpan[COUNT]; //array of busy times  
      DWORD idleSpan[COUNT]; //array of idle times  
      int half = INTERVAL/2;  
      double radian = 0.0;  
          //如何近似趋近一条正弦曲线？这样！  
      for(int i = 0; i < COUNT; ++i)  
      {  
          busySpan[i] = (DWORD)(half + (sin(PI * radian) * half));  
          idleSpan[i] = INTERVAL - busySpan[i];  
          radian += SPLIT;  
      }  
      DWORD startTime = 0;  
      int j = 0;  
      ::SetProcessAffinityMask(::GetCurrentProcess(),0x00000002);   
      while(true)  
      {  
          j = j % COUNT;  
          startTime = GetTickCount();  
          while((GetTickCount() - startTime) <= busySpan[j]);  
              Sleep(idleSpan[j]);  
          j++;  
      }  
      return 0;  
  }
  

  通过在一个周期2*PI中等分200份，将每一个间隔点的half + （sin( PI * radian) * half))的值存入busySpan[i]，将其补植存入idleSpan[i]。half是整个值域INTERVAL的一半。这样可以近似趋近一条正弦曲线。

  运行效果为：

  （4)可以通过RDTSC指令获得当前CPU核心运行周期数。

  在x86平台上定义函数：

  inline __int64 GetCPUTickCount()  
  {  
      __asm  
      {  
          rdtsc;  
      }  
  }
  

  在x64平台上定义：

  #define GetCPUTickCount() __rdtsc()

  使用CallNtPowerInformation API得到CPU频率，从而将周期数转化为毫秒数，例如如下：

  _PROCESSOR_POWER_INFORMATION info;  
  CallNTPowerInformation(11,              //query processor power information  
      NULL,                               //no input buffer  
      0,                                  //input buffer size is zero  
      &info,                              //output buffer  
      sizeof(info)                        //outbuf size  
      );  
  __int64 t_begin = GetCPUTickCount();  
  //do something  
  __int64 t_end = GetCPUTickCount();  
  millisec = ((double)t_end - (double)t_begin)/(double)info.CurrentMhz;
  

  RDTSC指令读取当前CPU的周期数，在多CPU系统中这个周期数在不同的CPU间基数不同，频率也不同。用从两个不同的CPU得到的周期数来计算会得出没有意义的值。所以需要用SetProcessAffinityMask避免进程迁移。另外，CPU的频率也会随系统供电及负荷情况有所调整。 (收起)

  2011-06-30 00:42:14   回应

  收藏

  推荐
• 

  1.2 中国象棋将帅问题

  keep_it_real (No fear.No distractions.)

  引子问题： 中国象棋将帅问题： 在一把象棋的残局中，象棋双方的将帅不可以相见，即不可以在中间没有其他棋子的情况下在同一列出现。而将、帅各被限制在己方的3*3的格子中运动。相信大家都非常熟悉象棋的玩法吧，这里就不详细说明游戏规则了。 用A、B代表将和帅，请写出一个程序，输出A、B所有合法的位置。要求在代码中只能用一个变量。 分析与解法： 这个问题的解法并不复杂。 遍历A的所有位置 遍历B的所有位... (更多)

  引子问题：

  中国象棋将帅问题：

  在一把象棋的残局中，象棋双方的将帅不可以相见，即不可以在中间没有其他棋子的情况下在同一列出现。而将、帅各被限制在己方的3*3的格子中运动。相信大家都非常熟悉象棋的玩法吧，这里就不详细说明游戏规则了。 用A、B代表将和帅，请写出一个程序，输出A、B所有合法的位置。要求在代码中只能用一个变量。

  分析与解法：

  这个问题的解法并不复杂。

  遍历A的所有位置

  遍历B的所有位置

  如果A的位置和B的位置在同一列

  输出结果

  否则 继续寻找

  地图可以用0-8表示A或B可能的9个位置

  0------1------2

  3------4------5

  6------7------8

  关键问题在于只使用一个变量来表示A和B的位置。所以可以使用位运算来解决。一个无符号字符类型的长度是1字节，也就是8位，8位可以表示2^8=256个值，对于A、B的9个位置来说足够。可以用前4位来表示A的位置情况，后4位表示B的位置情况。而4位可以表示16个数也足够表示A、B的位置情况了。

  通过位运算可以对A、B的位置进行读取和修改。

  几种基本的位运算：

  （1）& 按位与运算

  （2）| 按位或运算 "与"和"或"就不用说了吧

  （3）^ 按位异或运算 相同为假，不同为真

  （4）~ 按位取反 一元运算符

  （5）<< 按位左移 如 0000 0111 << 2 = 0001 1100,将此数左移两位相当于将此数扩大两倍。

  （6）>> 按位右移 如 0001 1000 >> 2 = 0000 0110,将此数右移两位相当于将此数缩小两倍。

  令LMASK为1111 0000，另任意一个1字节的字符型变量与其做与运算，结果右移四位，便可得到此变量的高四位的值。

  Example,

  0110 1011

  &1111 0000

  = 0110 0000 >> 4 = 0000 0110

  同理，令RMASK为0000 1111，即可得到它低四位的值。

  Ex.

  0110 1011

  & 0000 1111

  = 0000 1011

  设置1字节字符型变量，比如对高四位进行设置，先将变量与RMASK相与，将要修改的变量左移四位后于前一结果进行“异或”或“或运算”。

  Ex.将0110 1011高四位设置为1001.

  0110 1011

  & 0000 1111

  = 0000 1011 0000 1001 << 4 = 1001 0000

  ^ 1001 0000

  = 1001 1011

  同样的方法设置低四位的值。

  代码：

  #include<stdio.h>
  
  #define HALF_BITS_LENGTH    4                                                                            //一半字节的长度
  #define FULLMASK                 255                                                                        //即1111 1111
  #define LMASK                      (FULLMASK << HALF_BITS_LENGTH)                     //即1111 0000
  #define RMASK                      (FULLMASK >> HALF_BITS_LENGTH)                    //即0000 1111
  #define RSET(b, n)                  (b = (LMASK & b) ^ n)                                          //设置低四位
  #define LSET(b, n)                  (b = (RMASK & b) ^ (n << HALF_BITS_LENGTH)) //设置高四位
  #define RGET(b)                     (RMASK & b)                                                        //得到低四位
  #define LGET(b)                     ((LMASK & b) >> HALF_BITS_LENGTH)                //得到高四位
  #define GRIDW                     3                                                                          //将帅活动范围尺寸
  #define BYTE                         unsigned char
  
  int main(void)
  {
      BYTE b;     //只有一个变量
      for(LSET(b, 1); LGET(b) <= GRIDW * GRIDW; LSET(b, (LGET(b) + 1)))//从A的1位置一直找到9位置，注意自增的写法
          for(RSET(b, 1); RGET(b) <= GRIDW * GRIDW; RSET(b, (RGET(b) + 1)))//从B的1位置找到9位置
              if((LGET(b) % GRIDW) != (RGET(b) % GRIDW))   //如果不在同一列，则打印结果
                  printf("A = %d, B = %d\n", LGET(b), RGET(b));
      return 0;
  }
  

  这是个关于如何利用位运算解决问题的一个简单的运用，可以看到位运算合理地利用一个变量解决象棋将帅问题。算法本身很简单，重点是位运算的应用。

  <BOP>上还有两个更简洁的算法：

  第一个：

  #include<stdio.h>
  
  #define BYTE unsigned char
  
  int main(void)
  {
      BYTE i = 81;
      while(i--)
      {
          if((i / 9) % 3 == (i % 9) % 3)
              continue;
          printf("A = %d, B = %d\n", i /9 + 1, i%9 + 1);
      }
      return 0;
  }
  

  可以把变量i想象成一个两位九进制的变量，而i在计算机中存储的值是i的十进制表示。则i/9的计算机处理结果，即结果直接去掉小数点后部分的结果即是此九进制数的第二位，而i%9即是此九进制数的个位。本程序用此九进制数的第二位保存A的位置，个位表示B的位置。最大值为88，即为十进制的80.程序从十进制的80，即九进制的88遍历到十进制的0，即九进制的0.将符合条件的位置全部输出。

  第二个：

  #include<stdio.h>
  
  
  int main(void)
  {
      struct
      {
          unsigned char a:4;
          unsigned char b:4;
      }i;
  
  
      for(i.a = 1; i.a <= 9; i.a++)
          for(i.b = 1; i.b <= 9; i.b++)
              if(i.a % 3 != i.b % 3)
                  printf("A = %d, B = %d\n", i.a, i.b);
      return 0;
  }
  

  算法与上面的如出一辙。

  其中unsigned char a:4表示结构体中a的位域只有4位，高位用作它用。只能在结构体里使用，建议尽量少用，会破坏程序的移植性。

  当结构体中的元素的取值范围很小时，可以将几个字段按位合成一个字段来表示，起到节省内存空间的作用。

  Ex:

  #include<stdio.h>
  
  int main(void)
  {
      struct test
      {
          unsigned char a:4;
          unsigned char b:4;
      }i;
      i.a = 15;
      i.b = 10;
      printf("%d\n", sizeof(i));
  }
  

  将上面例子中的变量i的大小输出，结果为1字节。说明i.a和i.b各占4位。

  结构体是C语言中的一种常用的自定义数据结构。

  看下面的例子：

  #include<stdio.h>
  
  int main(void)
  {
      struct test
      {
          int a;
          char b;
      }i;
      printf("%d\n",sizeof(i));
  }
  

  按理说结构体变量i的大小应该是sizeof(int)+sizeof(char)，即5，而输出显示的结果为8。再看一个例子：

  #include<stdio.h>
  
  int main(void)
  {
      struct test
      {
          int a;
          char b,c;
      }i;
      printf("%d\n",sizeof(i));
  }
  

  应该是6对吧？结果还是8.这是为什么呢？

  这是因为在32位的操作系统上，操作系统组织数据是以32位(4个字节)作为一个标准，因此各种变量的size都一般都是4的倍数。而且结构体数据都是按照定义时所使用的顺序存放的，因此在第一个例子中尽管b变量只会占有一个字节，但是a + b = 5 > 4，因此第一个4个字节存放a，第二个4个字节用于存放b,这样实际上就浪费了3个字节。在第二个例子中第二个4个字节用来存放b和c。

  所以，在结构体中要注意结构体中的变量定义的顺序，不同的顺序可能会造成占用空间的不同。这在嵌入式程序设计等系统资源比较少的情况下尤为重要。比如如下两种结构体：

  #include<stdio.h>
  
  struct m
  {
      char a;
      int b;
      char c;
  }x;
  struct n
  {
      char a;
      char c;
      int b;
  }y;
  int main(void)
  {
      printf("m:%d\nn:%d\n", sizeof(x), sizeof(y));
      return 0;
  }
  

  对于结构体m来说，x变量的大小为12，而y变量的大小为8.编译器是按程序员在结构体中声明变量的顺序处理的。不当的顺序会造成空间的浪费。读者可以想到发生这样情况的原因的。所以建议声明结构体时，按照不同变量的类型，按占用空间的大小升序或降序声明会取得较好的空间占用。 (收起)

  2011-07-17 08:51:22   1回应

  收藏

  推荐
• 

  第211页

  大神布朗 (tiny bear......)

  字符串移位包含问题 /代码内容已省略/ 简单的测试一下读书笔记功能！ (更多)

  字符串移位包含问题

  public class StrRotate {
     public static void  main(String[] args) {
       String str1 = "AABBCCD";
       String str2 = "CDAA";
  		
       boolean rotate = strRotate(str1, str2);
       boolean rotate2 = strRotate2(str1, str2);
       System.out.println(rotate);
       System.out.println(rotate2);
     } 
  	
     public static boolean strRotate(String src, String des) {
        char[] charSrc = src.toCharArray();
        char[] charDes = des.toCharArray();
  		
        int len = charSrc.length;
        for(int i = 0; i < len; i++) {
           char tempchar = charSrc[0];
  	 for(int j = 0; j < len -1; j++)
  	     charSrc[j] = charSrc[j+1];
               charSrc[len - 1] = tempchar;
  	     if(String.valueOf(charSrc).indexOf(String.valueOf(charDes)) != -1) 
  	        return true;
  	 }
  	 return false;
      }
  	
      public static boolean strRotate2(String src, String des) {
         String cat = src + src;
         if(cat.indexOf(des) != -1 ) 
            return true;
         return false;
      }
  
  }
  

  简单的测试一下读书笔记功能！ (收起)

  2011-01-26 17:43:55   1人收藏   回应

  收藏

  推荐

• 

  第1页

  wltan (新年快乐)

  开放维基空间：http://goo.gl/Qn8Mg (更多)

  开放维基空间：http://goo.gl/Qn8Mg (收起)

  2011-08-01 09:50:07   回应

  收藏

  推荐
• 

  第10页

  素涵 (La Fin)

  第10页的代码在VS2008跑的时候会报错，错误出在此行 /代码内容已省略/ 错误 1 error C2061: syntax error : identifier '_TCHAR' d:\code\beautyofprogramming\code1-4\code1-4\code1-4.cpp 10 Code1-4 查到资料发现_tmain和main并无本质上的差别，于是自作主张改为了main,CPU并非单核，因此实现不了正弦曲线的效果，未免遗憾，还未尝试在x64平台上如何进行绘制 (更多)

  第10页的代码在VS2008跑的时候会报错，错误出在此行

  int _tmain(int argc, _TCHAR* argv[])
  

  错误 1 error C2061: syntax error : identifier '_TCHAR' d:\code\beautyofprogramming\code1-4\code1-4\code1-4.cpp 10 Code1-4

  查到资料发现_tmain和main并无本质上的差别，于是自作主张改为了main,CPU并非单核，因此实现不了正弦曲线的效果，未免遗憾，还未尝试在x64平台上如何进行绘制 (收起)

  2011-08-08 11:18:59   回应

  收藏

  推荐
• 

  第10页

  northfield

  今天的题目体现了节省存储空间、代码执行效率高的要求；解决一个程序问题，最简单的方法就是不考虑效率，采用穷举的方法，但是当将所有的约束用程序表达出来，程序变得高效。所以提高程序执行效率的方法：用好的方法表达约束。 (更多)

  今天的题目体现了节省存储空间、代码执行效率高的要求；解决一个程序问题，最简单的方法就是不考虑效率，采用穷举的方法，但是当将所有的约束用程序表达出来，程序变得高效。所以提高程序执行效率的方法：用好的方法表达约束。 (收起)

  2011-09-21 10:16:41   回应

  收藏

  推荐

• 

  1.2 中国象棋将帅问题

  kraft (stay hungry, stay foolish)

  有关问题 bit field究竟算不算变量，原题是说一个变量，并不是说一个字节的变量存储空间，最后的例子使用了两个bit field, 我觉得就是两个变量。 另外 单独针对这一道题还有不用变量的解决办法 1 人脑穷举，挨个写出来 2 写个生成程序，输出穷举的程序 (更多)

  有关问题

  bit field究竟算不算变量，原题是说一个变量，并不是说一个字节的变量存储空间，最后的例子使用了两个bit field, 我觉得就是两个变量。

  另外 单独针对这一道题还有不用变量的解决办法

  1 人脑穷举，挨个写出来

  2 写个生成程序，输出穷举的程序 (收起)

  2011-11-29 19:37:05   回应

  收藏

  推荐
• 

  别被阶乘吓到

  小丽

  趁着京东特价，买了一堆的书，其中就有这本《编程之美》，随手翻了翻，就看到这个了，本来以为这种倾向于算法的书会比较复杂，结果跟想象中的复杂程度相差很多，很顺利的就看了一点，心里甚是安慰。 (更多)

  趁着京东特价，买了一堆的书，其中就有这本《编程之美》，随手翻了翻，就看到这个了，本来以为这种倾向于算法的书会比较复杂，结果跟想象中的复杂程度相差很多，很顺利的就看了一点，心里甚是安慰。

  (收起)

  2011-11-04 13:27:08   回应

  收藏

  推荐
• 

  中国象棋将帅问题

  藿香正气 (八表同昏，平陆成江。)

  /代码内容已省略/ (更多)

  
  struct {
        unsigned char a:4;
        unsigned char b:4;
  } i;
  
  for (i.a = 1; i.a <= 9; i.a++)
       for (i.b = 1; i.b = 9; i.b++)
            if (i.a %3 != i.b % 3)
                printf("A = %d, B = %d\n", i.a, i.b);
  
  

  (收起)

  2011-09-22 11:14:08   回应

  收藏

  推荐