http://amberlife.net 又一个 WordPress Blog Sat, 17 Jul 2010 13:36:16 +0000 http://backend.userland.com/rss092 en I have a dream that one day every valley shall be exalted: every hill an d mountain shall be made low ,the rough places will be made plane, and the crooked places will be made straight, and the glory of the Lord shall be revealed, and all ... http://amberlife.net/2010/07/%e6%88%91%e6%a2%a6%e6%83%b3%e6%9c%89%e4%b8%80%e5%a4%a9%ef%bc%8c%e6%b7%b1%e8%b0%b7%e5%bc%a5%e5%90%88%ef%bc%8c%e9%ab%98%e5%b1%b1%e5%a4%b7%e5%b9%b3%ef%bc%8c%e6%ad%a7%e8%b7%af%e5%8c%96%e5%9d%a6%e9%80%94/ 豆瓣url分析图关于豆瓣的一个url分析，保存一份，供以后在分析 http://amberlife.net/2010/07/%e8%b1%86%e7%93%a3url%e8%84%91%e5%9b%be%e5%88%86%e6%9e%90%e3%80%82/ 软件工程考试资料 访问此链接可获取：http://amberlife.net/wp-content/uploads/2010/06/软件工程.htm ，转载自http://www.wisdomlife.cn/review2010/se.html http://amberlife.net/2010/06/%e8%bd%af%e4%bb%b6%e5%b7%a5%e7%a8%8b%e8%80%83%e8%af%95%e8%b5%84%e6%96%99/  As we know , we live in the times of knowledge explosion, when news,information even rumors comes from all around of the world. (when news , facts,opinions even rumors have been bombarding us from every corner of the world )With the development of information technology,more and more e-books come to ... http://amberlife.net/2010/06/2008%e5%b9%b46%e6%9c%88%ef%bc%8ccet-6%e4%bd%9c%e6%96%87/ there has been a heatted discussion about the picture . As is shown above ,there are two handicapped men ,one is lame in the left,while the other is in the other one,with their walking sticks being stand in the road,supporting each other go ahead. simple as the picture is ,the ... http://amberlife.net/2010/06/08%e5%b9%b4%e8%80%83%e7%a0%94%e8%8b%b1%e8%af%ad%e5%a4%a7%e4%bd%9c%e6%96%87/ 01背包问题-回溯法 #include #include int n=5,c=10; int value[5]={6,3,5,4,6}; int weight[5]={2,2,6,5,4}; int cv[5]={0,0,0,0,0}; int bv[5]={0,0,0,0,0}; int cw=0; int curv = 0 ; int bestv =0 ; void output() { int i =0; for(i; i=n) { if(bestv http://amberlife.net/2010/05/01%e8%83%8c%e5%8c%85%e9%97%ae%e9%a2%98-%e5%9b%9e%e6%ba%af%e6%b3%95-c%e8%af%ad%e8%a8%80%e5%ae%9e%e7%8e%b0%e3%80%82/ 开学后复习的第一门课程是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/