Subscribe: C++博客-游戏人生-随笔分类-A算法导论
http://www.cppblog.com/Fox/category/6990.html/rss
Added By: Feedage Forager Feedage Grade B rated
Language: English
Tags:
Rate this Feed
Rate this feedRate this feedRate this feedRate this feedRate this feed
Rate this feed 1 starRate this feed 2 starRate this feed 3 starRate this feed 4 starRate this feed 5 star

Comments (0)

Feed Details and Statistics Feed Statistics
Preview: C++博客-游戏人生-随笔分类-A算法导论

C++博客-游戏人生-随笔分类-A算法导论



游戏人生 != ( 人生 == 游戏 ) 站点迁移至:http://www.yulefox.com。请订阅本博的朋友将RSS修改为http://feeds.feedburner.com/yulefox



Published: Mon, 07 Dec 2009 01:13:14 GMT

Last Build Date: Mon, 07 Dec 2009 01:13:14 GMT

 



UUID算法分析

Sun, 06 Dec 2009 07:07:00 GMT

本文同步自游戏人生 Writen by Fox(yulefox.at.gmail.com) 在具体讨论之前,本文先厘清UUID(Universally Unique IDentifier)与GUID(Globally Unique IDentifier)的关系。 在分布式、网络、单机环境下,为了能够使用具有某种形式的ID唯一标识系统中的任一元素,这样的ID可以不依赖中心认证自动生成,于是UUID就诞生了。 UUID标准的历史沿革和具体实现在RFC 4122、ITU-T Rec. X.667和ISO/IEC 9834-8:2008中均有详细描述。ITU和ISO采用的标准和RFC 4122都是在UUID的早期版本基础上完成,各版本之间具有一致性和兼容性。 因为不能保证UUID的唯一性,ITU和ISO针对UUID的使用都有免责声明。 GUID一般是指Microsoft对于UUID标准的实现,UUID的实现则多见于其他系统(*NIX、MAC OS等)中。在了解了这一区别后,本文将统一使用UUID来指代对应的原理、算法及实现。 文中关于UUID的讨论全部基于RFC 4122和ITU-T Rec. X.667以及OSF、IETF、ITU-T、ISO、FIPS的各种标准文档。而UUID的细节(如结构、表示、算法、实现等)均以ITU-T Rec. X667为唯一蓝本,文中“本标准”即指代该蓝本。 o 介绍 UUID是长度为16-byte(128-bit)的ID,一般以形如f81d4fae-7dec-11d0-a765-00a0c91e6bf6的字符串作为URN(Uniform Resource Name,统一资源名称)。 o 动机 无须中心认证,自动生成,支持一台机器每秒生成10M次(100纳秒级,其隐含原因是指能够区分的最小时间单位为100ns,将时间作为因子时,连续生成两个UUID的时间至少要间隔100ns)。方便存取、分配、排序、查找。 o 结构    76543210765432107654321076543210    + – - – = – - – = – - – = – - – + 15 |            TimeLow            | 12 11 |    TimeMid    |   Version..   |  8 7  |Vari.. |Clock..|     Node      |  4 3  |             Node              |  0    + – - – = – - – = – - – = – - – + 15 – 12: TimeLow 时间值的低位 11 – 10: TimeMid 时间值的中位 09 – 08: VersionAndTimeHigh 4位版本号和时间值的高位 07: VariantAndClockSeqHigh 2位变体(ITU-T)和时钟序列高位 06: ClockSeqLow 时钟序列低位 05 – 00: Node 结点 hexOctet = hexDigit hexDigit hexDigit = “0″ / “1″ / “2″ / “3″ / “4″ / “5″ / “6″ / “7″ / “8″ / “9″ / “a” / “b” / “c” / “d” / “e” / “f” / “A” / “B” / “C” / “D” / “E” / “F” UUID = TimeLow “-” TimeMid “-” VersionAndTimeHigh “-” VariantAndClockSeqHigh ClockSeqLow “-” Node UUID由上述6个域构成,每个域编码为若干字节,并以16进制数表示这128位的UUID,相邻域以减号“-”分隔 (VariantAndClockSeqHigh和ClockSeqLow对应的两个字节例外,如上所示)。该结构中包含版本(Version)、变体 (Variant)、时间(Time)、时钟序列(Clock Sequence)、节点(Note)信息(以无符号整型值表示)。 o 合法性 除判断variant位设置是否正确、基于时间生成的UUID时间值是否为未经分配的将来时间外,实际应用中没有其他机制可以判定UUID是否合法。 o 变体 Variant位是UUID第7字节(VariantAndClockSeqHigh)的最高3位, 7 6 5  Descriptio[...]



终论Fibonacci数

Wed, 05 Nov 2008 16:34:00 GMT

