博客园-Use after Think

CPU占用率算法

floodpeak — Tue, 15 Jul 2008 10:11:00 +0800

阅读: 675 评论: 0 作者: floodpeak 发表于 2008-07-15 10:11 原文链接

    windows2000任务管理器可以看到CPU的占用率。
    CPU是不能间断运行的，只要CPU上电就要运行指令，即使无事可做，也要执行NOP操作。所以windows的CPU占用率低并不是指CPU目前无事可做，而是指CPU可以从当前状态中腾出多少时间来做用户的事情。
    在多任务操作系统中的进程一般都实现了优先权算法，抢占式实时操作系统的高优先权进程能够立即抢占低优先权进程的CPU，而分时操作系统则一般等到当前进程的CPU时间片用完后再调度，但无论实时系统还是分时系统，高优先权进程在分配CPU时间上都比低优先权的进程占优势。
    可以定义PRIORITY_HIGHEST为操作系统定义的最高优先权，PRIORITY_LOWEST为操作系统定义的最低优先权，一般PRIORITY_HIGHEST的值就是0，PRIORITY_LOWEST是大于0的一个数，虽然这样会或多或少混淆HIGHEST和LOWEST的意思。在windows中PRIORITY_HIGHEST为0，是系统进程；PRIORITY_LOWEST不知道是多少，但一定是空闲进程，就是任务管理器中看到System Idle Process进程。在比PRIORITY_LOWEST低一级的（PRIORITY_LOWEST-1)有一个统计进程，姑且叫OSStat，就是用来统计CPU占用率的。
    在OS初始化时一定有一段时间是只有系统进程在运行的，因为初始化还没完成，没开始调度用户进程。这个时候OS可以对CPU进行计时，计算CPU一秒内可以执行多少次加法，比如可以写这样的代码

1 OSIdleCtr = 0L; /* Clear idle counter */
2 OSTimeDly(OS_TICKS_PER_SEC); /* Determine MAX. idle counter value for 1 second */
3 OSIdleCtrMax = OSIdleCtr; /* Store maximum idle counter count in 1 second */
4

其中OSTimeDly是使系统所有进程（除Idle进程外）都挂起OS_TICKS_PER_SEC个时间片，而OS_TICKS_PER_SEC的值可以通过晶振的频率直接计算得到指令周期再由CPU划分，也可以通过CPU提供的指令得到指令周期再由CPU划分。
在Idle进程中加入这样的代码

OSIdleCtr++;

    到这里OSTimeDly(OS_TICKS_PER_SEC)的意义就很明确了，由于挂起其他进程，这样系统中只有Idle在运行，Idle对OSIdleCtr累加就不会被其他更高优先级的进程中断而造成计算不准确。
    如此就得到了1秒中Idle进程可以执行的最大加法次数，为什么Idle进程对OSIdleCtr的累加就是CPU一秒内最大加法次数呢，因为其他进程都被挂起了1秒，在这1秒内CPU只执行Idle的代码嘛，所以Idle对OSIdleCtr的累加可以代表一个系统的最大执行能力，不可能有其他方式可以在1秒内使OSIdleCtr的值累加到超过这个值。
    另外Idle的其他代码不会影响OSIdleCtr的准确性，因为可以把定义‘系统执行加法的最大次数’改成‘系统执行Idle过程的最大次数’，意义是不变的，仍然代表了CPU的执行能力。
    事实上Idle也是一个进程，所以也参与进程的调度算法，既然已经在Idle中加入了OSIdleCtr累加的算法，那么系统只需要在每秒钟中断的时候将OSIdleCtr初始化为0，则在系统正常运行的时候（用户进程已经开始）1秒钟内Idle对OSIdleCtr的累加就可以看成在普通用户状态下的CPU在1秒内的处理能力，因为这个时候用户进程已经开始参与调度，而Idle进程是系统中最低优先级的进程，其只在无用户任务的情况下调入，只要用户有其他任务，Idle都会挂起来等待，所以这个时候Idle对OSIdleCtr的累加就代表了在当前任务压力下CPU的空闲程度。因为OSIdleCtr每秒钟被复0一次，所以CPU的占用率自然也可以写成
    CPUUsage％=100*(1-OSIdleCtr/OSIdleCtrMax)这条公式的计算写在OSStat里，就形成了windows的CPU占用率形式。
    事实上，上面讨论的算法是ucos2系统的CPU占用率算法，ucos2是一个开源实时操作系统，通常用在嵌入式CPU中。

转载作者：Lingch
摘自：http://blog.csdn.net/sboom/archive/2005/12/25/561412.aspx

评论: 0　查看评论　发表评论

最新新闻：
· Yahoo脑震荡关闭服务汇总贴(2010-02-10 12:06)
· 2003年微软遭遇iTunes：我们彻底晕头转向了(2010-02-10 12:06)
· 百度数据能被“作弊”软件篡改？百度:追究侵权(2010-02-10 11:52)
· Ksplice为Linux提供永远不用重启服务(2010-02-10 11:51)
· 视频网站2010年格局之变：七成企业将被淘汰(2010-02-10 11:48)

编辑推荐：Google社会化产品Buzz发布会实录

网站导航：博客园首页个人主页新闻闪存小组博问社区知识库

如何摆脱写文档时截屏的困扰

floodpeak — Fri, 20 Jun 2008 10:56:00 +0800

