算法 - 我的文章 -

weiliming.cublog.cn

关于作者

姓名：
职业：
年龄：
位置：
个性介绍：

\|\|	<<	>>	\|\|

我的分类

	文章列表 - 算法

	线程调度算法分析 zz
	<DIV> <P><A name=N1004F><SPAN class=atitle3>4.1.1 线程调度算法的总体描述</SPAN></A><BR>在分时系统中，内核给每个线程分配一段CPU时间，这段时间称为时间片，当这段时间过去之后，内核将调度另一个线程将其变为执行态。这就是所谓的时间片轮转法。</P> <P>与UNIX中的线程调度十分相似的是，OSKit的调度程序也采用了一种被称为多级反馈循环调度的算法，此种算法属于操作系统调度程序中最常用的一种。其核心思想是：内核给线程分一个时间片，并把该线程反馈回若干优先级队列中的某一个。一个线程在结束它之前，可能需要多次通过多次的"反馈循环"。当内核作上下文切换和恢复的时候，调度程序必须保证该线程从原来挂起的地方继续执行，否则这种调度算法是不能采用的。</P> <P>因此，我认为有必要向大家重申一下线程的上下文切换和恢复。首先，所谓线程的上下文是指由用户地址空间的内容、硬件寄存器的内容以及与该线程有关的内核数据结构组成的。更加严格的讲，线程的上下文是由它的用户级上下文、寄存器上下文以及系统级上下文组成。</P> <P><A name=N1005E><SPAN class=atitle3>4.1.2 优先级逆转法</SPAN></A><BR>OSKit中采用了操作系统设计中比较精彩的优先级逆转算法……
查看全文
	发表于:2008-07-07 ┆ 阅读(5) ┆ 评论(0)

	数组元素循环左/右移问题 zz
	<DIV><!--StartFragment-->  <TABLE cellSpacing=0 cellPadding=0 width="96%" border=0> <TBODY> <TR height=7> <TD width=7 height=7></TD> <TD width="100%" bgColor=#f3f3f3 height=7></TD> <TD width=7 height=7></TD></TR> <TR> <TD align=middle bgColor=#f3f3f3 colSpan=3> <TABLE cellSpacing=0 cellPadding=0 width="100%" border=0> <TBODY> <TR height=25> <TD align=middle height=25><STRONG><A href="http://blog.chinaunix.net/u/22520/showart_424791.html"><FONT color=#810081>http://blog.chinaunix.net/u/22520/showart_424791.html</FONT></A></STRONG></TD></TR> <TR height=1> <TD bgColor=#d2dee2 height=1><FONT color=#810081></FONT></TD></TR> <TR height=1> <TD bgColor=#ffffff height=1><FONT color=#810081></FONT></TD></TR> <TR> <TD align=middle> <TABLE cellSpacing=0 cellPadding=0 width="100%" border=0> <TBODY> <TR> <TD width="100%"> <DIV>汇编语言和C语言里面都有循环移位指令或操作符，可以实现循环左移或右移若干个bit，但若要在数组中循环左移或右移若干个元素，却无法直接实现。下面以字符数组……
查看全文
	发表于:2008-03-26 ┆ 阅读(157) ┆ 评论(0)

	[转]位运算简介及实用技巧 zz
	<DIV> <DIV class=t_msgfont id=postmessage_9745461><BR>   去年年底写的关于位运算<FONT color=#810081></FONT>的日志是这个Blog里少数大受欢迎的文章之一，很多人都希望我能不断完善那篇文章。后来我看到了不少其它的资料，学习到了更多关于位运算的知识，有了重新整理位运算技巧的想法。从今天起我就开始写这一系列位运算讲解文章，与其说是原来那篇文章的follow-up，不如说是一个remake。当然首先我还是从最基础的东西说起。<BR><BR><STRONG>什么是位运算？</STRONG><BR>    程序中的所有数在计算机<SPAN class=t_tag onclick=tagshow(event) href="tag.php?name=%C4%DA%B4%E6">内存</SPAN>中都是以二进制的形式储存的。位运算说穿了，就是直接对整数在<SPAN class=t_tag onclick=tagshow(event) href="tag.php?name=%C4%DA%B4%E6">内存</SPAN>中的二进制位进行操作。比如，and运算本来是一个逻辑运算符，但整数与整数之间也可以进行and运算。举个例子，6的二进制是110，11的二进制是1011，那么6 and 11的结果就是2，它是二进制对应位进行逻辑运算的结果（0表示False，1表示True，空位都当0处理）：<BR><FONT face="宋体 ">   &nbsp……
查看全文
	发表于:2008-03-26 ┆ 阅读(243) ┆ 评论(0)

	STL中的排序算法zz
	<!--StartFragment--> <DIV>STL中有多种排序算法，各有各的适用范围，下面听我一一道来：<BR><BR><STRONG>I、完全排序</STRONG><BR><STRONG>sort() </STRONG><BR>首先要隆重推出的当然是最最常用的sort了，sort有两种形式，第一种形式有两个迭代器参数，构成一个前开后闭的区间，按照元素的 less 关系排序；第二种形式多加一个指定排序准则的谓词。sort基本是最通用的排序函数，它使用快速排序算法，并且在递归过程中，当元素数目小于一个阈值（一般是16，我的试验是24）时，转成直接插入排序。伟大的数学家Knuth已经证明，在平均意义上，快速排序是最快的了；当然，最坏复杂性比较差。sort要求随机迭代器，因此对于很多编译器来说，对于前向迭代器（如list）使用sort是一个编译错误。(不过，在vc2005里面，这个错误信息实在很糟糕)<BR><BR>sort的基本使用方式如下：</DIV> <TABLE borderColor=#999999 cellSpacing=0 cellPadding=0 width="95%" bgColor=#f1f1f1 border=1> <TBODY> <TR> <TD> <P><FONT face=新宋体 size=1>#include <vector> <BR>#include <algorithm> <BR>#include <functional> <BR>#include <cstdlib> <BR><BR>using namesp……