现在每天的工作主要是为了满足项目需求和进度而不停的思考、敲键盘。有时候也确实需要抽点时间来思考思考那些看上去用不到的一些东西,又想起了Fibonacci数

之前曾经三次写过Fibonacci数:2007年4月的我的Fibonacci数列,2007年12月的也说说级数求和(1+2+3…N)和其他,2008年5月的动态规划算法,但给出的都不是非常优的算法。

上次回去把同学借的《编程之美》偷过来还没怎么看,晚上翻了一下,看到有讲Fibonacci数,想起来的The Art of Computer Programming Vol.1也讲过,觉得有必要对Fibonacci数做个了断。

诚如在The Art of Computer Programming Vol.1所述,是中世纪以来欧洲最伟大的数学家,他关于al-Khwarizmi的研究催生了算法(algorithm)一词。

阅读全文

看到这些,我又激动了,数学之美,不正是美在这些地方吗?我们不是要做数学家,但这并不妨碍我们站在门口向里张望……

(image)

Fox 2008-11-06 00:34 发表评论



动态规划算法

Wed, 07 May 2008 12:43:00 GMT

以前在学习非数值算法的时候,曾经了解过动态规划算法(Dynamic programming),以下是对Wikipedia上动态规划的翻译,图也是Wikipedia上的,仓促行文,不到之处,请方家指正。 这篇文章的术语实在是太多了,所以我在文中加入了少量注释,一律以粗斜体注明。 本文的不足之处将随时修正,MIT的《Introduction to Algorithms》第15章是专门讲动态规划的。 _____________________________________________________________ 动态规划 在数学与计算机科学领域,动态规划用于解决那些可分解为重复子问题(overlapping subproblems,想想递归求阶乘吧)并具有最优子结构(optimal substructure,想想最短路径算法)(如下所述)的问题,动态规划比通常算法花费更少时间。 上世纪40年代,Richard Bellman最早使用动态规划这一概念表述通过遍历寻找最优决策解问题的求解过程。1953年,Richard Bellman将动态规划赋予现代意义,该领域被IEEE纳入系统分析和工程中。为纪念Bellman的贡献,动态规划的核心方程被命名为贝尔曼方程,该方程以递归形式重申了一个优化问题。 在“动态规划”(dynamic programming)一词中,programming与“计算机编程”(computer programming)中的programming并无关联,而是来自“数学规划”(mathematical programming),也称优化。因此,规划是指对生成活动的优化策略。举个例子,编制一场展览的日程可称为规划。 在此意义上,规划意味着找到一个可行的活动计划。 概述   图1 使用最优子结构寻找最短路径:直线表示边,波状线表示两顶点间的最短路径(路径中其他节点未显示);粗线表示从起点到终点的最短路径。 不难看出,start到goal的最短路径由start的相邻节点到goal的最短路径及start到其相邻节点的成本决定。     最优子结构即可用来寻找整个问题最优解的子问题的最优解。举例来说,寻找图上某顶点到终点的最短路径,可先计算该顶点所有相邻顶点至终点的最短路径,然后以此来选择最佳整体路径,如图1所示。 一般而言,最优子结构通过如下三个步骤解决问题: a) 将问题分解成较小的子问题; b) 通过递归使用这三个步骤求出子问题的最优解; c) 使用这些最优解构造初始问题的最优解。 子问题的求解是通过不断划分为更小的子问题实现的,直至我们可以在常数时间内求解。     图2 Fibonacci序列的子问题示意图:使用有向无环图(DAG, directed acyclic graph)而非树表示重复子问题的分解。 为什么是DAG而不是树呢?答案就是,如果是树的话,会有很多重复计算,下面有相关的解释。     一个问题可划分为重复子问题是指通过相同的子问题可以解决不同的较大问题。例如,在Fibonacci序列中,F3 = F1 + F2和F4 = F2 + F3都包含计算F2。由于计算F5需要计算F3和F4,一个比较笨的计算F5的方法可能会重复计算F2两次甚至两次以上。这一点对所有重复子问题都适用:愚蠢的做法可能会为重复计算已经解决的最优子问题的解而浪费时间。 为避免重复计算,可将已经得到的子问题的解保存起来,当我们要解决相同的子问题时,重用即可。该方法即所谓的缓存(memoization,而不是存储memorization,虽然这个词亦适合,姑且这么叫吧,这个单词太难翻译了,简直就是可意会不可言传,其意义是没计算过则计算,计算过则保存)。当我们确信将不会再需要某一解时,可以将其抛弃,以节省空间。在某些情况下,我们甚至可以提前计算出那些将来会用到的子问题的解。 总括而言,动态规划利用: 1) 重复子问题 2) 最优子结构 3) 缓存 动态规划通[...]