阅读: 2635 评论: 16 作者: floodpeak 发表于 2008-06-20 10:56 原文链接

    终于可以写博客了，一个月来，第一次有时间静下心来。
    一个月中，我的全部精力都投入到了一件事：投标。前面的大部分时间用来编写程序demo，最后三天用来写标书。
    大家都会有这样的经验：纯文字的东西一会儿就会使人昏昏欲睡，图文并茂才会使我们保持良好的阅读欲望。可见在文字描述的过程中，图片的加入举足轻重。
    技术文档的插图大部分都是程序运行时的截图，此时能否快速便捷的进行图片截取就成了文档成文速度的重要影响因素。
    传统的截屏方法是利用键盘上的PrintScreen键，按下该键后当前屏幕被存储到剪贴板中，在画图工具中进行粘贴就可以进行屏幕图像的编辑了。此种方式非常简便，但也有一些方面不尽如人意。
    1）程序运行的时候，鼠标的位置是一个比较重要的信息，所以自然希望截取的图片中含有鼠标，但是直接使用PrintScreen键是不会含有鼠标的，在网上搜索了一下，有文章说按住Windows键再加上PrintScreen可以含有鼠标，在我机器上的试验结果是与只按PrintScreen结果无异，如有园友知道方法请不吝赐教。
    2）程序的操作往往具有一定的连贯性，为了说明程序的运行流程需要截取一系列图像，这样问题就出现了，由于截取的图片是保存到剪贴板中的，每次截屏都会覆盖掉上一次的截屏，所以连续截屏在技术上是达不到的，不得不在截取完一幅图像后进入图片处理程序把刚刚截的图保存下来再回到原来的程序中，经过这一阵鼓捣，严重打乱了操作时的思路。
    另一种方法是利用截屏工具。我常用的是qq，别的没有使用过所以没有发言权。Qq的截屏方式是在屏幕上画上一个框，然后保存框中的图像。这种方式使得想保存鼠标的位置化为泡影，上面提到的第二条也会因为要切入到第三方截屏程序而照旧存在。
    下面就来到了我的推荐方法，选用此种方式大大提高了截屏速度，更重要的是解决了上面提出的两个问题。
    解决的思路是这样的，首先开启一个录制屏幕程序，然后开始进行操作，操作完成后停止录制程序，此时你的整个操作过程已经被保存到了一个视频文件中。打开视频文件，把你需要的帧摘出来进行编辑就可以了。做到这些需要一些软件的支持，下面是我的推荐：

    屏幕录制程序：HyperCam 下载地址
    视频播放程序：暴风影音  下载地址
    图片编辑程序：PhotoShop CS3

    启动HyperCam，选择录像输出路径，选择录像范围，按下F2开始录像，这时你可以开始操作你的程序，不必考虑截屏问题，当一个完整的功能演示完毕，再次按下F2停止录像，此时这段操作的录像就会保存到你的输出路径中。
    在暴风影音中打开该视频文件，当播放过程中出现需要截取的帧时，暂停下来，按下F5，此帧就会被存入我的文档中，在视频播放器中会出现存放的路径，当然如果希望选定存放位置，可以在文件->截屏中选择，下次再按F5就会将截图存到选定的位置下了。
图片被存下来后再进行编辑，就可以放到文档中了。
    下面是我用这种方法制作的一幅图像，在此次投标文档中，这样的图像共有三十余幅，每幅大致需要五次截屏，如果采用传统方法……

评论: 16　查看评论　发表评论

编辑推荐：Google社会化产品Buzz发布会实录

网站导航：博客园首页个人主页新闻闪存小组博问社区知识库

第六回：寻找交点，离胜利就剩一步之纽带

floodpeak — Wed, 07 May 2008 12:30:00 +0800

阅读: 1524 评论: 15 作者: floodpeak 发表于 2008-05-07 12:30 原文链接

    终于，我们进入了算法的核心地带。
    在《第二回：漫谈新思路，是我们自己干的时候了》中我们说到整个算法的处理过程包括三个大块：寻找辅助线、寻找交点、寻找三角形。交点的寻找及其结果的组织，是能否找到三角形的关键，因而本回会用较长的篇幅把这个过程阐述清楚，为后文打下坚实的基础。
    由于内容实在过多，为了避免冗长造成的疲倦，我将本回分成两个部分。本文的主题是介绍寻找交点和寻找三角形两个大块的纽带——二维表Point2Table，还记得《第二回：漫谈新思路，是我们自己干的时候了》“二、寻找相交点”小节中提到的二维表吗，没错，就是它！

一、类图和代码

这里是整个类的代码，行数逾百，后面会进行逐段的分析。

Point2Table
  1Public Class Point2Table
  2
  3    Private Class PointIndexWithT
  4            Implements IComparable
  5
  6        Private _index As Integer '在VertexBuffer中的索引
  7        Private t As Decimal
  8
  9      Public Sub New(ByVal ind As Integer, ByVal t As Decimal)