查看全文
	发表于:2008-03-26 ┆ 阅读(122) ┆ 评论(0)

	查找算法 zz
	<DIV> <DIV></DIV> <DIV><STRONG>顺序查找、二分查找、插值查找、动态查找(数组实现、链表实现)</STRONG></DIV> <DIV>// search.cpp : Defines the entry point for the console application.<BR>//<BR><BR>#include "stdafx.h"<BR>#include "LinkTable.h"<BR>#define         MAX_KEY   500<BR><STRONG><BR>//------------------------------数组实现部分----------------------------------</STRONG><BR>/*//<BR>     <STRONG>无序数组顺序查找算法函数nsq_Order_Search<用数组实现></STRONG><BR>     参数描述：<BR>    int array[]     :被查找数组<BR>         int n         :被查找数组元素个数<BR>         int key         :被查找的关键值<BR>     返回值:<BR>     &……
查看全文
	发表于:2008-03-24 ┆ 阅读(131) ┆ 评论(0)

	螺旋队列算法 zz
	<DIV>  转自<A href="http://tb.blog.csdn.net/TrackBack.aspx?PostId=2121999">http://tb.blog.csdn.net/TrackBack.aspx?PostId=2121999</A></DIV> <DIV>  111  112  113  114  115  116  117  118  119  120  121<BR>  110   73   74   75   76   77   78   79   80   81   82<BR>  109   72   43   44   45   46   47   48   49   50   83<BR>  108   71   42   <SPAN style="TEXT-DECORATION: line-through">21   22   23    24   25</SPAN>   26   51   84<BR>  107   70   41   <SPAN style="TEXT-DECORATION: line-through">20</SPAN>    7     8      9&nb……
查看全文
	发表于:2008-03-22 ┆ 阅读(246) ┆ 评论(1)

	快速排序 zz
	<DIV class=tit> </DIV> <TABLE style="TABLE-LAYOUT: fixed"> <TBODY> <TR> <TD> <DIV class=cnt id=blog_text> <P>    基本思想是：任取待排序列的某个记录作为基准，按照该关键码大小，将整个序列分成两个序列——左侧的所有记录的关键码都比基准小（或者等），右侧的都比基准大，基准则放在两个子序列之间，显然这时基准放在了最后应该放置的位置。分别对左右子序列重复上面的过程，直到最后所有的记录都放在相应的位置。</P> <P>　　下面的例程不容易看懂，因为这是几次改进之后的样子：</P> <P>template <class T><BR>int Partition(T a[], int left, int right, int& KCN, int& RMN)<BR>{<BR>int pivotpos = left; T pivot = a[left];//枢轴<BR>for (int i = left + 1; i <= right; i++)<BR>if (++KCN && a[i] < pivot && ++pivotpos != i)<BR>{ swap(a[i], a[pivotpos]); RMN += 3;}<BR>swap(a[left], a[pivotpos]); RMN += 3;<BR>return pivotpos;<BR>} </P> <P>　　将计算枢轴位置单独作为一个函数，可以避免递归的时候保存无用的临时变量。当你决定使用递归的时候，都要注意这点——将一切可以放……
查看全文
	发表于:2008-03-21 ┆ 阅读(93) ┆ 评论(0)

	C语言常用排序全解 zz
	<DIV align=center> <TABLE class=MsoNormalTable style="WIDTH: 100%; BORDER-COLLAPSE: collapse; mso-padding-alt: 0cm 0cm 0cm 0cm" cellSpacing=0 cellPadding=0 width="100%" border=0> <TBODY> <TR style="HEIGHT: 18.75pt; mso-yfti-irow: 0; mso-yfti-firstrow: yes"> <TD style="BORDER-RIGHT: #ebe9ed; PADDING-RIGHT: 0cm; BORDER-TOP: #ebe9ed; PADDING-LEFT: 0cm; PADDING-BOTTOM: 0cm; BORDER-LEFT: #ebe9ed; PADDING-TOP: 0cm; BORDER-BOTTOM: #ebe9ed; HEIGHT: 18.75pt; BACKGROUND-COLOR: transparent"> <P class=MsoNormal style="MARGIN: 0cm 0cm 0pt; TEXT-ALIGN: center; mso-pagination: widow-orphan" align=center><B><SPAN style="FONT-SIZE: 14pt; COLOR: #02368d; FONT-FAMILY: 宋体; mso-font-kerning: 0pt; mso-bidi-font-family: 宋体; mso-ascii-font-family: Verdana; mso-hansi-font-family: Verdana"></SPAN></B><SPAN lang=EN-US style="FONT-SIZE: 9pt; FONT-FAMILY: Verdana; mso-font-kerning: 0pt; mso-bidi-font-family: 宋体"><?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" /><o:p></o:p></SPA……
查看全文
	发表于:2008-03-20 ┆ 阅读(104) ┆ 评论(0)