http://amberlife.net 又一个 WordPress Blog Wed, 03 Mar 2010 12:27:10 +0000 http://backend.userland.com/rss092 en 开学后复习的第一门课程是C语言，选择翻看这本经典的《c  programming language 》。目前看到第三章3.3。书中介绍了两种用C语言实现的折半查找法。看到第一个算法的时候自己感觉很容易理解，随即向后看去，后面的一道习题，让用另外的一种策略来实现改进现有的折半查找，要求只用一次判断来实现，实验比较一下这两个算法的执行效率上是否存在差异。此时心想着这一定是一个比前面那个更高明的算法，于是乎，兴奋的去翻看了答案，看着答案的实现感觉理解起来还行，代码比原有的长，比原来的逻辑复杂。心想着，这就是高明的算法的啊。谁知道后面的解析对答案的评价是：“两种方案的执行时间几乎没有什么差异。我们并没有得到多大的性能改进，反而失掉了代码可读性。教材原有的代码更容易阅读和理解”。 看到这句话后，立马有一种被欺骗的感觉，我上当了。可仔细想想，这难道不是因为我自己的意识在作怪吗。自己干嘛不亲自将两种代码都做做实验呢。做个test，看看两种方法的执行时间的话，也许自己会确定自己的答案。永远不要跟着自己的习惯走，让自己认为答案永远都是好的。有时候自己动动手，会有更大的收获。自己最近想的太多了，可是动手的时间少了。平衡一下自己的实践和理论学习也是必须的。 下面我把两段代码都写出来共大家参考，也算是一次练手的机会吧。 int binsearch(int x ,int v[],int n) { int low ,high,mid; low =0 ; high=n-1; while(low<=high) { mid = (low+high)/2; ... http://amberlife.net/2010/03/%e4%b8%8d%e8%a6%81%e8%ae%a9%e8%87%aa%e5%b7%b1%e7%9a%84%e4%b9%a0%e6%83%af%e7%a7%b0%e4%b8%ba%e5%b7%a6%e5%8f%b3%e8%87%aa%e5%b7%b1%e7%9a%84%e6%80%9d%e7%bb%b4/ 1.搜索 //回溯 2.DP（动态规划） 3.贪心 4.图论 //Dijkstra、最小生成树、网络流 5.数论 //解模线性方程 6.计算几何 //凸壳、同等安置矩形的并的面积与周长 7.组合数学 //Polya定理 8.模拟 9.数据结构 //并查集、堆 10.博弈论 1、 排序 1423, 1694, 1723, 1727, 1763, 1788, 1828, 1838, 1840, 2201, 2376, 2377, 2380, 1318, 1877, 1928, 1971, 1974, 1990, 2001, 2002, 2092, 2379, 1002（需要字符处理，排序用快排即可） 1007（稳定的排序） 2159（题意较难懂） 2231 2371（简单排序） 2388（顺序统计算法） 2418（二叉排序树） 2、 搜索、回溯、遍历 1022 1111d 1118 1129 1190 1562 1564 1573 1655 2184 2225 2243 2312 2362 2378 2386 1010,1011,1018,1020,1054,1062,1256,1321,1363,1501，1650,1659,1664,1753,2078 ,2083,2303,2310,2329 简单：1128, ... http://amberlife.net/2010/02/%e5%8c%97%e5%a4%a7acm%ef%bc%88pku-judgeonline%ef%bc%89%e9%a2%98%e7%9b%ae%e5%88%86%e7%b1%bb%e3%80%90%e8%bd%ac%e8%bd%bd%e3%80%91/ c#中构建多线程应用程序，不一定要通过System.Threading命名空间下的类来实现，通过delegate委托也能够实现多线程编程所需要的方式，（其实delegate就是利用CLR的ThreadPool来实现的，这个不再我们的讨论范围）。 先来说一下委托吧，通过当我们在应用程序中定义了一个委托后，其实在被编译成CIL后，就是一个类，我们可以通过ildasm.exe 这个程序来查看生成的CIL。 我们举个例子: delegate int del (string str1, string str2) del被编译后，生成的类的定义如下： sealed class del: System.MulticastDelegate { public del(object target,uint functionAddress); public void Invoke(string str1,string str2); public IAsyncResult BeginInvoke(string str1,string str2,AsyncCallback cb ,object state); public int EndInvoke(IAsyncResult result); } 生成的Invoke()方法用来调用被代理对象同步方式维护的方法，调用线程（应用程序的主线程）会一直等待，直到委托调用完成。在c#中，Invoke()不会被显式的调用，而是在同步方式下自动被触发。 下面我们来说说BeginInvoke方法和EndInvoke()方法，这两个方法是在利用委托来实现异步调用的关键。 在本例中BeginInvoke方法如下： IAsyncResult BeginInvoke(string str1,string str2, AsyncCallback cb ,object state); 可以看到BeginInvoke方法返回IAsyncResult，参数列表中含有四个参数，前两个参数如同del委托中参数的定义，后两个参数System.AsyncCallback和System.Object类型的。 在本例中的EndInvoke方法如下： int EndInvoke(IAsyncResult result) EndInvoke方法返回int ，参数列表中含有一个参数，参数类型为IAsyncResult。在BeginInvoke方法和EndInvoke方法中，BeginInvoke方法中除了最后两个参数，前面的参数必须和之前定义的委托中的参数一样；EndInvoke方法的返回值必须和之前定义的委托的返回值一样。 借助上面定义的委托，我们写这样一个函数 int stradd (string str1,string str2) { //仅仅为了测试一下异步方法的线程和调用线程是否是一致的。 Console.WriteLine("stradd thread id : ... http://amberlife.net/2010/01/%e7%90%86%e8%a7%a3c%e4%b8%ad%e7%9a%84%e5%bc%82%e6%ad%a5%e6%96%b9%e6%b3%95/ 一.多线程的概念 Windows是一个多任务的系统，如果你使用的是windows 2000及其以上版本，你可以通过任务管理器查看当前系统运行的程序和进程。什么是进程呢？当一个程序开始运行时，它就是一个进程，进程所指包括运行中的程序和程序所使用到的内存和系统资源。而一个进程又是由多个线程所组成的，线程是程序中的一个执行流，每个线程都有自己的专有寄存器(栈指针、程序计数器等)，但代码区是共享的，即不同的线程可以执行同样的函数。多线程是指程序中包含多个执行流，即在一个程序中可以同时运行多个不同的线程来执行不同的任务，也就是说允许单个程序创建多个并行执行的线程来完成各自的任务。浏览器就是一个很好的多线程的例子,在浏览器中你可以在下载JAVA小应用程序或图象的同时滚动页面,在访问新页面时,播放动画和声音,打印文件等。 多线程的好处在于可以提高CPU的利用率——任何一个程序员都不希望自己的程序很多时候没事可干，在多线程程序中，一个线程必须等待的时候，CPU可以运行其它的线程而不是等待，这样就大大提高了程序的效率。 然而我们也必须认识到线程本身可能影响系统性能的不利方面，以正确使用线程： 线程也是程序，所以线程需要占用内存，线程越多占用内存也越多 多线程需要协调和管理，所以需要CPU时间跟踪线程 线程之间对共享资源的访问会相互影响，必须解决竞用共享资源的问题 线程太多会导致控制太复杂，最终可能造成很多Bug 基于以上认识，我们可以一个比喻来加深理解。假设有一个公司，公司里有很多各司其职的职员，那么我们可以认为这个正常运作的公司就是一个进程，而公司里的职员就是线程。一个公司至少得有一个职员吧，同理，一个进程至少包含一个线程。在公司里，你可以一个职员干所有的事，但是效率很显然是高不起来的，一个人的公司也不可能做大；一个程序中也可以只用一个线程去做事，事实上，一些过时的语言如fortune,basic都是如此，但是象一个人的公司一样，效率很低，如果做大程序，效率更低——事实上现在几乎没有单线程的商业软件。公司的职员越多，老板就得发越多的薪水给他们，还得耗费大量精力去管理他们，协调他们之间的矛盾和利益；程序也是如此，线程越多耗费的资源也越多，需要CPU时间去跟踪线程，还得解决诸如死锁，同步等问题。总之，如果你不想你的公司被称为“皮包公司”，你就得多几个员工；如果你不想让你的程序显得稚气，就在你的程序里引入多线程吧！ 本文将对C#编程中的多线程机制进行探讨，通过一些实例解决对线程的控制，多线程间通讯等问题。为了省去创建GUI那些繁琐的步骤，更清晰地逼近线程的本质，下面所有的程序都是控制台程序，程序最后的Console.ReadLine()是为了使程序中途停下来，以便看清楚执行过程中的输出。 好了，废话少说，让我们来体验一下多线程的C#吧！ 二.操纵一个线程 任何程序在执行时，至少有一个主线程，下面这段小程序可以给读者一个直观的印象： //SystemThread.cs using System; using System.Threading; namespace ThreadTest { class RunIt { [STAThread] static void Main(string[] args) { Thread.CurrentThread.Name="System Thread";//给当前线程起名为"System Thread" Console.WriteLine(Thread.CurrentThread.Name+"'Status:"+Thread.CurrentThread.ThreadState); Console.ReadLine(); } } } 编译执行后你看到了什么？是的，程序将产生如下输出： System Thread's Status:Running 在这里，我们通过Thread类的静态属性CurrentThread获取了当前执行的线程，对其Name属性赋值“System Thread”，最后还输出了它的当前状态（ThreadState）。所谓静态属性，就是这个类所有对象所公有的属性，不管你创建了多少个这个类的实例，但是类的静态属性在内存中只有一个。很容易理解CurrentThread为什么是静态的——虽然有多个线程同时存在，但是在某一个时刻，CPU只能执行其中一个。 就像上面程序所演示的，我们通过Thread类来创建和控制线程。注意到程序的头部，我们使用了如下命名空间： using System; using System.Threading; 在.net framework class library中，所有与多线程机制应用相关的类都是放在System.Threading命名空间中的。其中提供Thread类用于创建线程，ThreadPool类用于管理线程池等等，此外还提供解决了线程执行安排，死锁，线程间通讯等实际问题的机制。如果你想在你的应用程序中使用多线程，就必须包含这个类。Thread类有几个至关重要的方法，描述如下： Start():启动线程 Sleep(int):静态方法，暂停当前线程指定的毫秒数 Abort():通常使用该方法来终止一个线程 Suspend()：该方法并不终止未完成的线程，它仅仅挂起线程，以后还可恢复。 Resume():恢复被Suspend()方法挂起的线程的执行 下面我们就动手来创建一个线程，使用Thread类创建线程时，只需提供线程入口即可。线程入口使程序知道该让这个线程干什么事，在C#中，线程入口是通过ThreadStart代理（delegate）来提供的，你可以把ThreadStart理解为一个函数指针，指向线程要执行的函数，当调用Thread.Start()方法后，线程就开始执行ThreadStart所代表或者说指向的函数。 打开你的VS.net，新建一个控制台应用程序（Console Application），下面这些代码将让你体味到完全控制一个线程的无穷乐趣！ //ThreadTest.cs using System; using System.Threading; namespace ThreadTest { public class Alpha { public void Beta() { while (true) { Console.WriteLine("Alpha.Beta is running in its own thread."); } } }; public class Simple { public static int Main() { Console.WriteLine("Thread Start/Stop/Join Sample"); Alpha oAlpha = new Alpha(); file://这里创建一个线程，使之执行Alpha类的Beta()方法 Thread oThread = new Thread(new ThreadStart(oAlpha.Beta)); oThread.Start(); while ... http://amberlife.net/2010/01/%e8%bd%acc-%e5%a4%9a%e7%ba%bf%e7%a8%8b-%e7%bc%96%e7%a8%8b/ 进程 进程是操作系统用于隔离众多正在运行的应用程序的机制。在．Net之前，每一个应用程序被加载到单独的进程中，并为该进程指定私有的虚拟内存。进程不能直接访问物理内存，操作系统通过其它的处理把这些虚拟内存映射到物理内存或IO设备的某个区域，而这些物理内存之间不会有重叠，这就决定了一个进程不可能访问分配给另一个进程的内存。相应地，运行在该进程中的应用程序也不可能写入另一个应用程序的内存，这确保了任何执行出错的代码不会损害其地址空间以外的应用程序。在这种机制下，进程作为应用程序之间一个独立而安全的边界在很大程度上提高了运行安全。 进程的缺点是降低了性能。许多一起工作的进程需要相互通信，而进程却不能共享任何内存，你不能通过任何有意义的方式使用从一个进程传递到另一个进程的内存指针。此外，你不能在两个进程间进行直接调用。你必须代之以使用代理，它提供一定程度的间接性。虽然，使用动态连接库dll让所有的组件运行在同一空间，一定程度上可以提高性能，但这些组件相互影响，一个组件的错误将极有可能导致整个应用程序的崩溃，“dll地狱”更是让许多应用程序难以避免。 线程 线程是进程中的一个实体，是被系统独立调度和分派的基本单位，线程自己不拥有系统资源，只拥有一点在运行中必不可少的资源，但它可与同属一个进程的其它线程共享进程所拥有的全部资源。一个线程可以创建和撤消另一个线程，同一进程中的多个线程之间可以并发执行。由于线程之间的相互制约，致使线程在运行中呈现出间断性。线程也有就绪、阻塞和运行三种基本状态。 线程是程序中一个单一的顺序控制流程.在单个程序中同时运行多个线程完成不同的工作,称为多线程. 线程和进程的区别在于,子进程和父进程有不同的代码和数据空间,而多个线程则共享数据空间,每个线程有自己的执行堆栈和程序计数器为其执行上下文.多线程主要是为了节约CPU时间,发挥利用,根据具体情况而定. 线程的运行中需要使用计算机的内存资源和CPU. 应用程序域(AppDomain) 在．Net中，应用程序有了一个新的边界：应用程序域（以下简称域）。它是一个用于隔离应用程序的虚拟边界。为了禁止不应交互的代码进行交互，这种隔离是必要的。．Net的应用程序在域层次上进行隔离，一个域中的应用程序不能直接访问另一个域中的代码和数据。这种隔离使得在一个应用程序范围内创建的所有对象都在一个域内创建，确保在同一进程中一个域内运行的代码不会影响其他域内的应用程序，大大提高了运行的安全。 .Net结构中，由于公共语言运行库能够验证代码是否为类型安全的代码，所以它可以提供与进程边界一样大的隔离级别，其性能开销也要低得多。你可以在单个进程中运行几个域，而不会造成进程间调用或切换等方面的额外开销。这种方法是把任何一个进程分解到多个域中，允许多个应用程序在同一进程中运行，每个域大致对应一个应用程序，运行的每个线程都在一个特殊的域中。如果不同的可执行文件都运行在同一个进程空间中，它们就能轻松地共享数据或直接访问彼此的数据。这种代码同运行同一个进程但域不同的类型安全代码一起运行时是安全的。在一个进程内运行多个应用程序的能力显著增强了服务器的可伸缩性。 域与线程的关系 在.Net中，线程是公共语言运行库用来执行代码的操作系统构造。在运行时，所有托管代码均加载到一个域中，由特定的操作系统线程来运行。然而，域和线程之间并不具有一一对应关系。在任意给定时间，单个域中可以执行不止一个线程，而且特定线程也并不局限在单个域内。也就是说，线程可以跨越域边界，不为每个域创建新线程。当然，在指定时刻，每一线程都只能在一个域中执行。运行库会跟踪所有域中有哪些线程正在运行。通过调用．Net类库的 Thread.GetDomain 方法，你还可以确定正在执行的线程所在的域。 <转载自：http://www.cnblogs.com/Dlonghow/archive/2009/09/24/1573122.html> http://amberlife.net/2009/12/%e8%bf%9b%e7%a8%8b%e3%80%81%e7%ba%bf%e7%a8%8b%e4%b8%8e%e5%ba%94%e7%94%a8%e7%a8%8b%e5%ba%8f%e5%9f%9fappdomain-%e6%b5%85%e6%9e%90/ 1 动态加载程序集 2 反射获取Type信息（类的信息，方法的信息） 3晚期绑定（1 创造对象实例  2 调用方法（有参，无参）） http://amberlife.net/2009/12/%e5%8f%8d%e5%b0%84%ef%bc%8c%e5%8a%a8%e6%80%81%e5%8a%a0%e8%bd%bd%ef%bc%8c%e6%99%9a%e6%9c%9f%e7%bb%91%e5%ae%9a%e9%97%b4%e7%9a%84%e5%85%b3%e7%b3%bb%e3%80%82/ win32文件首部 CLR文件首部 CIL代码 类型元数据 程序集清单 可选的嵌入资源 http://amberlife.net/2009/12/net%e7%a8%8b%e5%ba%8f%e9%9b%86%e6%a0%bc%e5%bc%8f/ 对于一个字节（8bit）的变量，求其二进制表示中“1”的个数，要求算法的执行效率尽可能地高。 【解法一】 可以举一个八位的二进制例子来进行分析。对于二进制操作，我们知道，除以一个2，原来的数字将会减少一个0。如果除的过程中有余，那么就表示当前位置有一个1。 int Count(int v) { int num = 0; while(v) { if(v % 2 == 1) { num++; } v = v/ 2; } return num; } 【解法二】使用位操作 前面的代码看起来比较复杂。我们知道，向右移位操作同样也可以达到相除的目的。唯一不同之处在于，移位之后如何来判断是否有1存在。对于这个问题，再来看看一个八位的数字：10 100 001。 在向右移位的过程中，我们会把最后一位直接丢弃。因此，需要判断最后一位是否为1，而“与”操作可以达到目的。可以把这个八位的数字与00000001进行“与”操作。如果结果为1，则表示当前八位数的最后一位为1，否则为0。代码如下： int Count(int v) { int num = 0; While(v) { num += v &0x01; v >>= 1; } return num; } 【解法三】 位操作比除、余操作的效率高了很多。但是，即使采用位操作，时间复杂度仍为O（log2v），log2v为二进制数的位数。那么，还能不能再降低一些复杂度呢？如果有办法让算法的复杂度只与“1”的个数有关，复杂度不就能进一步降低了吗？ 同样用10 100 001来举例。如果只考虑和1的个数相关，那么，我们是否能够在每次判断中，仅与1来进行判断呢？ 为了简化这个问题，我们考虑只有一个1的情况。例如：01 000 000。 如何判断给定的二进制数里面有且仅有一个1呢？可以通过判断这个数是否是2的整数次幂来实现。另外，如果只和这一个“1”进行判断，如何设计操作呢？我们知道的是，如果进行这个操作，结果为0或为1，就可以得到结论。 int Count(int v) { int num = 0; while(v) { v &= (v-1); num++; } return num; } 【解法五】查表法 int countTable[256] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, ... http://amberlife.net/2009/12/%e6%b1%82%e4%ba%8c%e8%bf%9b%e5%88%b6%e6%95%b0%e4%b8%ad1%e7%9a%84%e4%b8%aa%e6%95%b0/ 看移山之道这个网站，看到了不错的问题，好多牛人在讨论，以后得常去，最近忙着考试，写到要少的多了。 有一次我烙了三个饼，一个两面都焦了，一个两面都是金黄色，一个一面是焦的，一面是金黄色，我把它们摞一起，只能看到最上一面，发现是焦的，问最上面这个饼的另一面是焦的概率是多少？ 解法1： 1. 最上一面是焦的, 排除最上一张是两面金黄色 2. 剩下两张饼四个面, 三面是焦的, 一面金黄色, 现知道其中一面是焦的, 所以判断另一面是焦的概率就是求 二面焦 + 一面金黄 中焦的概率, = 2/2+1 = 2/3 解法2： A=最上面的饼双面焦 B=最上面的饼双面金黄 C=最上面的饼一面金黄一面焦 J=最上面的一面焦 则P(J|A)=1，P(J|B)=0，P(J|C)=0.5 P(A|J)=P(AJ)/P(J)=(1/3)/(1/2)=2/3 http://amberlife.net/2009/12/%e4%b8%80%e6%91%9e%e7%83%99%e9%a5%bc%e5%bc%95%e5%8f%91%e7%9a%84%e2%80%9c%e8%a1%80%e6%a1%88%e2%80%9d/ 1.vi /etc/sysconfig/i18n 将内容改为 LANG="zh_CN.GB18030" LANGUAGE="zh_CN.GB18030:zh_CN.GB2312:zh_CN" SUPPORTED="zh_CN.GB18030:zh_CN:zh:en_US.UTF-8:en_US:en" SYSFONT="lat0-sun16" 这样中文在SSH,telnet终端就可以正常显示了。 2.安安装Linux的时候选择的是中文字,但是使用的时候出现了乱码解决方法是在命令提示下输入export LANG=C 3.export LC_ALL=zh_CN.GBK export LANG=zh_CN.GBK http://amberlife.net/2009/11/ssh%e4%b8%8b%e7%9a%84%e4%b9%b1%e7%a0%81%e9%97%ae%e9%a2%98/