10            Me._index = ind
11            Me.t = t
12        End Sub
13
14      Public ReadOnly Property Index() As Integer
15            Get
16                Return Me._index
17            End Get
18        End Property
19
20      Public Function CompareTo(ByVal obj As Object) As Integer Implements System.IComparable.CompareTo
21            If Not (TypeOf obj Is PointIndexWithT) Then
22                MsgBox("PointWithU中传入参数有误")
23                Return 0
24            End If
25            Dim pwu As PointIndexWithT = CType(obj, PointIndexWithT)
26            Return Me.t.CompareTo(pwu.t)
27        End Function
28    End Class
29
30    Private rowsForSort As New List(Of List(Of PointIndexWithT))
31    Private rows As New List(Of List(Of Integer))
32    Private vb As New VertexBuffer
33    Private ib As IndexBuffer = Nothing
34
35  Public ReadOnly Property IndexBuffer() As IndexBuffer
36        Get
37            If (ib Is Nothing) Then
38                ib = New IndexBuffer
39                Dim qs As New QuadrangleSeeker(Me)
40                Dim quadrangles As List(Of Integer) = Nothing
41                Me.Sort() '对表进行排序
42                quadrangles = qs.getQuadrangles()
43                For i As Integer = 0 To quadrangles.Count - 1 Step 4
44                    If (quadrangles(i + 2) <> quadrangles(i + 3)) Then
45                        ib.add(quadrangles(i))
46                        ib.add(quadrangles(i + 2))
47                        ib.add(quadrangles(i + 3))
48                    End If
49                    If (quadrangles(i) <> quadrangles(i + 1)) Then
50                        ib.add(quadrangles(i + 3))
51                        ib.add(quadrangles(i + 1))
52                        ib.add(quadrangles(i))
53                    End If
54                Next
55            End If
56            Return Me.ib
57        End Get
58    End Property
59
60  Public ReadOnly Property VertexBuffer() As VertexBuffer
61        Get
62            Return Me.vb
63        End Get
64    End Property
65
66  Default Public ReadOnly Property Item(ByVal i As Integer) As List(Of Integer)
67        Get
68            If (i < rowsForSort.Count AndAlso i >= 0) Then
69                Return rows(i)
70            Else
71                MsgBox("数组越界")
72                Return Nothing
73            End If
74        End Get
75    End Property
76
77  Public ReadOnly Property Count() As Integer
78        Get
79            Return Me.rowsForSort.Count
80        End Get
81    End Property
82
83  Public Sub addRow()
84        rowsForSort.Add(New List(Of PointIndexWithT))
85    End Sub
86
87  Public Sub addPoint(ByVal point As Point2, ByVal t As Decimal, ByVal u As Decimal)
88        If (u < 0 OrElse u > 1) Then    '没有和线段相交
89            Return
90        End If
91        Dim index As Integer = Me.vb.add(point)
92        rowsForSort(rowsForSort.Count - 1).Add(New PointIndexWithT(index, t))
93    End Sub
94
95  Public Sub removePoint(ByVal rowIndex As Integer, ByVal columnIndex As Integer)
96        Me.rowsForSort(rowIndex).RemoveAt(columnIndex)
97    End Sub
98
99  Public Sub Sort()
100        Me.rows = New List(Of List(Of Integer))
101        For Each row As List(Of PointIndexWithT) In rowsForSort
102            row.Sort()      '按照t进行排序
103            Dim list As New List(Of Integer)        '实例化一行
104            For Each piwt As PointIndexWithT In row '遍历行中每一个带T的点索引
105                list.Add(piwt.Index)                '将索引值添加到列表中
106            Next
107            Me.rows.Add(list)   '将列表添加进行中
108        Next
109    End Sub
110End Class
111

二、两个缓冲的宿主
容易看出属性中的IndexBuffer和VertexBuffer正是上篇文章中设计的数据结构，客户代码可以直接调用这两个只读属性获得处理完毕的两个缓冲，进而加以利用，所以说Point2Table除了是寻找交点和寻找三角形的纽带外，还有另一重身份，那就是整个算法和客户代码的纽带，这里是算法的出口。在调用IndexBuffer属性时，程序会去调用寻找三角形的逻辑，这部分内容我们将在下一回中详细介绍。在调用VertexBuffer属性时，程序直接返回顶点缓冲vb，这个缓冲是用户在寻找交点的过程中填充的，这部分内容我们将在本回的下一部分中详细介绍。

三、嵌套类PointIndexWithT
在上面的类图中，有一个可爱的棒糖，棒糖下面是一个名字古怪的私有嵌套类PointIndexWithT，翻译过来就是带着T的点索引，索引就是上文VertexBuffer中的索引，T就是《第四回：掌握数学工具，没个好帮手怎么行》“三、用向量描述直线”小节中提到的T。下图可以直观的看出Index和T的含义：

该类的引入只有一个目的，将某条扫描线上的所有交点从左至右进行排序，注意一点，这里参与排序的是T，而排序的实体（我们要的结果）是点的索引。

1 Public Function CompareTo(ByVal obj As Object) As Integer Implements System.IComparable.CompareTo
2        If Not (TypeOf obj Is PointIndexWithT) Then
3            MsgBox("PointWithU中传入参数有误")
4            Return 0
5        End If
6        Dim pwu As PointIndexWithT = CType(obj, PointIndexWithT)
7        Return Me.t.CompareTo(pwu.t)
8    End Function

上面的这段代码实现了IComparable接口的CompateTo方法，目的是让PointIndexWithT的数组可以使用框架提供的Sort函数。代码很简单，只是简单的比较了一下T，我们已经说过了，T就是为了排序而生。如果你还不是太清楚，没关系，下面我就用一个例子来说明。

四、例说排序
下图是三角剖分一个凹多边形的过程，图中的VB代表VertexBuffer，也就是顶点缓冲。每一行后面会有几个矩形框，每个矩形框代表一个加入到Point2Table的点，框中上面一个值代表Index，下面的值为该点的T。

上图中的T只是一个示意值，请不要用尺子丈量。

五、排序的实现
有了上面直观的了解，相信下面的内容很容易理解。

Private rowsForSort As New List(Of List(Of PointIndexWithT))
Private rows As New List(Of List(Of Integer))

1Public Sub Sort()
2        Me.rows = New List(Of List(Of Integer))
3        For Each row As List(Of PointIndexWithT) In rowsForSort
4            row.Sort()      '按照t进行排序
5            Dim list As New List(Of Integer)        '实例化一行
6            For Each piwt As PointIndexWithT In row '遍历行中每一个带T的点索引
7                list.Add(piwt.Index)                '将索引值添加到列表中
8            Next
9            Me.rows.Add(list)   '将列表添加进行中
10        Next
11  End Sub

顾名思义，rowsForSort就是为了排序而建立的行集合，这里的一行指的是一条扫描线，从代码中可以看到该字段实际上是一个PointIndexWithT的参差二维数组（二维表）。你一定发现了rows的存在，它和rowsForSort的结构完全相同，从Sort方法中可以看到rows中保存的是排好了序后rowsForSort中的所有索引，换句话说，它将用于排序的T去除了。引入这样一个字段显然浪费了一些空间，因为rowsForSort完全可以担当起rows的职责，但是由于在寻找三角形的过程中需要对rows进行一些处理（删除某个点），因此如果直接将rowsForSort传过去将会造成不可逆转的删除，因而这里选择了克隆一份新数据的变通方法。

1Public Sub addRow()
2        rowsForSort.Add(New List(Of PointIndexWithT))
3End Sub
4
5Public Sub addPoint(ByVal point As Point2, ByVal t As Decimal, ByVal u As Decimal)
6        If (u < 0 OrElse u > 1) Then    '没有和线段相交
7            Return
8        End If
9        Dim index As Integer = Me.vb.add(point)
10        rowsForSort(rowsForSort.Count - 1).Add(New PointIndexWithT(index, t))
11End Sub

addRow和addPoint是操纵rowsForSort的两个方法。其中addRow是为二维表添加一行，addPoint则是在新添加的行中添加一个交点，注意addPoint的三个参数，第一个是一个二维点对象，第二个是上文提到的用于排序的T，第三个是《第四回：掌握数学工具，没个好帮手怎么行》 “四、射线与线段的交点”小节中提到的U，我们已经知道，如果U没有落在[0，1]的区间内，该点是不在线段上的，因而也是不会被添加到二维表中的。

二维表是一个容纳交点的数据结构，同时它可以根据每个交点的T来对表中每行上的交点进行排序以供寻找三角形之用，因而该类是寻找交点和寻找三角形两个大块的纽带，又由于该类提供了算法的出口（两个缓冲），故而该类还是整个算法和用户代码之间的纽带。上面的种种奠定了该类在整个算法中的地位，是整个算法三个核心类之一。下一篇文章，也就是本回的第二部分，将介绍另一个核心类RegionToTriangle，正是该类的辛勤工作填满了Point2Table。

评论: 15　查看评论　发表评论

编辑推荐：Google社会化产品Buzz发布会实录

网站导航：博客园首页个人主页新闻闪存小组博问社区知识库

备忘录专题首页

floodpeak — Tue, 06 May 2008 21:47:00 +0800

阅读: 137 评论: 0 作者: floodpeak 发表于 2008-05-06 21:47 原文链接

本专题将一些备查的资料收集起来，以备后用。看到小logo了吗？对，放飞大脑。

目录：
参考文献的各种字母的含义

评论: 0　查看评论　发表评论

编辑推荐：Google社会化产品Buzz发布会实录

网站导航：博客园首页个人主页新闻闪存小组博问社区知识库

转载系列首页

floodpeak — Sun, 04 May 2008 22:01:00 +0800

阅读: 162 评论: 0 作者: floodpeak 发表于 2008-05-04 22:01 原文链接

    在这个系列中，我会将一些在网上发现的好文章收藏过来，这其中包括技术方面的、生活方面的甚至是科普方面的，谁知道呢?
    虽然是转载别人的文章，我也会力求精益求精，将原文的谬误更正过来，有必要的话我会进行重新排版，甚至添加一些新的图片，当然我会尽量尊重原文。
    本系列所转载的所有文章都会在显著位置注明文章来源及作者，如有不妥之处请与我联系。

	起始时间：	2008年5月1日
	当前数量：	5

	起始时间：	2008年5月5日
	当前数量：	1

评论: 0　查看评论　发表评论

编辑推荐：Google社会化产品Buzz发布会实录

网站导航：博客园首页个人主页新闻闪存小组博问社区知识库

吐血三八二十四

floodpeak — Fri, 02 May 2008 19:46:00 +0800

阅读: 285 评论: 6 作者: floodpeak 发表于 2008-05-02 19:46 原文链接

第一题：3，8，3，8
第二题：5，5，5，1
第三题：0，0，0，0

别瞪眼，你没看错，努力想想吧，回复索要答案

评论: 6　查看评论　发表评论

编辑推荐：Google社会化产品Buzz发布会实录

网站导航：博客园首页个人主页新闻闪存小组博问社区知识库

澄清P问题、NP问题、NPC问题的概念

floodpeak — Fri, 02 May 2008 16:22:00 +0800

阅读: 1232 评论: 14 作者: floodpeak 发表于 2008-05-02 16:22 原文链接

    你会经常看到网上出现“这怎么做，这不是NP问题吗”、“这个只有搜了，这已经被证明是NP问题了”之类的话。你要知道，大多数人此时所说的NP问题其实都是指的NPC问题。他们没有搞清楚NP问题和NPC问题的概念。NP问题并不是那种“只有搜才行”的问题，NPC问题才是。好，行了，基本上这个误解已经被澄清了。下面的内容都是在讲什么是P问题，什么是NP问题，什么是NPC问题，你如果不是很感兴趣就可以不看了。接下来你可以看到，把NP问题当成是NPC问题是一个多大的错误。
    还是先用几句话简单说明一下时间复杂度。时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。也就是说，对于高速处理数据的计算机来说，处理某一个特定数据的效率不能衡量一个程序的好坏，而应该看当这个数据的规模变大到数百倍后，程序运行时间是否还是一样，或者也跟着慢了数百倍，或者变慢了数万倍。不管数据有多大，程序处理花的时间始终是那么多的，我们就说这个程序很好，具有O(1)的时间复杂度，也称常数级复杂度；数据规模变得有多大，花的时间也跟着变得有多长，这个程序的时间复杂度就是O(n)，比如找n个数中的最大值；而像冒泡排序、插入排序等，数据扩大2倍，时间变慢4倍的，属于O(n^2)的复杂度。还有一些穷举类的算法，所需时间长度成几何阶数上涨，这就是O(a^n)的指数级复杂度，甚至O(n!)的阶乘级复杂度。不会存在O(2*n^2)的复杂度，因为前面的那个“2”是系数，根本不会影响到整个程序的时间增长。同样地，O(n^3+n^2)的复杂度也就是O(n^3)的复杂度。因此，我们会说，一个O(0.01*n^3)的程序的效率比O(100*n^2)的效率低，尽管在n很小的时候，前者优于后者，但后者时间随数据规模增长得慢，最终O(n^3)的复杂度将远远超过O(n^2)。我们也说，O(n^100)的复杂度小于O(1.01^n)的复杂度。
    容易看出，前面的几类复杂度被分为两种级别，其中后者的复杂度无论如何都远远大于前者：一种是O(1),O(log(n)),O(n^a)等，我们把它叫做多项式级的复杂度，因为它的规模n出现在底数的位置；另一种是O(a^n)和O(n!)型复杂度，它是非多项式级的，其复杂度计算机往往不能承受。当我们在解决一个问题时，我们选择的算法通常都需要是多项式级的复杂度，非多项式级的复杂度需要的时间太多，往往会超时，除非是数据规模非常小。
    自然地，人们会想到一个问题：会不会所有的问题都可以找到复杂度为多项式级的算法呢？很遗憾，答案是否定的。有些问题甚至根本不可能找到一个正确的算法来，这称之为“不可解问题”(Undecidable Decision Problem)，The Halting Problem就是一个著名的不可解问题。再比如，输出从1到n这n个数的全排列。不管你用什么方法，你的复杂度都是阶乘级，因为你总得用阶乘级的时间打印出结果来。有人说，这样的“问题”不是一个“正规”的问题，正规的问题是让程序解决一个问题，输出一个“YES”或“NO”（这被称为判定性问题），或者一个什么什么的最优值（这被称为最优化问题）。那么，根据这个定义，我也能举出一个不大可能会有多项式级算法的问题来：Hamilton回路。问题是这样的：给你一个图，问你能否找到一条经过每个顶点一次且恰好一次（不遗漏也不重复）最后又走回来的路（满足这个条件的路径叫做Hamilton回路）。这个问题现在还没有找到多项式级的算法。事实上，这个问题就是我们后面要说的NPC问题。
    下面引入P类问题的概念：如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题。P是英文单词多项式的第一个字母。哪些问题是P类问题呢？通常NOI和NOIP不会出不属于P类问题的题目。我们常见到的一些信息奥赛的题目都是P问题。道理很简单，一个用穷举换来的非多项式级时间的超时程序不会涵盖任何有价值的算法。
    接下来引入NP问题的概念。这个就有点难理解了，或者说容易理解错误。在这里强调（回到我竭力想澄清的误区上），NP问题不是非P类问题。NP问题是指可以在多项式的时间里验证一个解的问题。NP问题的另一个定义是，可以在多项式的时间里猜出一个解的问题。比方说，我RP很好，在程序中需要枚举时，我可以一猜一个准。现在某人拿到了一个求最短路径的问题，问从起点到终点是否有一条小于100个单位长度的路线。它根据数据画好了图，但怎么也算不出来，于是来问我：你看怎么选条路走得最少？我说，我RP很好，肯定能随便给你指条很短的路出来。然后我就胡乱画了几条线，说就这条吧。那人按我指的这条把权值加起来一看，嘿，神了，路径长度98，比100小。于是答案出来了，存在比100小的路径。别人会问他这题怎么做出来的，他就可以说，因为我找到了一个比100小的解。在这个题中，找一个解很困难，但验证一个解很容易。验证一个解只需要O(n)的时间复杂度，也就是说我可以花O(n)的时间把我猜的路径的长度加出来。那么，只要我RP好，猜得准，我一定能在多项式的时间里解决这个问题。我猜到的方案总是最优的，不满足题意的方案也不会来骗我去选它。这就是NP问题。当然有不是NP问题的问题，即你猜到了解但是没用，因为你不能在多项式的时间里去验证它。下面我要举的例子是一个经典的例子，它指出了一个目前还没有办法在多项式的时间里验证一个解的问题。很显然，前面所说的Hamilton回路是NP问题，因为验证一条路是否恰好经过了每一个顶点非常容易。但我要把问题换成这样：试问一个图中是否不存在Hamilton回路。这样问题就没法在多项式的时间里进行验证了，因为除非你试过所有的路，否则你不敢断定它“没有Hamilton回路”。
    之所以要定义NP问题，是因为通常只有NP问题才可能找到多项式的算法。我们不会指望一个连多项式地验证一个解都不行的问题存在一个解决它的多项式级的算法。相信读者很快明白，信息学中的号称最困难的问题——“NP问题”，实际上是在探讨NP问题与P类问题的关系。
    很显然，所有的P类问题都是NP问题。也就是说，能多项式地解决一个问题，必然能多项式地验证一个问题的解——既然正解都出来了，验证任意给定的解也只需要比较一下就可以了。关键是，人们想知道，是否所有的NP问题都是P类问题。我们可以再用集合的观点来说明。如果把所有P类问题归为一个集合P中，把所有NP问题划进另一个集合NP中，那么，显然有P属于NP。现在，所有对NP问题的研究都集中在一个问题上，即究竟是否有P=NP？通常所谓的“NP问题”，其实就一句话：证明或推翻P=NP。
    NP问题一直都是信息学的巅峰。巅峰，意即很引人注目但难以解决。在信息学研究中，这是一个耗费了很多时间和精力也没有解决的终极问题，好比物理学中的大统一和数学中的歌德巴赫猜想等。
    目前为止这个问题还“啃不动”。但是，一个总的趋势、一个大方向是有的。人们普遍认为，P=NP不成立，也就是说，多数人相信，存在至少一个不可能有多项式级复杂度的算法的NP问题。人们如此坚信P≠NP是有原因的，就是在研究NP问题的过程中找出了一类非常特殊的NP问题叫做NP-完全问题，也即所谓的NPC问题。C是英文单词“完全”的第一个字母。正是NPC问题的存在，使人们相信P≠NP。下文将花大量篇幅介绍NPC问题，你从中可以体会到NPC问题使P=NP变得多么不可思议。
    为了说明NPC问题，我们先引入一个概念——约化(Reducibility，有的资料上叫“归约”)。
    简单地说，一个问题A可以约化为问题B的含义即是，可以用问题B的解法解决问题A，或者说，问题A可以“变成”问题B。《算法导论》上举了这么一个例子。比如说，现在有两个问题：求解一个一元一次方程和求解一个一元二次方程。那么我们说，前者可以约化为后者，意即知道如何解一个一元二次方程那么一定能解出一元一次方程。我们可以写出两个程序分别对应两个问题，那么我们能找到一个“规则”，按照这个规则把解一元一次方程程序的输入数据变一下，用在解一元二次方程的程序上，两个程序总能得到一样的结果。这个规则即是：两个方程的对应项系数不变，一元二次方程的二次项系数为0。按照这个规则把前一个问题转换成后一个问题，两个问题就等价了。同样地，我们可以说，Hamilton回路可以约化为TSP问题(Travelling Salesman Problem，旅行商问题)：在Hamilton回路问题中，两点相连即这两点距离为0，两点不直接相连则令其距离为1，于是问题转化为在TSP问题中，是否存在一条长为0的路径。Hamilton回路存在当且仅当TSP问题中存在长为0的回路。
    “问题A可约化为问题B”有一个重要的直观意义：B的时间复杂度高于或者等于A的时间复杂度。也就是说，问题A不比问题B难。这很容易理解。既然问题A能用问题B来解决，倘若B的时间复杂度比A的时间复杂度还低了，那A的算法就可以改进为B的算法，两者的时间复杂度还是相同。正如解一元二次方程比解一元一次方程难，因为解决前者的方法可以用来解决后者。
    很显然，约化具有一项重要的性质：约化具有传递性。如果问题A可约化为问题B，问题B可约化为问题C，则问题A一定可约化为问题C。这个道理非常简单，就不必阐述了。
    现在再来说一下约化的标准概念就不难理解了：如果能找到这样一个变化法则，对任意一个程序A的输入，都能按这个法则变换成程序B的输入，使两程序的输出相同，那么我们说，问题A可约化为问题B。
    当然，我们所说的“可约化”是指的可“多项式地”约化(Polynomial-time Reducible)，即变换输入的方法是能在多项式的时间里完成的。约化的过程只有用多项式的时间完成才有意义。
    好了，从约化的定义中我们看到，一个问题约化为另一个问题，时间复杂度增加了，问题的应用范围也增大了。通过对某些问题的不断约化，我们能够不断寻找复杂度更高，但应用范围更广的算法来代替复杂度虽然低，但只能用于很小的一类问题的算法。再回想前面讲的P和NP问题，联想起约化的传递性，自然地，我们会想问，如果不断地约化上去，不断找到能“通吃”若干小NP问题的一个稍复杂的大NP问题，那么最后是否有可能找到一个时间复杂度最高，并且能“通吃”所有的NP问题的这样一个超级NP问题？答案居然是肯定的。也就是说，存在这样一个NP问题，所有的NP问题都可以约化成它。换句话说，只要解决了这个问题，那么所有的NP问题都解决了。这种问题的存在难以置信，并且更加不可思议的是，这种问题不只一个，它有很多个，它是一类问题。这一类问题就是传说中的NPC问题，也就是NP-完全问题。NPC问题的出现使整个NP问题的研究得到了飞跃式的发展。我们有理由相信，NPC问题是最复杂的问题。再次回到全文开头，我们可以看到，人们想表达一个问题不存在多项式的高效算法时应该说它“属于NPC问题”。此时，我的目的终于达到了，我已经把NP问题和NPC问题区别开了。到此为止，本文已经写了近5000字了，我佩服你还能看到这里来，同时也佩服一下自己能写到这里来。
    NPC问题的定义非常简单。同时满足下面两个条件的问题就是NPC问题。首先，它得是一个NP问题；然后，所有的NP问题都可以约化到它。证明一个问题是NPC问题也很简单。先证明它至少是一个NP问题，再证明其中一个已知的NPC问题能约化到它（由约化的传递性，则NPC问题定义的第二条也得以满足；至于第一个NPC问题是怎么来的，下文将介绍），这样就可以说它是NPC问题了。
    既然所有的NP问题都能约化成NPC问题，那么只要任意一个NPC问题找到了一个多项式的算法，那么所有的NP问题都能用这个算法解决了，NP也就等于P了。因此，给NPC找一个多项式算法太不可思议了。因此，前文才说，“正是NPC问题的存在，使人们相信P≠NP”。我们可以就此直观地理解，NPC问题目前没有多项式的有效算法，只能用指数级甚至阶乘级复杂度的搜索。
    顺便讲一下NP-Hard问题。NP-Hard问题是这样一种问题，它满足NPC问题定义的第二条但不一定要满足第一条（就是说，NP-Hard问题要比NPC问题的范围广）。NP-Hard问题同样难以找到多项式的算法，但它不列入我们的研究范围，因为它不一定是NP问题。即使NPC问题发现了多项式级的算法，NP-Hard问题有可能仍然无法得到多项式级的算法。事实上，由于NP-Hard放宽了限定条件，它将有可能比所有的NPC问题的时间复杂度更高从而更难以解决。
    不要以为NPC问题是一纸空谈。NPC问题是存在的。确实有这么一个非常具体的问题属于NPC问题。下文即将介绍它。
    下文即将介绍逻辑电路问题。这是第一个NPC问题。其它的NPC问题都是由这个问题约化而来的。因此，逻辑电路问题是NPC类问题的“鼻祖”。
    逻辑电路问题是指的这样一个问题：给定一个逻辑电路，问是否存在一种输入使输出为True。
    什么叫做逻辑电路呢？一个逻辑电路由若干个输入，一个输出，若干“逻辑门”和密密麻麻的线组成。看下面一例，不需要解释你马上就明白了。

这是个较简单的逻辑电路，当输入1、输入2、输入3分别为True、True、False或False、True、False时，输出为True。
有输出无论如何都不可能为True的逻辑电路吗？有。下面就是一个简单的例子。

    上面这个逻辑电路中，无论输入是什么，输出都是False。我们就说，这个逻辑电路不存在使输出为True的一组输入。
    回到上文，给定一个逻辑电路，问是否存在一种输入使输出为True，这即逻辑电路问题。
    逻辑电路问题属于NPC问题。这是有严格证明的。它显然属于NP问题，并且可以直接证明所有的NP问题都可以约化到它（不要以为NP问题有无穷多个将给证明造成不可逾越的困难）。证明过程相当复杂，其大概意思是说任意一个NP问题的输入和输出都可以转换成逻辑电路的输入和输出（想想计算机内部也不过是一些0和1的运算），因此对于一个NP问题来说，问题转化为了求出满足结果为True的一个输入（即一个可行解）。
    有了第一个NPC问题后，一大堆NPC问题就出现了，因为再证明一个新的NPC问题只需要将一个已知的NPC问题约化到它就行了。后来，Hamilton回路成了NPC问题，TSP问题也成了NPC问题。现在被证明是NPC问题的有很多，任何一个找到了多项式算法的话所有的NP问题都可以完美解决了。因此说，正是因为NPC问题的存在，P=NP变得难以置信。P=NP问题还有许多有趣的东西，有待大家自己进一步的挖掘。攀登这个信息学的巅峰是我们这一代的终极目标。现在我们需要做的，至少是不要把概念弄混淆了。

转载作者：Matrix67
摘自：http://matrix-67.spaces.live.com/blog/cns!420b543611ba4e21!621.entry

评论: 14　查看评论　发表评论

编辑推荐：Google社会化产品Buzz发布会实录

网站导航：博客园首页个人主页新闻闪存小组博问社区知识库

经典文章专题首页

floodpeak — Thu, 01 May 2008 21:21:00 +0800

阅读: 177 评论: 0 作者: floodpeak 发表于 2008-05-01 21:21 原文链接

    本专题收录各个方面的经典文章，并不拘泥于技术，当然还是以技术文章为主的。当某些收录的文章可以构成一个专题时，就会将这些文章分离出去形成一个新的专题，换句话说，这里是那些主题比较分散的经典文章。正如本专题的logo小脚印一样，经典文章是经过多方积累而形成的，它们具有极高的借鉴意义，将这些文章收录成集，有利于重温经典，更上一层楼。

目录：
    社会生活中的十二大著名法则
    10个心理学故事引出的各种效应
    一篇关于人民币升值的好文
    澄清P问题、NP问题、NPC问题的概念
    CPU占用率算法

评论: 0　查看评论　发表评论

编辑推荐：Google社会化产品Buzz发布会实录

网站导航：博客园首页个人主页新闻闪存小组博问社区知识库

第五回：设计数据结构，存好了数据好干活

floodpeak — Fri, 25 Apr 2008 14:19:00 +0800

阅读: 2166 评论: 21 作者: floodpeak 发表于 2008-04-25 14:19 原文链接

    上篇文章介绍了本算法中需要用到的一些数学工具以及运算技巧，为后文打下了数学基础。本文从另一个方面着手，为后文提供存储数据的数据结构。
    在所有的数据结构书籍中一定会有这样一个公式：程序 = 算法 + 数据结构，显然这二者是每个程序员的必修课。由于对它们的研究比较深入，各种经典结构及算法已经基本定型，所以无论是在.NET还是在Java中都被封装成非常好用的类，这样就大幅提高了开发效率，并且降低了编程门槛，这都是好事。但是万不可因为它们非常容易使用就只知其然不知其所以然，一定的了解还是必要的，毕竟经典的数据结构在某些时候未必会完全符合要求，我们需要进行包装甚至是重头搭建，还好本算法使用的数据结构不那么复杂，适当的包装一下就可以了。

一、 DirectX中的两个缓冲
    如果你不是DirectX菜鸟，可以直接跳过这一段，本段是对DirectX中顶点缓冲（Vertex Buffer）和索引缓冲（Index Buffer）的概要介绍。
    在DirectX中，一切都是三角形（当然如果你非拿线段来质问我就太矫情了），所有的物体都是由大量的三角形拟合而成，这也正是本专题存在的前提。
    如果是我们来设计DirectX中的数据结构会怎样做呢？最直观的，把每个三角形的三个顶点按照顺序（DirectX中是逆时针）构成一个三元组，再把所有这些三元组组成一个大数组不就可以了。没错，DirectX正是这样做的，只不过并没有什么三元组，而是把所有的顶点一股脑的装进那个大数组，每相邻的三个为一组表示一个三角形罢了。
    上面所说的方案是DirectX支持的一种，这个大数组就是顶点缓冲，它无可挑剔的直观，但是它的缺点也是致命的：浪费了大量的存储空间。浪费在什么地方了呢？很多三角形是共用顶点的！每个顶点所占用的空间可是不菲呀，重复的那几遍毫无意义。
    很自然的，我们想到，如果把顶点缓冲当做一个没有顺序关系，没有重复的顶点池，把每个三角形顶点在这个池中的索引拿出来放到另一个数组中，像前面一样把索引三个一组的排列来表示一个三角形，会不会更好呢？

我们来算笔帐：描述空间三角形某个顶点需要三个分量，每个分量都是Double型的，在.NET中一个Double值占用8个字节，所以一个顶点需要24个字节。现假设渲染如图的一个立方体，总共有6个面，每个面需要两个三角形，总共是12个三角形，36个顶点，如果将这36个顶点一股脑的装进顶点缓冲需要6×2×3×24 = 864字节；现在换用第二种方法，顶点个数一共是8个，所以顶点缓冲需要8×24 = 192字节，三角形的个数还是那么多，所以需要有36个索引来分别代表上一种方法的36个顶点，这些索引都是其对应顶点在顶点缓冲中的索引，在这里是0~7，索引都是Integer型的，在.NET中一个Integer值占用4个字节，所以这里索引数组需要36×4 = 144字节，总共是192 + 144 = 336字节。结果很明显，采用第二种方法的空间占有量仅为第一种方法的336 / 864 = 38.9%，优势极其明显，当模型更为复杂时这种优势将更加强化，所以只有在模型极为简单的时候才使用第一种方法，毕竟直观嘛，如果模型稍微复杂一些，就要使用带有索引的方法了，索引的数组正是DirectX的索引缓冲。
这种顶点缓冲与索引缓冲的应用，与享元模式何其相似来尔！

二、设计数据结构
由于该算法三角剖分出来的结果是要为DirectX提供数据的，所以我们的数据结构要能很好的与DirectX数据结构交互，因此参照DirectX数据结构设计是很自然的，况且根据前面的分析，该种设计方式也是很合理的。

VertexBuffer

IndexBuffer

顶点缓冲中的Point2OnLine是上篇文章Point2的子类，含有一些其它属性，在这里不必关心。由于我们面对的问题是平面多边形的三角剖分，所以所有顶点不必具有三个分量，可以认为z值始终为零。

三、例说二缓冲
下面我们就从一个具体的例子来详细说明两个缓冲是如何配合的。

第一步：绘制一个多边形
第二步：利用扫描线在多边形上找到所有被扫描线扫到的点（整体思路请看《第二回：漫谈新思路，是我们自己干的时候了》）
第三步：上一步找到的点已经被组织到顶点缓冲，顺序是无所谓的，但是不可以重复，上文已经说过了
第四步：第一个三角形ABD的索引按照顺序（逆时针）添加到索引缓冲
第五步：所有五个三角形的顶点索引按照顺序添加到索引缓冲
上面的步骤中第二步和第三步是交替进行的，找到一个点后就将该点加入到顶点缓冲中，具体过程请看《第六回：寻找交点，离胜利就剩一步之开找》，第四第五步的详细过程请看《第七回：寻找三角形，夺取红旗》。

终于，一切准备工作已经完成，用于算法调试的步骤显示在《第三回：实现步骤显示，一步一步看得见》已经实现，数学基础在《第四回：掌握数学工具，没个好帮手怎么行》已经打下，本文又给数据存储做好了准备，下一篇文章我们将进入整个算法的最核心地带，讲述交点的寻找历程。

评论: 21　查看评论　发表评论

编辑推荐：Google社会化产品Buzz发布会实录

网站导航：博客园首页个人主页新闻闪存小组博问社区知识库

上班途中如打仗

floodpeak — Wed, 23 Apr 2008 16:00:00 +0800

阅读: 258 评论: 0 作者: floodpeak 发表于 2008-04-23 16:00 原文链接

    在连日两天的阴雨天气后，太阳公公终于上班了！
    早晨一睁开眼看到了普照阳光，心情煞是舒畅，怀着愉快的心情出发了，一切都没有预兆。
    <7：00>坐在车里，打开收音机，听着交通广播，路况信息里传来一阵急促的声音：快速路河东段各个入口全部封闭，在富民路附近发生了严重的交通事故，快速路河东向河西一侧无法通行。心里只有一个感觉，要上战场了！
    <7：14>像平常一样很轻松的就上了津塘路，快到快速路了，仍无征兆。我开到通往快速路入口的立交桥上，一上去黑压压的，另一番世界。朝快速路上看了一眼，正如路况信息所说，所有汽车动弹不得！这时我做了一个重大决定：绕行。
    绕行的决定不是那么好做的，这代表着要多走十公里左右的路程，而且这些路程也只能一步一步的移动，这些路就是在平常我都尽量不走的，可是没有办法，与其堵在那儿，还不如闯一闯，或许还能不迟到。我向左一打方向盘，直奔中环线而去。
    与我想法一样的兄弟姐妹们煞是不少，于是津塘路也来了个水泄不通，本来很宽的六行车道（单侧）停了十来排，无奈下，我决定穿楼群，多亏这一带我很熟，在这里上了6年的中学。
    <7：30>楼群间的路虽然很窄，但是还好，并不拥堵，很快我就转回了津塘路，准备上蝶桥了。自此开始了漫长的排队，平均时速不到20公里，在一番一档二档的频繁交换下，终于绕回了快速路。<8：10>
    快速路上没有几辆车，大概都是堵在那边了吧，于是，我愤怒的在不到30秒的时间里将车速提到了100公里，疾驰而去，因为我知道，前面还有一个小战役。
    由于宾悦桥还没有修好，如果从桥下进入华苑等于送死，每天我都是从中石油桥转到津涞路上，接上我的女朋友再上外环。津涞路虽然不堵但是却大坑小坑落玉盘，经过两天雨水的浇灌，再被那些可恶的大车碾压，已然成了山丘一片，这里每天也要花上一段气力。<8：20>
    在外环上又撒了缰，终于准时的到达了公司楼下，这里比平常的车少了很多，我想还有很多人在奋斗吧，这时路况信息来了：河东各个快速路入口开始缓慢放行。

此图是正常情况下我应当走的路线：（点击图片可以查看炫地图）

下图是今天的绕行路线，由于时间紧没有接女朋友而直接到了我的公司：（点击图片可以查看炫地图）

评论: 0　查看评论　发表评论

编辑推荐：Google社会化产品Buzz发布会实录

网站导航：博客园首页个人主页新闻闪存小组博问社区知识库

博客园-Use after Think

CPU占用率算法

如何摆脱写文档时截屏的困扰

第六回：寻找交点，离胜利就剩一步 之 纽带

备忘录专题首页

转载系列首页

吐血三八二十四

澄清P问题、NP问题、NPC问题的概念

经典文章专题首页

第五回：设计数据结构，存好了数据好干活

上班途中如打仗

第六回：寻找交点，离胜利就剩一步之纽带